Самый быстрый способ найти количество строк в тексте (C++)
Определите UITableViewDelegate и UITableViewDataSource в ваших UIViewController
8 ответов
Единственный способ узнать количество строк - это прочитать весь файл и подсчитать количество символов конца строки. Самый быстрый способ сделать это, вероятно, - прочитать весь файл в большой буфер за одну операцию чтения, а затем пройти через буфер, считая символы '\ n'.
Поскольку ваш текущий размер файла составляет около 60 МБ, это не привлекательный вариант. Вы можете получить некоторую скорость, не читая файл целиком, а читая его по частям, скажем размером 1 МБ. Вы также говорите, что о базе данных не может быть и речи, но она действительно выглядит лучшим долгосрочным решением.
Изменить: Я только что провел небольшой тест по этому вопросу, используя подход с буферизацией (размер буфера 1024K) кажется чуть более чем в два раза быстрее, чем чтение строки с помощью getline (). Вот' s код - мои тесты были выполнены с 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;
}
Не используйте строки C ++ stl и getline (или fgets C), только необработанные указатели в стиле C и либо блокируйте чтение фрагментами размера страницы, либо mmap файла.
Затем просканируйте блок с исходным размером слова вашей системы (то есть uint32_t или uint64_t ), используя один из магических алгоритмов 'SIMD Within A Register (SWAR) Operations »для проверки байтов в слове. Например, здесь ; цикл с 0x0a0a0a0a0a0a0a0aLL в нем сканирует на наличие разрывов строки. (этот код составляет около 5 циклов на входной байт, соответствующий регулярному выражению в каждой строке файла)
Если размер файла составляет всего несколько десятков или сотен или около того мегабайт, и он продолжает расти (т.е. что-то продолжает писать в него ), то есть' Есть большая вероятность, что linux кэширует его в памяти, поэтому он не будет ограничен дисковым вводом-выводом, а будет ограничена пропускная способность памяти.
Если файл только когда-либо добавляется, вы также можете запомнить количество строк и предыдущая длина, и начать оттуда.
Было указано, что вы можете использовать mmap с алгоритмами stl C ++ и создать функтор для перехода к std :: foreach. Я посоветовал вам не делать этого не потому, что вы не можете этого сделать, но нет никакой выгоды в написании дополнительного кода для этого. Или вы можете использовать итератор boost mmapped, который сделает все за вас; но из-за проблемы код, на который я ссылался, был написан, потому что он был намного медленнее, и вопрос был в скорости, а не в стиле.
You wrote that it keeps get larger. Похоже, это файл журнала или что-то подобное, где новые строки добавляются, но существующие строки не меняются. В этом случае вы можете попробовать инкрементный подход .
Разобрать до конца файла.
Запомните количество строк и смещение EOF.
Когда файл увеличивается fseek до смещения, выполните синтаксический анализ до EOF и обновите счетчик строк и смещение.
Это не медленно из-за вашего алгоритма, оно медленное из-за медленных операций ввода-вывода. Я полагаю, вы используете простой алгоритм O (n), который просто последовательно просматривает файл. В этом случае нет более быстрого алгоритма, который может оптимизировать вашу программу.
Однако , я сказал, что нет более быстрого алгоритма, но есть более быстрый механизм, который называется «Файл с отображением памяти» ,
Помните, что все fstreams буферизуются. Таким образом, они фактически читают по частям, поэтому вам не нужно воссоздавать эту функциональность. Итак, все, что вам нужно сделать, это просканировать буфер. Не используйте 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.
}
Есть разница между счетными линиями и разделителями счетных строк. Некоторые общие ошибки, на которые следует обратить внимание, если важно получить точное количество строк:
Какая кодировка файла? Побайтовые решения будут работать для 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 ()видеть весь файл как одну гигантскую строку.) Читая фрагменты в буфер фиксированного размера и используя конечный автомат, вы можете сделать его пуленепробиваемым.
Код в принятый ответ страдает от большинства этих ловушек. Сделайте это правильно, прежде чем приступить к работе.
То, что требует времени, - это загрузка 40+ МБ в память. Самый быстрый способ сделать это - либо отобразить его в памяти, либо загрузить за один раз в большой буфер. Когда он так или иначе находится в памяти, цикл, просматривающий данные в поисках \ n символов, становится почти мгновенным, независимо от того, как он реализован.
Итак, на самом деле, самый важный трюк - это чтобы как можно быстрее загрузить файл в память. И самый быстрый способ сделать это - выполнить это как одну операцию.
В противном случае может существовать множество уловок для ускорения алгоритма. Если строки только добавляются, никогда не изменяются и не удаляются, и если вы читаете файл неоднократно, вы можете кэшировать ранее прочитанные строки, а в следующий раз, когда вам нужно будет прочитать файл, прочтите только недавно добавленные строки.
Или, возможно, вы можете вести отдельный индексный файл, показывающий расположение известных символов '\ n', чтобы эти части файла можно было пропустить.
Чтение больших объемов данных с жесткого диска происходит медленно. Никакого другого выхода нет.
Вы можете получить окончательный ответ только путем сканирования всего файла в поисках символов новой строки. Нет никакого способа обойти это.
Однако есть несколько возможностей, которые вы можете рассмотреть.
1 / Если вы используете упрощенный цикл, читая по одному символу за раз, проверяя наличие новой строки, не т. Несмотря на то, что ввод-вывод может быть буферизован, вызовы функций сами по себе дороги с точки зрения времени.
Лучшим вариантом является чтение больших фрагментов файла (скажем, 5 МБ) в память с помощью одной операции ввода-вывода, а затем обработка который. Вам, вероятно, не стоит особо беспокоиться о специальных инструкциях по сборке, поскольку библиотека времени выполнения C все равно будет оптимизирована - это должна сделать простая strchr () .
2 / Если вы так говорите. общая длина строки составляет около 40-50 символов, и вы не log через некоторый конвейер процесса, а не cat x.log . Чтобы получить количество строк в «файле», выполните wc -l в текущем x.log (относительно быстро) и добавьте его к сумме всех значений в x_ *. подсчитать файлов.