Задать вопрос
kuraga333
@kuraga333
Программист, аналитик

Как эффективно составить гистограмму слов (big data)?

Есть набор (десятки гигабайт) файлов, в которых приведены слова в нижнем регистре, разделённые пробельными символами.

Ищу эффективный способ составить гистограмму слов. До чего там сейчас техника дошла?

  1. a library (I'm a programmer), one node;
  2. a library (I'm a programmer), many nodes;
  3. a GUI tool, one node;
  4. a GUI tool, many node.
  • Вопрос задан
  • 119 просмотров
Подписаться 1 Средний 8 комментариев
Решения вопроса 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Если реализовывать самостоятельно, то самый эффективный вариант - использовать структуру бор. Правда, тут надо чтобы все файлы влезли в память.

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

Если памяти на компьютере не 64-128гб, и писать что-то не хочется, то можно файл отсортировать и потом подсчитать там повторения за один проход. Это будет чуть медленнее теоретически оптимального решения. rPman уже привел линуксовую команду, которая это делает. Только разбивать на части просто так нельзя, надо чтобы одинаковые строки остались вместе, иначе собирать ответ с нескольких кусков надо будет хитро. Но это и не надо в вашей задаче.

Если же вы что-то распределенное все-таки хотите использовать, то ваша задача - это фактически обучающий пример для всяких map-reduce фреймворков типа hadoop. Но там придется повозиться с установкой и настройкой этого добра и код с примера скопировать.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
@rPman
wc
утилита командной строки, часть coreutils любого linux - в один поток считает количество строк/слов/символов в текстовых файлах


разделение слов в файле с помощью xargs, сортировка sort, подсчет уникальных слов uniq -c
cat file | xargs -n 1 | sort | uniq -c

если файлы упакованы, распаковка запускается параллельно с помощью потоков (команда распаковки в stdout | wc )

parallel (одноименный пакет linux) - позволяет максимально просто запускать параллельно несколько процессов (список команд указываются в stdin, по мере необходимости они читаются и запускаются)

На нескольких нодах запускай команду сам.

Итого, любым языком программирования подготавливаешь список команд, обрабатывающих текстовые данные по частям (с учетом их размещения на разных носителях, так как обычно именно они часто являются самым узким местом тут), скармливаешь его parallel и так же своими утилитами читаешь логи на предмет ошибок и результатов.

типа такого:
for a in *.zst;do echo "zstd -d --stdout $a |(printf \"%s\\t\" $a;wc)";done | parallel -j 5

данный код выводит по строчкам имя архива zstd со сжатым текстом и 3 числа, количество строк, слов и символов, параллельно запуская распаковку и подсчет символов в 5 потоков, утилизируя 12 ядер (12-gen intel) по максимуму посчитав 38гб несжатых (4.4гб сжатых) коротких json-файлов (построчно записаны в кучу файлов) за 121сек (узкое место тут распаковка)
Ответ написан
mayton2019
@mayton2019
Bigdata Engineer
Это стандартный туториал из книжки Изучаем Apache Spark. Там за 5 строчек кода ведется подсчет частоты слов.
Ответ написан
Комментировать
2ord
@2ord
Пришел в голову такой вариант:
В текстовом потоке берём каждый токен и делаем инкремент количества, и т.д.
Затем сортируем результаты - здесь вопрос какую структуру данных выбрать, чтобы сортировать находу.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы