Самый быстрый способ узнать количество строк в тексте (C ++)

Question

Мне нужно прочитать количество строк в файле перед выполнением некоторых операций с этим файлом. Когда я пытаюсь прочитать файл и увеличивать переменную line_count на каждой итерации, пока не достигну eof. В моем случае это было не так быстро. Я использовал как ifstream, так и fgets. Они оба были медленными. Есть ли хакерский способ сделать это, который также используется, например, BSD, ядром Linux или Berkeley DB (может быть с помощью побитовых операций).

Как я уже говорил, в этом файле миллионы строк, и он продолжает увеличиваться, каждая строка содержит около 40 или 50 символов. Я использую Linux.

Примечание: Я уверен, что найдутся люди, которые скажут, что используют DB идиот. Но кратко в моем случае я не могу использовать БД.

Answer 1

Единственный способ узнать количество строк - это прочитать весь файл и посчитать количество символов конца строки. Самый быстрый способ сделать это, вероятно, - это прочитать весь файл в большой буфер за одну операцию чтения, а затем пройти через буфер, считая символы '\ n'.

Поскольку текущий размер файла составляет около 60 МБ, это не очень привлекательный вариант. Вы можете получить некоторую скорость, не читая весь файл, а читая его кусками, скажем, размером 1Mb. Вы также говорите, что о базе данных не может быть и речи, но она действительно выглядит лучшим долгосрочным решением.

Редактировать: Я только что провел небольшой тест по этому вопросу, и использование буферизованного подхода (размер буфера 1024 КБ) кажется более чем в два раза быстрее, чем чтение строки за раз с помощью getline () , Вот код - мои тесты были выполнены на g ++ с использованием уровня оптимизации -O2:

#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
using namespace std;

unsigned int FileRead( istream & is, vector <char> & buff ) {
    is.read( &buff[0], buff.size() );
    return is.gcount();
}

unsigned int CountLines( const vector <char> & buff, int sz ) {
    int newlines = 0;
    const char * p = &buff[0];
    for ( int i = 0; i < sz; i++ ) {
        if ( p[i] == '\n' ) {
            newlines++;
        }
    }
    return newlines;
}

int main( int argc, char * argv[] ) {
    time_t now = time(0);
    if ( argc == 1  ) {
        cout << "lines\n";
        ifstream ifs( "lines.dat" );
        int n = 0;
        string s;
        while( getline( ifs, s ) ) {
            n++;
        }
        cout << n << endl;
    }
    else {
        cout << "buffer\n";
        const int SZ = 1024 * 1024;
        std::vector <char> buff( SZ );
        ifstream ifs( "lines.dat" );
        int n = 0;
        while( int cc = FileRead( ifs, buff ) ) {
            n += CountLines( buff, cc );
        }
        cout << n << endl;
    }
    cout << time(0) - now << endl;
}

Answer 2

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

Разбор до конца файла. Запомните количество строк и смещение EOF. Когда размер файла увеличится на fseek до смещения, проанализируйте EOF и обновите счетчик строк и смещение.

Answer 3

Не используйте строки st ++ C ++ и getline (или fgets C), только необработанные указатели в стиле C и либо блок чтения в кусках размера страницы, либо mmap файл.

Затем отсканируйте блок по собственному размеру слова вашей системы (то есть либо uint32_t или uint64_t), используя один из магических алгоритмов «Операции SIMD Within A Register (SWAR)» для тестирования байты в слове. Например, здесь ; цикл с 0x0a0a0a0a0a0a0a0aLL сканирует разрывы строк. (этот код получает около 5 циклов на входной байт, соответствующий регулярному выражению в каждой строке файла)

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

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

---

Было отмечено, что вы можете использовать mmap с алгоритмами st ++ C ++ и создать функтор для передачи в std :: foreach. Я предложил вам не делать этого не потому, что вы не можете сделать это таким образом, но нет никакого смысла в написании дополнительного кода для этого. Или вы можете использовать итератор Boost Mmapped, который обрабатывает все это для вас; но для этой проблемы код, на который я ссылался, был написан для этого намного медленнее, и вопрос был о скорости, а не о стиле.

Answer 4

Существует разница между счетчиками строк и счетчиками строк. Некоторые распространенные ошибки, на которые стоит обратить внимание, если важно получить точное количество строк:

1. Какая кодировка файла? Побайтовые решения будут работать для ASCII и UTF-8, но будьте осторожны, если у вас есть UTF-16 или какое-нибудь многобайтовое кодирование, которое не гарантирует, что байт со значением перевода строки обязательно кодирует перевод строки.

2. Многие текстовые файлы не имеют разделителя строк в конце последней строки. Поэтому, если в вашем файле указано "Hello, World!", вы можете получить счетчик 0 вместо 1. Вместо того, чтобы просто считать разделители строк, вам понадобится простой конечный автомат для отслеживания.

3. Некоторые очень непонятные файлы используют Unicode U+2028 LINE SEPARATOR (или даже U+2029 PARAGRAPH SEPARATOR) в качестве разделителей строк вместо более распространенного возврата каретки и / или перевода строки. Вы также можете следить за U+0085 NEXT LINE (NEL).

4. Вам нужно будет подумать, хотите ли вы считать некоторые другие управляющие символы в качестве переносчиков строк. Например, следует ли считать U+000C FORM FEED или U+000B LINE TABULATION (например, вертикальная табуляция) переходом на новую строку?

5. Текстовые файлы из более старых версий Mac OS (до OS X) используют возврат каретки (U+000D), а не переводы строк (U+000A) для разделения строк. Если вы читаете необработанные байты в буфер (например, с вашим потоком в двоичном режиме) и сканируете их, вы получите счетчик 0 для этих файлов. Вы не можете рассчитывать как возврат каретки, так и перевод строки, поскольку файлы ПК обычно заканчивают строку обоими. Опять же, вам понадобится простой конечный автомат. (В качестве альтернативы вы можете прочитать файл в текстовом режиме, а не в двоичном режиме. Текстовые интерфейсы нормализуют разделители строк до '\n' для файлов, которые соответствуют соглашению, используемому на вашей платформе. Если вы читаете файлы с других платформ, вы вернусь в двоичный режим с конечным автоматом.)

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

Код в принятом ответе страдает от большинства этих ловушек. Сделай это прямо перед тем, как быстро.

Answer 5

Помните, что все потоки буферизируются. Таким образом, они в действительности читают порциями, поэтому вам не нужно заново создавать эту функцию. Так что все, что вам нужно сделать, это просканировать буфер. Не используйте getline (), поскольку это заставит вас измерять строку. Поэтому я бы просто использовал STL std :: count и потоковые итераторы.

#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>


struct TestEOL
{
    bool operator()(char c)
    {
        last    = c;
        return last == '\n';
    }
    char    last;
};

int main()
{
    std::fstream  file("Plop.txt");

    TestEOL       test;
    std::size_t   count   = std::count_if(std::istreambuf_iterator<char>(file),
                                          std::istreambuf_iterator<char>(),
                                          test);

    if (test.last != '\n')  // If the last character checked is not '\n'
    {                       // then the last line in the file has not been 
        ++count;            // counted. So increement the count so we count
    }                       // the last line even if it is not '\n' terminated.
}

Answer 6

Вы можете получить окончательный ответ только путем сканирования всего файла в поисках символов новой строки. Обойти это невозможно.

Однако есть пара возможностей, которые вы можете рассмотреть.

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

Лучшим вариантом является чтение больших кусков файла (скажем, 5M) в память с помощью одной операции ввода-вывода, а затем обработка. Вам, вероятно, не нужно слишком беспокоиться о специальных инструкциях по сборке, так как библиотека времени выполнения C все равно будет оптимизирована - простой strchr() должен сделать это.

2 / Если вы говорите, что общая длина строки составляет около 40-50 символов, и вам не нужно точное количество строк, просто возьмите размер файла и разделите на 45 (или что-то еще среднее значение, которое вы считаете нужным).

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

Например, когда он достигает 5M, переместите его (например, x.log) к датированному имени файла (например, x_20090101_1022.log) и определите, сколько строк в этой точке (сохраняя в * 1020) *, затем запустите новый файл журнала x.log Характеристики файлов журнала означают, что созданный датированный раздел никогда не изменится, поэтому вам никогда не придется пересчитывать количество строк.

Чтобы обработать «файл» журнала, вам нужно просто cat x_*.log через некоторый канал процесса, а не cat x.log. Чтобы получить количество строк в «файле», выполните wc -l в текущем x.log (относительно быстро) и добавьте его к сумме всех значений в x_*.count файлах.

Answer 7

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

Однако , я сказал, что нет более быстрого алгоритма, но есть более быстрый механизм, который называется «Файл с отображенной памятью». Есть некоторые недостатки для отображаемых файлов, и он может не подходить для вашего случая Поэтому вам придется прочитать об этом и самим разобраться.

Файлы с отображенной памятью не позволят вам реализовать алгоритм лучше, чем O (n), но может сократит время доступа к IO.

Answer 8

То, что требует времени, - это загрузка 40+ МБ в память. Самый быстрый способ сделать это - либо отобразить карту памяти, либо загрузить ее за один раз в большой буфер. После того, как он у вас в памяти, так или иначе, цикл, проходящий по данным в поисках \n символов, становится практически мгновенным, независимо от того, как он реализован.

Так что, действительно, самый важный трюк - это загрузить файл в память как можно быстрее. И самый быстрый способ сделать это - выполнить одну операцию.

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

Или, возможно, вы можете сохранить отдельный индексный файл, показывающий расположение известных символов '\ n', чтобы эти части файла можно было пропустить.

Медленное чтение больших объемов данных с жесткого диска. Обойти это невозможно.