Обработка огромных текстовых файлов

Question

Проблема: У меня огромный сырой текстовый файл (предположительно 3 гигабайта), мне нужно просмотреть каждое слово в файле и выясните, сколько раз в файле появляется слово.

Мое предлагаемое решение: Разделите огромный файл на несколько файлов, и каждый разделенный файл будет иметь слова в отсортированном виде. Например, все слова, начинающиеся с " a ", будут сохранены в файле " _a.dic ". Поэтому в любое время мы не превысим более 26 файлов.

Проблема в этом подходе:

Я мог использовать потоки для чтения файла, но хотел использовать потоки для чтения определенных частей файла. Например, прочитайте 0-1024 байта с отдельным потоком (по крайней мере, 4-8 потоков на основе числа процессоров существуют в коробке). Это возможно или я сплю?

Есть ли лучший подход?

Примечание: это должно быть чистое решение на основе c ++ или c. Базы данных и т. Д. Не допускаются.

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

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

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

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

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

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

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

Answer 6

Не 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

Answer 7

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

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

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

index = 0

numwords = 0

mysplitfile = openfile (index-split.txt)

while (bigfile >> word)

mysplitfile << word

numwords ++

if (numwords > 5000)

    mysplitfile.close()

    index++

    mysplitfile = openfile(index-split.txt)

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

maplock = create_pthread_lock ()

sharedmap = std :: map ()

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

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

dump_map (sharedmap)

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)

}

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

Answer 8

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

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

Answer 9

Поток

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

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

К примеру:

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

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

Answer 10

C на основе решения?

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