☰

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 조합이 5천만 개 이상 생성되었습니다.

목표는 ID가 얼마나 자주 함께 나타나는지 찾는 것입니다. 예를 들어 1001, 1004, 1010이 함께 나타나는 빈도입니다. 또는 1010, 1020, 1030, 1040이 함께 나타나는 빈도 등입니다. 기본적으로 2개의 ID, 3개의 ID, 4개의 ID, 5개의 ID, 6개의 ID의 각 조합이 함께 나타나는 빈도입니다.

Bash 스크립트(실행 중)를 작성했는데 3일 동안 실행했는데 아직 완료되지 않았다는 것을 깨달았습니다.

내 현재 스크립트는 배열 파일(5천만 레코드)의 각 줄을 읽고 있으며, 각 레코드에 대해 배열에 있는 ID 수를 읽은 다음 awk를 사용합니다.

(3개의 ID 조합의 경우):

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

(4개의 ID 조합의 경우):

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

...5천만 개가 넘는 조합을 반복합니다. 초당 약 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결과에 정렬되지 않은 중복 항목이 없습니다.) 예제 숫자에 따르면 초당 30,000개의 행이 처리됩니다.

관련 정보