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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

Во-первых, я почти уверен, что 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 ) Используйте общую структуру данных карты и потоки pthread для создания новых потоков для чтения каждого из подфайлов. Опять же, псевдокод:

maplock = create_pthread_lock ()

sharedmap = std :: map ()

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

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

dump_map (sharedmap)

void myfunction (filename, sharedmap) {

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.

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