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

Question

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

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

Проблемы в таком подходе есть,

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

Любой лучший подход?

Примечание. Это должно быть чистое решение на основе C++ или c. Запрещены базы данных и т. Д.

Answer 1

Вы должны смотреть на «The Practice of Programming» по Керниган и Пайк, и в частности главы 3.

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

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

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

Answer 2

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

Я думаю, что perl родился именно для этой цели.

Answer 3

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

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

Answer 4

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

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

К примеру:

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

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

Answer 5

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

C++: what regex library should I use?

Answer 6

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

Но, предполагая ваши ограничения, вот что я делаю.

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

индекс = 0

numwords = 0

mysplitfile = OpenFile (индекс-split.txt)

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

mysplitfile << word 

numwords ++ 

if (numwords > 5000) 

    mysplitfile.close() 

    index++ 

    mysplitfile = openfile(index-split.txt) 

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

maplock = create_pthread_lock()

sharedmap = станд :: Карта()

для каждого индекса-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) 

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

Answer 7

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

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

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

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

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

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

Answer 8

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

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

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

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

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

Answer 9

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

Answer 10

не 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
После того, как из file было установлено,
sort хэш частотой $h{$b}<=>$h{$a}
Если две частоты идентичны, сортировать по алфавиту $a cmp $b
печати частота $h{$w} и слово $w
Перенаправление результаты в файл «частота»

Я побежал этот код на 3.3 GB текстовый файл с 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