Melhor solução para encontrar grupos de IDs (permutações / combinações)

Question

Meu objetivo para essa pergunta é encontrar uma solução mais eficiente para realizar uma tarefa.

Eu tenho um arquivo contendo linhas de IDs, por exemplo:

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 

(* Existem mais de 500 mil linhas.)

Nesta lista, criei permutações de todas as combinações possíveis de 2 IDs, 3 IDs, 4 IDs, 5 IDs e 6 IDs. Das 500 mil linhas, mais de 50 milhões de combinações de 2, 3, 4, 5 e 6 IDs foram criadas.

O objetivo é descobrir com que frequência os IDs ocorrem juntos. Por exemplo, quantas vezes 1001, 1004 e 1010 ocorrem juntos. Ou quantas vezes 1010, 1020, 1030, 1040 ocorrem juntos, etc. Basicamente, com que frequência cada combinação de 2 IDs, 3 IDs, 4 IDs, 5 IDs e 6 IDs ocorrem juntos.

Eu escrevi um script Bash (que está funcionando), mas ele está funcionando há 3 dias e eu percebi que não é perto de ser feito.

Meu script atual está lendo cada linha no meu arquivo de permutações (50 milhões de registros) e para cada registro está lendo quantos IDs estão na permutação e, em seguida, usando o awk:

(para um combo de 3 IDs):

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

(para um combo de 4 ID):

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

... e iterando pelas 50 milhões de combinações. Ele está trabalhando em cerca de 2-3 combos por segundo, mas a matemática simples vai me dizer que deve demorar mais de 200 dias.

Alguém pode sugerir uma solução mais eficiente?

    

Answer 1

Isso vai mais para programação, mas eu abordaria isso lendo o arquivo linha por linha, formando as combinações que estão presentes em cada linha, contando suas aparências em uma tabela de hash.

A parte sobre a formação das combinações é algo que você vai querer usar uma biblioteca para.

Perl para o resgate, Algorithm :: Combinatorics tem um ready-made função para listar as combinações. Com base nos exemplos, algo assim parece muito fácil de fazer. Isso só conta combinações de dois, sinta-se livre para melhorá-lo.

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

Eu assumi que a ordem dos números em cada linha não importava, então eu classifiquei a entrada. (Eu acho que combinations mantém a ordem dos elementos, então o resultado não tem duplicatas não classificadas).   Com os números de exemplo, obtive algo como 30000 linhas processadas por segundo.