☰

查找 ID 组的更好解决方案（排列/组合）

tag-icon • tag-icon bash shell-script grep math permutations
查找 ID 组的更好解决方案（排列/组合）

我对这个问题的目标是找到一个更有效的解决方案来完成任务。

我有一个包含 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

ETC。

（*有超过 500K 行。）

根据这个列表，我创建了 2 个 ID、3 个 ID、4 个 ID、5 个 ID 和 6 个 ID 的所有可能组合的排列。从 50 万行中，创建了超过 5000 万个 2、3、4、5 和 6 个 ID 的组合。

目标是找出 ID 一起出现的频率。例如，1001、1004 和 1010 一起出现的频率。或者1010、1020、1030、1040一起出现的频率等等。基本上是2个ID、3个ID、4个ID、5个ID和6个ID的每个组合一起出现的频率。

我写了一个 Bash 脚本（正在运行），但它已经运行了 3 天，我意识到还没有完成。

我当前的脚本正在读取排列文件中的每一行（5000 万条记录），对于每条记录，它读取排列中有多少个 ID，然后使用 awk：

（对于 3 ID 组合）：

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

（对于 4 ID 组合）：

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

...并迭代 5000 万个组合。它每秒大约可以进行 2-3 次连击，但简单的数学计算会告诉我，这应该需要 200 多天的时间。

谁能提出更有效的解决方案？

答案1

这更多地涉及到编程，但我会通过逐行读取文件、形成每行上存在的组合、计算它们在哈希表中的出现来实现这一点。

关于形成组合的部分是您需要使用库的部分。

Perl 来救援，算法::组合学有一个现成的功能用于列出组合。根据示例，类似的事情似乎很容易制作。这仅计算两个的组合，请随意改进它。

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 行的数据。

相关内容