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

Ответ 1

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

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

Изменить: Я только что провел небольшой тест на этом и используя буферный подход (размер буфера 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;
}

Ответ 2

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

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

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

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

Было указано, что вы можете использовать mmap с алгоритмами stl С++ и создать функтор для перехода к std:: foreach. Я предложил вам не делать этого не потому, что вы не можете этого сделать, но нет никакой выгоды в написании дополнительного кода для этого. Или вы можете использовать boost mmapped iterator, который обрабатывает все это для вас; но для проблемы код, с которым я связан, был написан для этого, был намного, намного медленнее, и вопрос касался скорости, а не стиля.

Ответ 3

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

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

Ответ 4

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

• Что кодирует файл? Байт-байтовые решения будут работать для ASCII и UTF-8, но следите за тем, есть ли у вас UTF-16 или несколько многобайтовых кодировок, что не гарантирует, что байт со значением линейного фида обязательно кодирует фид строки.

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

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

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

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

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

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

Ответ 5

Помните, что все флаги буферизуются. Таким образом, они in-effect действительно читают в кусках, поэтому вам не нужно воссоздавать эту функциональность. Итак, все, что вам нужно сделать, это сканировать буфер. Не используйте 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.
}

Ответ 6

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

Однако, я сказал, что нет более быстрого алгоритма, но есть более быстрый механизм, который называется "Memory Mapped file". Есть некоторые недостатки для сопоставленных файлов, и это может быть неприемлемо для вас., Поэтому вам придется прочитать об этом и выяснить сами.

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

Ответ 7

Вы можете получить окончательный ответ, просмотрев весь файл, ищущий символы новой строки. Ничего подобного.

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

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

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

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

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

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

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

Ответ 8

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

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

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

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

Чтение больших объемов данных с жесткого диска происходит медленно. Ничего подобного.