Обработка больших текстовых файлов

Вам нужно взглянуть на "Практика программирования" Кернигана и Пайка, и конкретно глава 3.

В C++ используйте карту на основе строк и количества (std::map<string,size_t>, IIRC). Прочитайте файл (один раз — он слишком большой, чтобы читать его более одного раза), разбивая его на слова по мере продвижения (для некоторого определения «слова») и увеличивая количество в записи карты для каждого найденного слова.

В C вам придется создать карту самостоятельно. (Или найдите «C интерфейсы и реализации" Дэвида Хэнсона.)

Или вы можете использовать Perl, или Python, или Awk (все они имеют ассоциативные массивы, эквивалентные карте).

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

В случае, если ЦП действительно загружен в однопоточной версии, возможно потенциальное ускорение. Один поток мог считывать данные большими порциями и помещать их в очередь ограниченной емкости. Группа других рабочих потоков может работать каждый со своим фрагментом и считать слова. После завершения подсчета рабочих потоков вам необходимо объединить счетчики слов.

Во-первых, определитесь со структурой данных для сохранения слов.

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

Второе - многопоточность да или нет? Ответить на этот вопрос непросто. В зависимости от размера структуры данных растет и то, как вы распараллеливаете ответ, может отличаться.

1. Однопоточный — простой и простой в реализации.
2. Многопоточный с несколькими потоками чтения и одной структурой данных. Затем вы должны синхронизировать доступ к структуре данных. В Trie вам нужно только заблокировать узел, в котором вы фактически находитесь, чтобы несколько читателей могли получить доступ к структуре данных без особых помех. Самобалансирующееся дерево может быть другим, особенно при перебалансировке.
3. Многопоточный с несколькими потоками чтения, каждый со своей собственной структурой данных. Каждый поток строит свою собственную структуру данных при чтении части файла. После завершения каждого из них результаты должны быть объединены (что должно быть легко).

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

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

Один (возможный) способ получить значительную скорость - это обойти обычные потоки ввода-вывода - хотя некоторые из них почти так же быстры, как использование C FILE *, я не знаю ничего, что действительно быстрее, а некоторые значительно медленнее. Если вы используете это в системе (например, Windows), которая имеет модель ввода-вывода, заметно отличающуюся от C, вы можете получить значительно больше, если немного позаботитесь.

Проблема довольно проста: файл, который вы читаете, (потенциально) больше доступного места в кэше, но вы ничего не выиграете от кэширования, потому что вы не собираетесь снова перечитывать куски файла ( по крайней мере, если вы делаете вещи разумно). Таким образом, вы хотите, чтобы система обходила любое кэширование и просто переносила данные как можно напрямую с диска в вашу память, где вы можете их обработать. В Unix-подобной системе это, вероятно, open() и read() (и вы не получите многого). В Windows это CreateFile и ReadFile, передача флага FILE_FLAG_NO_BUFFERING в CreateFile -- и это, вероятно, примерно удвоит вашу скорость, если вы все сделаете правильно.

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

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

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

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

решение на основе c?

Я думаю, Perl был создан именно для этой цели.

поток имеет только один курсор. Если вы обращаетесь к потоку более чем с одним потоком одновременно, вы не будете уверены, что будете читать там, где хотите. Чтение выполняется с позиции курсора.

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

Например:

• Поток #i готов и попросите основной поток дать ему следующую часть,
• Основной поток читает следующие 1 Мб и передает их потоку 1,
• Тема #я читаю 1Мб и считаю слова сколько хочешь,
• Поток #i заканчивает свою работу и снова просит следующий 1Mb.

Таким образом, вы можете отделить потоковое чтение от потокового анализа.

То, что вы ищете, это RegEx. Этот поток Stackoverflow на механизмах регулярных выражений С++ должен помочь:

C++: какую библиотеку регулярных выражений следует использовать?

Во-первых, я почти уверен, что C/C++ не лучший способ справиться с этим. В идеале вы также должны использовать некоторую карту/уменьшение для параллелизма.

Но, учитывая ваши ограничения, вот что я бы сделал.

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

индекс = 0

цифры = 0

mysplitfile = открытый файл (index-split.txt)

в то время как (большой файл >> слово)

mysplitfile << word

numwords ++

if (numwords > 5000)

    mysplitfile.close()

    index++

    mysplitfile = openfile(index-split.txt)

2) Используйте общую структуру данных карты и потоки для создания новых потоков для чтения каждого из подфайлов. Опять псевдокод:

maplock = create_pthread_lock()

общая карта = std::map()

для каждого файла index-split.txt:

spawn-new-thread(myfunction, filename, sharedmap, lock)

dump_map (общая карта)

void myfunction (имя файла, общая карта) {

localmap = std::map<string, size_t>();

file = openfile(filename)

while (file >> word)

    if !localmap.contains(word)
         localmap[word] = 0

    localmap[word]++

acquire(lock)
for key,value in localmap
    if !sharedmap.contains(key)
         sharedmap[key] = 0

    sharedmap[key] += value
release(lock)

}

Извините за синтаксис. В последнее время я много пишу на питоне.

Не C, и немного УЖАСНО, но на это ушло всего 2 минуты:

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq

Зациклить каждую строку с помощью -n
Разбить каждую строку на @F слов с помощью -a
Каждое $_ слово увеличивает хэш %h
Как только будет достигнуто END из file,
sort хэш с частотой $h{$b}<=>$h{$a}
> Если две частоты совпадают, отсортировать по алфавиту $a cmp $b
Вывести частоту $h{$w} и слово $w
Перенаправить результаты в файл 'freq'

Я запустил этот код в текстовом файле размером 3,3 ГБ, содержащем 580 000 000 слов.
Perl 5.22 выполнился за 173 секунды.

В моем входном файле уже были удалены знаки препинания, а заглавные буквы были преобразованы в строчные с помощью этого фрагмента кода:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(время выполнения 144 секунды)

В качестве альтернативы сценарий подсчета слов можно было бы написать на awk:
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq