되풀이 쌍 목록을 생성하는 알고리즘

Question

아래 형식의 텍스트 파일이 주어지면 각 줄은 최대 50 의 목록입니다. 프로그램을 작성하면 적어도 50 개의 서로 다른 목록에 으로 함께 나타나는 이름 쌍 목록이 생성됩니다. 위의 샘플에서

Tyra,Miranda,Naomi,Adriana,Kate,Elle,Heidi 
Daniela,Miranda,Irina,Alessandra,Gisele,Adriana 

는 미란다와 아드리아나 두 번 함께 표시되지만 다른 모든 쌍은 한 번만 나타납니다. "Miranda, Adriana \ n"을 반환해야합니다. 높은 확률로 50 회 이상 나타나는 목록을 사용하여 근사해를 구할 수 있습니다.

나는 다음과 같은 솔루션의 생각 :

1. 가 Map <Pair,Integer> pairToCountMap를 생성, 파일을 읽은 후. 지도를 통해

2. 으로 반복하고,> = 50

이 작업을 수행 할 수있는 더 나은 방법이 있나요 카운트 가진 사람을 인쇄? 파일이 매우 클 수 있으며 근사 솔루션이 무엇을 의미하는지 확신 할 수 없습니다. 모든 링크 또는 리소스를 많이 주시면 감사하겠습니다.

Answer 1

먼저 이름의 길이가 제한되어 있다고 가정하고, 그 이름에 대한 조작은 일정 시간입니다.

답변이 메모리에 맞는 경우 허용되어야합니다. N 개의 줄에 각각 m 개의 줄이 있으면 솔루션을 완료하려면 O(N*m*m)이 필요합니다.

데이터 세트가 메모리에 맞지 않으면 파일에 쌍을 기록하고 병합 정렬을 사용하여 해당 파일을 정렬 한 다음 스캔하여 개수 쌍으로 스캔 할 수 있습니다. 이 실행 시간은 O(N*m*log(N*m))이지만 디스크 액세스 속도에 대한 세부 정보로 인해 실제로 더 빠르게 실행됩니다.

분산 된 클러스터가있는 경우 MapReduce를 사용할 수 있습니다. 마지막 솔루션과 매우 유사하게 실행됩니다.

통계 방법은 각 파일의 빈도와 이름이 다른 줄 수를 찾기 위해 파일 목록을 실행하는 것입니다. 각 행이 무작위로 구성된 이름이라면 통계를 사용하여 임의의 쌍의 공통 이름 사이에 교차 수가 얼마나되는지 추정 할 수 있습니다. 파일의 길이는 대략 선형입니다.

Answer 2

각 이름에 대해 표시 할 줄 번호 목록을 가져올 수 있습니다 (이름을 저장할 수있는 해시 테이블 사용). 그러면 모든 이름 쌍에 대해 해당 줄 색인의 교차 크기를 얻습니다. 두 개의 증가하는 시퀀스가 ​​선형 시간입니다. 이름의 길이가 상수에 의해 제한된다고 가정 해보십시오. 따라서 N 개의 이름과 M 개의 행이있는 경우 목록 작성은 O(MN)이고 마지막 단계는 O(N^2 M)입니다.