Java의 여러 배열에서 해당 값을 비교하는 더 나은 방법

Question

정렬되어있는 M 목록을 포함하는 ArraysList가 있습니다. Arraylist의 각 목록은 같은 크기 N입니다. 이제 각 목록의 첫 번째 (N-1) 값을 다른 사람과 비교하고 싶습니다. 동일한 첫 번째 값이 (N-1) 인 목록을 찾고 싶습니다. 직관적으로 두 개의 for-loop로 수행 할 수 있지만 복잡도는 M*N*N 일 수 있습니다. 이 작업을 수행하는 데 더 좋은 알고리즘이 있는지 궁금합니다. 그런데 M은 매우 큰 숫자 일 수 있고 N은 작은 숫자가 될 수 있습니다.

죄송합니다. 명확하지 않을 수 있습니다. 나는 최종 결과물이 같은 첫 번째가있는 목록의 쌍인 (N-1) 값을 원한다.

Answer 1

좋은 해싱 알고리즘을 사용하여 각 행의 N-1 항목의 해시 코드를 계산합니다. 행을 해시 코드로 구성하고 해시 코드가 일치 할 때만 전체 비교를 수행하십시오.

Answer 2

목록 목록을 정렬하십시오.

정렬은 O(N M LOG M)입니다 (비교가 O(N)라고 가정).

기수 정렬 방식으로 수행하는 경우 실제로는 O(N * M) 또는 심지어 O(M LOG M)의 줄에 더 많이 있어야합니다 (목록이 동일하지 않은 경우).

그런 다음 동일한 접두사가있는 목록은이 목록에서 후속이어야합니다.

APRIORI를 다시 구현하려는 경우 : 은 후보 항목 집합의 정렬 된 목록을 유지합니다. 이것은 바로 Apriori-Gen이 다음 라운드 후보자를 구축하는 데 필요한 것입니다. 정렬 된 트리로 유지하는 것은 매우 정교합니다. 이는 항목 집합 수를 계산하기 위해 데이터베이스를 검색 할 때도 빠르기 때문입니다.