Подсчет целочисленной частоты через трубу - PullRequest
Новая
       76

Подсчет целочисленной частоты через трубу

0 голосов
/ 08 мая 2020

Описание

У меня есть for l oop in bash с 10 ^ 4 итерациями всего. На каждой итерации из канала создается список из примерно 10 ^ 7 чисел, каждое из которых представляет собой целое число от 1 до 10 ^ 8. Я хочу отслеживать, сколько раз появлялось каждое целое число. Идеальным выходом был бы файл .txt с 10 ^ 8 строками, каждая строка которого содержит счетчик для целого числа, соответствующего номеру строки.

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

Воспроизводимый пример:

образец.R 

args = commandArgs(trailingOnly=TRUE)
n_samples = as.numeric(args[1])
n_max = as.numeric(args[2])
v = as.character(sample(1:n_max, n_samples))
writeLines(v)

для l oop: 

for i in {1..n_loops}
do
    Rscript sample.R n_samples n_max | "COLLECT AND INCREMENT HERE"
done

, где в моем случае n_loops = 10 ^ 4, n_samples = 10 ^ 7, n_max = 10 ^ 8.

1 Ответ

0 голосов
/ 08 мая 2020

Простой подход

Перед преждевременной оптимизацией попробуйте сначала обычный подход с sort | uniq -c - если это достаточно быстро, у вас будет меньше работы и более короткий сценарий. Чтобы ускорить процесс без особых хлопот, установите память, используя -S, и используйте простейшую кодировку текста LC_ALL=C. 

for i in {1..10000}; do
    Rscript sample.R n_samples n_max
done | LC_ALL=C sort -nS40% | LC_ALL=C uniq -c

На выходе будут строки вида number_of_matches integer_from_the_output. Будут перечислены только целые числа, которые встречались хотя бы один раз.

Чтобы преобразовать этот формат (неэффективно) в ваш предпочтительный формат с 10 8 строками, каждая из которых содержит счет для целого числа, соответствующего строке number замените часть ... | sort | uniq -c следующей командой: 

... | cat - <(seq 100''000''000) | LC_ALL=C sort -nS40% | LC_ALL=C uniq -c | awk '{$1--;$2=""}1'

Это предполагает, что все сгенерированные целые числа находятся в диапазоне от 1 до 10 8 включительно. Результат искажается, если какие-либо другие значения появляются более одного раза.

Ha sh Map

Если вы хотите go с картой ha sh, простейшей реализацией, вероятно, будет быть скриптом awk: 

for i in {1..10000}; do
    Rscript sample.R n_samples n_max
done | awk '{a[$0]++} END {for (ln=1; ln<=100000000; ln++) print int(a[ln])}'

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

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

10 4 итераций * 10 7 вхождений / итераций = 10 4 + 7 вхождений = 10 11 вхождений

... этого целого числа. Чтобы сохранить максимальное количество 10 11 , вам понадобится не менее 37 бит> log 2 (10 11 ) бит.
GNU awk 5 на 64 -битная система, кажется, обрабатывает числа такого размера.

Более быстрый подход

Подсчет вхождений в структуру данных - хорошая идея. Однако карта ha sh является излишней, поскольку в качестве вывода у вас есть «только» 10 8 возможные значения . Следовательно, вы можете использовать массив с 10 8 записями 64-битных счетчиков. В массиве будет использоваться ...

64 бит * 10 8 = 8 байт * 10 2 + 6 = 800 МБ

... памяти. Я считаю, что 800 МБ должно быть бесплатно даже на старых ПК и ноутбуках старше 10 лет go.

Для реализации этого подхода используйте «нормальный» язык программирования по вашему выбору. Bash не подходит для этой работы. Вы можете использовать bash, чтобы передать вывод l oop в вашу программу. Кроме того, вы можете выполнить for l oop прямо в своей программе.

...