Как быстро анализировать пространственно разделенные поплавки на С++?

Ответ 1

Если преобразование - это горло бутылки (что вполне возможно) вы должны начать с использования различных возможностей в стандарт. Логично, можно было бы ожидать, что они будут очень близки, но практически, они не всегда:

• Вы уже определили, что std::ifstream работает слишком медленно.

• Преобразование данных с отображением памяти в std::istringstream почти наверняка не является хорошим решением; вам сначала придется создайте строку, которая скопирует все данные.

• Написание собственного streambuf для чтения непосредственно из памяти, без копирования (или с использованием устаревшего std::istrstream) может быть решением, хотя, если проблема действительно преобразование... это все еще использует те же процедуры преобразования.

• Вы всегда можете попробовать fscanf или scanf в вашей карте памяти поток. В зависимости от реализации они могут быть быстрее чем различные реализации istream.

• Вероятно, быстрее любого из них следует использовать strtod. Не нужно tokenize для этого: strtod пропускает ведущее пустое пространство (включая '\n'), и имеет параметр out, где он помещает адрес первого символа не читается. Конечное условие немного сложно, ваш цикл, вероятно, должен выглядеть примерно так:

    char* begin;    //  Set to point to the mmap'ed data...
                    //  You'll also have to arrange for a '\0'
                    //  to follow the data.  This is probably
                    //  the most difficult issue.
    char* end;
    errno = 0;
    double tmp = strtod( begin, &end );
    while ( errno == 0 && end != begin ) {
        //  do whatever with tmp...
        begin = end;
        tmp = strtod( begin, &end );
    }

Если ни одно из них недостаточно быстро, вам нужно будет рассмотреть фактические данные. Вероятно, у него есть какая-то дополнительная ограничений, что означает, что вы можете написать процедура преобразования, которая быстрее, чем более общие; например strtod должен обрабатывать как фиксированные, так и научные, и это должен быть на 100% точным, даже если имеется 17 значащих цифр. Он также должен быть специфичным для локали. Все это добавлено сложность, что означает добавленный код для выполнения. Но будьте осторожны: написав эффективную и правильную процедуру преобразования, даже для ограниченный набор входных данных, нетривиален; вам действительно нужно знайте, что вы делаете.

EDIT:

Просто из любопытства я провел несколько тестов. В добавок к вышеупомянутые решения, я написал простой пользовательский конвертер, который обрабатывает только фиксированную точку (без научной), причем максимум пять цифр после десятичного знака, а значение до десятичной должен соответствовать int:

double
convert( char const* source, char const** endPtr )
{
    char* end;
    int left = strtol( source, &end, 10 );
    double results = left;
    if ( *end == '.' ) {
        char* start = end + 1;
        int right = strtol( start, &end, 10 );
        static double const fracMult[] 
            = { 0.0, 0.1, 0.01, 0.001, 0.0001, 0.00001 };
        results += right * fracMult[ end - start ];
    }
    if ( endPtr != nullptr ) {
        *endPtr = end;
    }
    return results;
}

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

Интерфейс в точности соответствует strtod, чтобы упростить кодирование.

Я провел тесты в двух средах (на разных машинах, поэтому абсолютные значения любого времени не имеют значения). Я получил следующие результаты:

В Windows 7, скомпилированном с VC 11 (/O2):

Testing Using fstream directly (5 iterations)...
    6.3528e+006 microseconds per iteration
Testing Using fscan directly (5 iterations)...
    685800 microseconds per iteration
Testing Using strtod (5 iterations)...
    597000 microseconds per iteration
Testing Using manual (5 iterations)...
    269600 microseconds per iteration

В Linux 2.6.18, скомпилированный с g++ 4.4.2 (-O2, IIRC):

Testing Using fstream directly (5 iterations)...
    784000 microseconds per iteration
Testing Using fscanf directly (5 iterations)...
    526000 microseconds per iteration
Testing Using strtod (5 iterations)...
    382000 microseconds per iteration
Testing Using strtof (5 iterations)...
    360000 microseconds per iteration
Testing Using manual (5 iterations)...
    186000 microseconds per iteration

Во всех случаях я читаю 554000 строк, каждый из которых 3 случайным образом сгенерированной с плавающей запятой в диапазоне [0...10000).

Самое поразительное - огромная разница между fstream и fscan под Windows (и относительно небольшая разница между fscan и strtod). Во-вторых, насколько сильно выигрывает простая пользовательская функция преобразования, на обе платформы. Необходимая обработка ошибок замедлит работу немного, но разница все еще значительна. Я ожидал некоторые улучшения, поскольку он не обрабатывает много вещей, стандартные процедуры преобразования (например, научный формат, очень, очень маленькие числа, Inf и NaN, i18n и т.д.), но не это много.

Ответ 2

UPDATE

Так как Spirit X3 доступен для тестирования, я обновил тесты. Тем временем я использовал Nonius, чтобы получить статистически обоснованные тесты.

Все доступные ниже графики доступны интерактивный онлайн

Benchmark Проект CMake + testdata используется для github: https://github.com/sehe/bench_float_parsing

Резюме:

Парсеры Spirit быстрее. Если вы можете использовать С++ 14, рассмотрите экспериментальную версию Spirit X3:

Вышеуказанные меры используются с использованием файлов с отображением памяти. Используя IOstream, он будет медленнее по сравнению с доской,

но не так медленно, как scanf, используя вызовы функций C/POSIX FILE*:

Далее следует части из OLD-ответа

Я реализовал версию Spirit и провел сравнительный тест по сравнению с другими предлагаемыми ответами.

Здесь мои результаты, все тесты выполняются на одном и том же элементе ввода (515Mb input.txt). См. Ниже точные спецификации.

^{(время настенных часов в секундах, среднее значение 2+ пробегов)}

К моему собственному удивлению, Boost Spirit получается самым быстрым и самым элегантным:

• обрабатывает/сообщает об ошибках
• поддерживает +/- Inf и NaN и переменные пробелы.
• никаких проблем при обнаружении конца ввода (в отличие от другого ответа mmap)

• выглядит хорошо:

  bool ok = phrase_parse(f,l,               // source iterators
       (double_ > double_ > double_) % eol, // grammar
       blank,                               // skipper
       data);                               // output attribute
  

Обратите внимание, что boost::spirit::istreambuf_iterator был невыразимо медленнее (15s +). Надеюсь, это поможет!

Детали контрольных показателей

Все разбор делается на vector of struct float3 { float x,y,z; }.

Создание входного файла с помощью

od -f -A none --width=12 /dev/urandom | head -n 11000000

В результате получается файл размером 515 Мб, содержащий данные типа

     -2627.0056   -1.967235e-12  -2.2784738e+33
  -1.0664798e-27  -4.6421956e-23   -6.917859e+20
  -1.1080849e+36   2.8909405e-33   1.7888695e-12
  -7.1663235e+33  -1.0840628e+36   1.5343362e-12
  -3.1773715e-17  -6.3655537e-22   -8.797282e+31
    9.781095e+19   1.7378472e-37        63825084
  -1.2139188e+09  -5.2464635e-05  -2.1235992e-38
   3.0109424e+08   5.3939846e+30  -6.6146894e-20

Скомпилируйте программу, используя:

g++ -std=c++0x -g -O3 -isystem -march=native test.cpp -o test -lboost_filesystem -lboost_iostreams

Измерьте время настенных часов с помощью

time ./test < input.txt 

Окружающая среда:

• Рабочий стол Linux 4.2.0-42-общий # 49-Ubuntu SMP x86_64
• Intel (R) Core (TM) i7-3770K CPU @3,50 ГГц
• 32GiB RAM

Полный код

Полный код для старого теста находится в истории изменений этого сообщения, самая новая версия на github

Ответ 3

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

boost::spirit для меня, по моему мнению, будет излишним. Попробуйте fscanf

FILE* f = fopen("yourfile");
if (NULL == f) {
   printf("Failed to open 'yourfile'");
   return;
}
float x,y,z;
int nItemsRead = fscanf(f,"%f %f %f\n", &x, &y, &z);
if (3 != nItemsRead) {
   printf("Oh dear, items aren't in the right format.\n");
   return;
}

Ответ 4

Я бы посмотрел этот связанный пост Использование ifstream для чтения float или Как я хочу tokenize строку в С++ особенно сообщения, связанные с С++ String Toolkit Library. Я использовал C strtok, потоки С++, Boost tokenizer и лучшие из них для удобства и использования - С++ String Toolkit Library.

Ответ 5

использование C будет самым быстрым решением. Разделить на токены с помощью strtok, а затем конвертировать в float с strtof. Или, если вы знаете точный формат, используйте fscanf.

Ответ 6

решающее решение было бы бросить больше ядер в проблему, порождая несколько потоков. Если узким местом является только процессор, вы можете сократить время работы на два потока (на многоядерных процессорах)

некоторые другие советы:

• старайтесь не разбирать функции из библиотеки, такие как boost и/или std. Они раздуты с условиями проверки ошибок, и большая часть времени обработки тратится на эти проверки. Всего за пару конверсий они прекрасны, но терпят неудачу, когда дело доходит до обработки миллионов ценностей. Если вы уже знаете, что ваши данные хорошо отформатированы, вы можете написать (или найти) настраиваемую оптимизированную функцию C, которая выполняет только преобразование данных

• используйте большой буфер памяти (скажем, 10 Мбайт), в котором вы загружаете куски вашего файла и выполняете конверсию там

• divide et impera: разделите свою проблему на более мелкие: предварительно обработайте свой файл, сделайте его одиночным одиночным поплавком, разделите каждую строку на "." символа и преобразовать целые числа вместо float, а затем объединить два целых числа для создания числа с плавающей точкой

Ответ 7

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

Я сделал простую тестовую программу, чтобы показать, насколько она проста. Мой тест говорит, что этот код работает на 40% быстрее, чем strtod версия.

#include <iostream>
#include <sstream>
#include <iomanip>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>

using namespace std;

string test_generate(size_t n)
{
    srand((unsigned)time(0));
    double sum = 0.0;
    ostringstream os;
    os << std::fixed;
    for (size_t i=0; i<n; ++i)
    {
        unsigned u = rand();
        int w = 0;
        if (u > UINT_MAX/2)
            w = - (u - UINT_MAX/2);
        else
            w = + (u - UINT_MAX/2);
        double f = w / 1000.0;
        sum += f;

        os << f;
        os << " ";
    }
    printf("generated %f\n", sum);
    return os.str();
}

void read_float_ss(const string& in)
{
    double sum = 0.0;
    const char* begin = in.c_str();
    char* end = NULL;
    errno = 0;
    double f = strtod( begin, &end );
    sum += f;

    while ( errno == 0 && end != begin )
    {
        begin = end;
        f = strtod( begin, &end );
        sum += f;
    }
    printf("scanned %f\n", sum);
}

double scan_float(const char* str, size_t& off, size_t len)
{
    static const double bases[13] = {
        0.0, 10.0, 100.0, 1000.0, 10000.0,
        100000.0, 1000000.0, 10000000.0, 100000000.0,
        1000000000.0, 10000000000.0, 100000000000.0, 1000000000000.0,
    };

    bool begin = false;
    bool fail = false;
    bool minus = false;
    int pfrac = 0;

    double dec = 0.0;
    double frac = 0.0;
    for (; !fail && off<len; ++off)
    {
        char c = str[off];
        if (c == '+')
        {
            if (!begin)
                begin = true;
            else
                fail = true;
        }
        else if (c == '-')
        {
            if (!begin)
                begin = true;
            else
                fail = true;
            minus = true;
        }
        else if (c == '.')
        {
            if (!begin)
                begin = true;
            else if (pfrac)
                fail = true;
            pfrac = 1;
        }
        else if (c >= '0' && c <= '9')
        {
            if (!begin)
                begin = true;
            if (pfrac == 0)
            {
                dec *= 10;
                dec += c - '0';
            }
            else if (pfrac < 13)
            {
                frac += (c - '0') / bases[pfrac];
                ++pfrac;
            }
        }
        else
        {
            break;
        }
    }

    if (!fail)
    {
        double f = dec + frac;
        if (minus)
            f = -f;
        return f;
    }

    return 0.0;
}

void read_float_direct(const string& in)
{
    double sum = 0.0;
    size_t len = in.length();
    const char* str = in.c_str();
    for (size_t i=0; i<len; ++i)
    {
        double f = scan_float(str, i, len);
        sum += f;
    }
    printf("scanned %f\n", sum);
}

int main()
{
    const int n = 1000000;
    printf("count = %d\n", n);

    string in = test_generate(n);    
    {
        struct timeval t1;
        gettimeofday(&t1, 0);
        printf("scan start\n");

        read_float_ss(in);

        struct timeval t2;
        gettimeofday(&t2, 0);
        double elapsed = (t2.tv_sec - t1.tv_sec) * 1000000.0;
        elapsed += (t2.tv_usec - t1.tv_usec) / 1000.0;
        printf("elapsed %.2fms\n", elapsed);
    }

    {
        struct timeval t1;
        gettimeofday(&t1, 0);
        printf("scan start\n");

        read_float_direct(in);

        struct timeval t2;
        gettimeofday(&t2, 0);
        double elapsed = (t2.tv_sec - t1.tv_sec) * 1000000.0;
        elapsed += (t2.tv_usec - t1.tv_usec) / 1000.0;
        printf("elapsed %.2fms\n", elapsed);
    }
    return 0;
}

Ниже представлен вывод консоли из i7 Mac Book Pro (скомпилирован в XCode 4.6).

count = 1000000
generated -1073202156466.638184
scan start
scanned -1073202156466.638184
elapsed 83.34ms
scan start
scanned -1073202156466.638184
elapsed 53.50ms