Лучшее решение для поиска групп идентификаторов (перестановки / комбинации)

Моя цель в этом вопросе – найти более эффективное решение для выполнения задачи.

У меня есть файл, содержащий строки ID, например:

1001 1004 1005 1010 1006 1020 1002 1002 1005 1006 1001 1010 1020 1043 1009 1016 1011 1012 1013 1010 1020 1030 1050 1004 1014 1001 1008 1004 1021 1022 1010 1001 1004 1010 

и т.п.

(* Есть более 500 тыс. Строк).

Из этого списка я создал перестановки всех возможных комбинаций из 2 идентификаторов, 3 идентификаторов, 4 идентификаторов, 5 идентификаторов и 6 идентификаторов. Из строк 500K было создано более 50 миллионов комбинаций из 2, 3, 4, 5 и 6 идентификаторов.

Цель состоит в том, чтобы выяснить, как часто встречаются идентификаторы. Например, как часто 1001, 1004 и 1010 встречаются вместе. Или как часто 1010, 1020, 1030, 1040 происходят вместе и т. Д. В принципе, как часто каждая комбинация из 2 идентификаторов, 3 идентификаторов, 4 идентификаторов, 5 идентификаторов и 6 идентификаторов встречаются вместе.

Я написал сценарий Bash (который работает), но он работает в течение 3 дней, и я понял, что рядом с этим не делается.

Мой текущий скрипт читает каждую строку в моем файле подстановок (50 миллионов записей), и для каждой записи он считывает количество идентификаторов в перестановке и затем использует awk:

(для комбинации 3 ID):

 awk '/'$id1'/ && /'$id2'/ && /'$id3'/' $filename 

(для компиляции 4 ID):

 awk '/'$id1'/ && /'$id2'/ && /'$id3'/' && /'$id4'/' $filename 

… и итерации через 50 миллионов комбинаций. Он работает примерно на 2-3 комбо в секунду, но простая математика скажет мне, что это займет 200 дней.

Может ли кто-нибудь предложить более эффективное решение?

One Solution collect form web for “Лучшее решение для поиска групп идентификаторов (перестановки / комбинации)”

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

Часть о формировании комбинаций – это то, что вы хотите использовать для библиотеки.

Perl для спасения, Алгоритм :: Combinatorics имеет готовую функцию для перечисления комбинаций. На основе примеров, что-то вроде этого кажется довольно легко сделать. Это только считается комбинацией двух, не стесняйтесь его улучшать.

 perl -MAlgorithm::Combinatorics=combinations -lane ' $i = combinations([sort @F], 2); while ($x = $i->next) { $count{join "-", @$x}++ } END {printf "%s: %d\n", $_, $count{$_} foreach keys %count } ' < ids > counts | sort -nk2 | tail -3 1010-1020: 3 1001-1010: 4 1004-1010: 4 

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

  • Извлечь текст между тремя одинарными кавычками
  • добавить имя файла в текст в углу файла изображения
  • Bash, как запустить некоторые фоновые процессы, но ждать других?
  • Имея аргументы $ line, переданные rsync при использовании опции --protect-args
  • Составить строку IP-адресов с помощью командной строки bash
  • как заменить IP-адрес на удаленном хосте, используя
  • Bash regex, строка соответствия из двух строк
  • Передача нескольких аргументов с пробелами через скрипт в ssh
  • Искать каталоги для многострочной строки
  • Производительность скрипта Bash
  • автоматизация конфигурации CentOS 7 с использованием сценариев оболочки
  • Rc.local не работает правильно команд
  • Linux и Unix - лучшая ОС в мире.