Чтение целых чисел из отформатированного файла памяти - PullRequest
Новая
       40

Чтение целых чисел из отформатированного файла памяти

2 голосов
/ 16 ноября 2010

У меня в памяти отображен большой отформатированный (текстовый) файл, содержащий одно целое число в строке, например: 

123
345
34324
3232
...

Итак, у меня есть указатель на память в первом байте, а также указатель на память в последнем байте. Я пытаюсь прочитать все эти целые числа в массив как можно быстрее. Первоначально я создал специализированный класс std :: streambuf для работы с std :: istream для чтения из этой памяти, но он кажется относительно медленным.

Есть ли у вас какие-либо предложения о том, как эффективно анализировать строку типа "1231232 \ r \ n123123 \ r \ n123 \ r \ n1231 \ r \ n2387897 ..." в массив {1231232,123123,1231,231, 2387897, ...}?

Число целых чисел в файле заранее неизвестно.

Ответы [ 4 ]

1 голос
/ 17 ноября 2010

Это было действительно интересной задачей для меня, чтобы узнать немного больше о C ++.

Допустим, код довольно большой и содержит множество проверок ошибок, но это только показывает, сколько разных вещей может пойти не так во время синтаксического анализа. 

#include <ctype.h>
#include <limits.h>
#include <stdio.h>

#include <iterator>
#include <vector>
#include <string>

static void
die(const char *reason)
{
  fprintf(stderr, "aborted (%s)\n", reason);
  exit(EXIT_FAILURE);
}

template <class BytePtr>
static bool
read_uint(BytePtr *begin_ref, BytePtr end, unsigned int *out)
{
  const unsigned int MAX_DIV = UINT_MAX / 10;
  const unsigned int MAX_MOD = UINT_MAX % 10;

  BytePtr begin = *begin_ref;
  unsigned int n = 0;

  while (begin != end && '0' <= *begin && *begin <= '9') {
    unsigned digit = *begin - '0';
    if (n > MAX_DIV || (n == MAX_DIV && digit > MAX_MOD))
      die("unsigned overflow");
    n = 10 * n + digit;
    begin++;
  }

  if (begin == *begin_ref)
    return false;

  *begin_ref = begin;
  *out = n;
  return true;
}

template <class BytePtr, class IntConsumer>
void
parse_ints(BytePtr begin, BytePtr end, IntConsumer out)
{
  while (true) {
    while (begin != end && *begin == (unsigned char) *begin && isspace(*begin))
      begin++;
    if (begin == end)
      return;

    bool negative = *begin == '-';
    if (negative) {
      begin++;
      if (begin == end)
        die("minus at end of input");
    }

    unsigned int un;
    if (!read_uint(&begin, end, &un))
      die("no number found");

    if (!negative && un > INT_MAX)
      die("too large positive");
    if (negative && un > -((unsigned int)INT_MIN))
      die("too small negative");

    int n = negative ? -un : un;
    *out++ = n;
  }
}

static void
print(int x)
{
  printf("%d\n", x);
}

int
main()
{
  std::vector<int> result;
  std::string input("2147483647 -2147483648 0 00000 1 2 32767 4 -17 6");

  parse_ints(input.begin(), input.end(), back_inserter(result));

  std::for_each(result.begin(), result.end(), print);
  return 0;
}

Я изо всех сил старался не вызывать неопределенного поведения , что может быть довольно сложно при преобразовании чисел без знака в числа со знаком или при вызове isspace для неизвестного типа данных.

0 голосов
/ 16 ноября 2010

Поскольку это отображение в память, очень эффективными будут простые копии символов в массив стека и atoi в другой целочисленный массив поверх другого файла отображения памяти.Таким образом, файл подкачки вообще не используется для этих больших буферов. 

open memory mapped file to output int buffer

declare small stack buffer of 20 chars
while not end of char array
  while current char not  line feed
    copy chars to stack buffer
    null terminate the buffer two chars back
    copy results of int buffer output buffer
    increment the output buffer pointer
  end while  
end while

Хотя библиотека не используется, она имеет преимущество, заключающееся в минимизации использования памяти для файлов, отображаемых в память, поэтому временные буферыограничено стеком один и тот, который используется atoi внутри.Выходной буфер может быть отброшен или сохранен в файл по мере необходимости.

0 голосов
/ 16 ноября 2010 
std::vector<int> array;
char * p = ...; // start of memory mapped block
while ( not end of memory block )
{
    array.push_back(static_cast<int>(strtol(p, &p, 10)));
    while (not end of memory block && !isdigit(*p))
        ++p;
}

Этот код немного небезопасен, так как нет гарантии, что strtol остановится в конце блока отображенной памяти, но это начало. Должен идти очень быстро даже с добавленной дополнительной проверкой.

0 голосов
/ 16 ноября 2010

ПРИМЕЧАНИЕ. Этот ответ редактировался несколько раз.

Считывает память построчно (на основе ссылка и ссылка ). 

class line 
{
   std::string data;
public:
   friend std::istream &operator>>(std::istream &is, line &l) 
   {
      std::getline(is, l.data);
      return is;
   }
   operator std::string() { return data; }    
};

std::streambuf osrb;
setg(ptr, ptr, ptrs + size-1);
std::istream istr(&osrb);

std::vector<int> ints;

std::istream_iterator<line> begin(istr);
std::istream_iterator<line> end;
std::transform(begin, end, std::back_inserter(ints), &boost::lexical_cast<int, std::string>);
...