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

Question

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

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

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

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

27

c++ line-count

Источник

user50676 09 май '09 в 11:28

9 ответов

Решение

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

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

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

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

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

11

Источник

user1527 09 май '09 в 11:38

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

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

10

Источник

user84671 09 май '09 в 12:42

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

Какая кодировка файла? Побайтовые решения будут работать для ASCII и UTF-8, но будьте внимательны, если у вас есть UTF-16 или какое-нибудь многобайтовое кодирование, которое не гарантирует, что байт со значением перевода строки обязательно кодирует перевод строки.
Многие текстовые файлы не имеют разделителя строк в конце последней строки. Так что если ваш файл говорит "Hello, World!", вы можете получить счетчик 0 вместо 1. Вместо того, чтобы просто считать разделители строк, вам понадобится простой конечный автомат для отслеживания.
Некоторые очень непонятные файлы используют Unicode U+2028 LINE SEPARATOR (или даже U+2029 PARAGRAPH SEPARATOR) в качестве разделителей строк вместо более распространенного возврата каретки и / или перевода строки. Вы также можете следить за U+0085 NEXT LINE (NEL),
Вам нужно будет подумать, хотите ли вы считать некоторые другие управляющие символы в качестве переносчиков строк. Например, если U+000C FORM FEED или же U+000B LINE TABULATION (ака вертикальная вкладка) считается переход на новую строку?
Текстовые файлы из более старых версий Mac OS (до OS X) используют возврат каретки (U+000D), а не переводы строки (U+000A) разделять строки. Если вы читаете необработанные байты в буфер (например, с вашим потоком в двоичном режиме) и сканируете их, вы получите счетчик 0 для этих файлов. Вы не можете сосчитать как возврат каретки, так и перевод строки, потому что файлы ПК обычно заканчивают строку обоими. Опять же, вам понадобится простой конечный автомат. (В качестве альтернативы вы можете прочитать файл в текстовом режиме, а не в двоичном режиме. Текстовые интерфейсы нормализуют разделители строк в '\n' для файлов, которые соответствуют соглашению, используемому на вашей платформе. Если вы читаете файлы с других платформ, вы вернетесь в двоичный режим с конечным автоматом.)
Если у вас есть супер длинная строка в файле, getline() подход может выдать исключение, приводящее к сбою вашего простого счетчика строк на небольшом количестве файлов. (Это особенно верно, если вы читаете старый файл Mac на платформе не Mac, что приводит к getline() чтобы увидеть весь файл как одну гигантскую строку.) Считывая куски в буфер фиксированного размера и используя конечный автомат, вы можете сделать его пуленепробиваемым.

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

6

Источник

user1386054 09 май '09 в 15:18

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

4

Источник

user14065 09 май '09 в 19:16

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

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

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

Лучшим вариантом является чтение больших фрагментов файла (скажем, 5M) в память с помощью одной операции ввода-вывода, а затем обработка. Вам, вероятно, не нужно слишком беспокоиться о специальной инструкции по сборке, так как библиотека времени выполнения C все равно будет оптимизирована - простой 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 файлы.

3

Источник

user14860 09 май '09 в 12:10

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

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

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

3

Источник

user88637 09 май '09 в 11:37

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

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

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

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

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

1

Источник

user33213 09 май '09 в 12:16

Если ваш файл только растет, Ludwig Weinzierl — лучшее решение, если у вас нет контроля над писателями. В противном случае вы можете сделать это еще быстрее: увеличивать счетчик на единицу каждый раз, когда строка записывается в файл. Если несколько писателей могут пытаться одновременно писать в файл, обязательно используйте блокировку. Достаточно заблокировать существующий файл. Счетчик может состоять из 4 или 8 байтов, записанных в двоичном виде в файл, записанный под/run/<your-prog-name>/counter(это ОЗУ так быстро).

Алгоритм Людвига

Инициализировать смещение до 0
Прочитайте файл со смещения до подсчета (как упоминалось другими, обязательно используйте буферизованный ввод-вывод и подсчитайте'\n'внутри этого буфера)
Обновить смещение с позицией вEOF
Сохраняйте счетчик и смещение в файл или в переменную, если они нужны только в вашем программном обеспечении.
Повторить от "Читать файл..." при изменении

Именно так функционируют различные файлы журналов обработки программного обеспечения (т.е.fail2banприходит в голову).

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

Проактивный алгоритм

При создании файлов сбросьте счетчик на 0.

Затем каждый раз, когда вы получаете новую строку для добавления в файл:

Заблокировать файл
Напишите одну строку
Счетчик нагрузки
Добавить один к счетчику
Сохранить счетчик
Разблокировать файл

Это очень близко к тому, что делают системы баз данных.SELECT COUNT(*) FROM tableв таблице с миллионами строк возвращаются мгновенно . Базы данных также делают это для каждого индекса. Итак, если вы добавитеWHEREпункт, который соответствует определенному индексу, вы также мгновенно получите итоговую сумму . Тот же принцип, что и выше.

Личное примечание: я вижу огромное количество отсталых программ в Интернете. Сторожевой таймер имеет смысл для различных вещей в программной среде. Однако в большинстве случаев, когда происходит что-то важное, вы должны отправить сообщение в то время, когда это происходит. Не используйте обратную концепцию проверки журналов, чтобы обнаружить, что только что произошло что-то плохое.

Например, вы обнаружили, что пользователь пытался получить доступ к веб-сайту и ввел неверный пароль 5 раз подряд. Вы хотите отправить мгновенное сообщение администратору, чтобы убедиться, что 6-й раз не был успешным, и теперь хакер может видеть все данные вашего пользователя... Если вы используете журналы, «мгновенное сообщение» будет опоздал на секунды, если не на минуты.

Не выполняйте обработку в обратном порядке.

0

Источник

user212378 09 июл '22 в 21:40

Другие вопросы по тегам c++ line-count

09 май '09 в 11:37 2009-05-09 11:37 · Accepted Answer · 2009-05-09 11:37

Единственный способ узнать количество строк - это прочитать весь файл и посчитать количество символов конца строки. Самый быстрый способ сделать это, вероятно, состоит в том, чтобы прочитать весь файл в большой буфер за одну операцию чтения, а затем пройти через буфер, считая символы '\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;
}