alexgor123Есть большой текстовый файл (~3 ГБ). Требуется подсчитать количество вхождений каждого слова в файл с использованием threads. Не подскажите с чего начать? Сколько потоков нужно создавать?
Как это обычно случается. Задача не описана польностью.
Потому что в такой постановке и одного потока достаточно.
Но ведь есть какие-то ещё требования, о которых вы умалчиваете. Например, чтобы парсинг укладывался по времени в сутки. Или часов 8.
Забавно, у нас недавно была похожая задача. Сам не делал, но знаю постановку и размышлял над тем как бы сделал я.
Правда у нас было 4Гб файл в zip архиве.
Итак. Каките требования ещё есть?

Количество потоков должно быть таким, чтобы CPU был всё время загружен на 100%. Это вычисляется из количества ядер. И соотношении времени прстоя на IO операциях к времени обработки на CPU.

Самое главное в этой задаче это реализовать масштабируемость по потокам. Т.е. если задача на 2х ядрах обсчитывается 12 часов, то чтобы на 4х было 6, а на 8-ми - три, без переписывания проекта.
Таким образом, можно, например, арендовать в облаке ненадолго многоядерный сервер и обсчитать файл в кратчайшее время.

Второе на что стоит обратить внимание это масштабирумость на физические устройства. Т.е. почему бы не побить файл на два и не обсчитать отдельно на 2х компах? Если у вас, например, небольшая software команда, то запустив файл на 5-10 компах ночью, можно обсчитать его за пару часов и меньше. Потом объединить результаты. (читать про Map-Reduce)

Третье это минимизация IO как самой долгой операции. 3Гб это на столько мало, что на многих машинах можно полностью загрузить в RAM до обработки.

И только в последнюю очередь стоит уже посмотреть на эффективность поиска и подсчета отдельных слов. Даже если эта задача решена не оптимально, зачастую будет дешевле купить\арендовать второй комп, и обсчитать в 2 раза быстрее, чем оптимизировать код. Конечно здесь нужно быть внимательным, чтобы не убить перформанс на корню. Но и оптимизировать очень усилино, смысла нет, если оно нормально масштабируется.

MasterZivЗадача состоит из:
- Чтения потокового файла — строго последовательный процесс.
- парсинга на слова
- похода к хэш-таблице за счетчиком слов.
Все строго последовательно, нет нигде провода параллелить.
Кстати да. Здесь обработка на столько простая что и решение в лоб может быть достаточно быстрым. У нас задача осложнялась тем что слова нельзя было выделить в тексте. Они не обособлены пробелами или знаками припинания.

ТимоНДаже в теории это невозможно ведь?
Почему? Если IO свести у нулю, а ядра загрузить независимыми задчами, то будет примерно так и масштабироваться.
А этой задаче ядрам никак не нужно обмениваться данными и работают они могут с независимыми участками памяти.
Конечно же будут потери на задачи ОС и т.п. Но в целом это к тому к чему можно стремиться в этой задаче.

MasterZivА как тогда слова обозначались?

Никак, их надо было ещё найти. У нас была задача поиска слов, а не статистики.

MasterZivНу и ты как бы модифицируешь исходную задачу.
Ну, да. Это я так. Лирическо отступление. У автора всё на много проще. Можно решить в лоб и потом тупо бить файл.

LeonidvКлассическая задача на map/reduce. Начать с его изучения и реализации.
Не обязательно. Если ресурсов достаточно и процессинг не такой сложный, то можно Fork/Join обойтись:
http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html

ТимоН Закон Амдала
Дык в указаной задаче ɑ стремится к единице:
1) Количество процессоров 4-8-16 достаточно мало, чтобы каждый из них независимо мог обрабатывать свой кусок входного файла.
2) Время обработки части файла несоизмеримо больше, чем суммирование результатов от каждого ядра. Пусть там даже словарь на 300К слов, выпонить 3М сложений это ничто на фоне чтения и сканирования 3Гб файла.

oneHalfЯ тут не совсем спец в этом, но может проще затянуть все в БД - все слова в один столбик одной таблицы, причем существуют спец. утилитки, (например для mssql - csv bulk insert) или использовать встраиваемые движки бд (derby, и т.д.) в программе. Тогда уже весь гемор по подсчету всяких вариаций всяких вхождений ляжет на плечи бд.
Можно делать кучу разных допущений и оптимизаций, если знать структуру входного файла. Но автор о ней умалчивает.
Но файл в 3Гб может содержать сотни миллионов слов. MySQL потом усрется count-ы считать по такой таблице.
Да и сам экспорт в базу с построением индексов может занять часы, если база не в памяти развернута.
Поэтому смысла особого нет, мне кажется.
Вариант описаный MasterZiv при нужном подходе может быть даже и в 6 часов уложится в один поток.

maytonТут слабым местом будет диск IMHO. По сути это вычитка файла.
Нет не будет. Сколько занимает времени вычитать 3Гб c HDD? Скорость современных винтов от 30Мб\с (какая-нибудь зеленая модель на 5400RPM). Т.е. 100 секунд на чтение файла. :) В худшем случае это минуты, но не часы.

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