☰

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

など。

（*500,000を超える行があります。）

このリストでは、2つのID、3つのID、4つのID、5つのID、6つのIDのすべての可能な組み合わせの順列を作成しました。 500,000行で、2、3、4、5、6個のIDの組み合わせが5000万個以上生成されました。

目標は、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

...5千万個を超える組み合わせを繰り返します。毎秒約2〜3コンボを実行できますが、簡単な計算で計算すると200日以上かかります。

誰でもより効率的なソリューションを提案できますか？

ベストアンサー1

これにはより多くのプログラミングが必要ですが、ファイルを1行ずつ読み込み、各行の組み合わせを形成し、ハッシュテーブルでその組み合わせの発生回数を計算してこれを行います。

組み合わせを構成する部分は、ライブラリを活用する必要がある部分です。

Perlが救出に来ます。アルゴリズム::組み合わせ組み合わせをリストする既製の機能があります。例を見ると、このようなものを簡単に作成できるようです。これは2つの組み合わせのみを計算するので、自由に改善してください。

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結果に並べ替えられていない重複項目はありません。）例の数値によれば、毎秒30,000行が処理されます。

おすすめ記事