주기적 데이터를 비교하는 빠른 방법

Question

임의의 유형의 데이터 세트 {A, B, C, D}가 있다고 가정하고이를 다른 데이터 세트와 비교하려고합니다. {A, B, C, D}, {B, C, D, A}, {C, D, A, B} 및 {D, A, B, C} {A, C, B, D} 또는 비슷한 순서로 정렬되지 않은 다른 세트에는 해당되지 않습니다. 이 작업을 수행하는 가장 빠른 방법은 무엇입니까?

그들을 회전에 배열로 저장하고 그런 식으로 비교하는 것은 O (n^2) 작업이므로별로 좋지 않습니다.

첫 번째 직관은 {A, B, C, D, A, B, C}와 같은 집합으로 데이터를 저장 한 다음 하위 집합 O (n) 만 검색하는 것입니다. 이 작업을 더 빨리 완료 할 수 있습니까?

Answer 1

문자열의 최소 회전을 찾는 빠른 알고리즘이 있습니다 (https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation). 따라서 최소 회전을 저장하고 비교할 수 있습니다.

Answer 2

하나의 옵션은 유향 그래프를 사용하는 것입니다. 다음 전환으로 그래프를 설정하십시오.

A -> B 
B -> C 
C -> D 
D -> A 

다른 모든 전환은 오류 상태가됩니다. 따라서 각 구성원이 고유 한 경우 (단어 집합이 인 것을 암시 함), 시작한 동일한 그래프 노드에서 끝나면 멤버십을 결정할 수 있습니다.

검색에 값이 여러 번 나타날 수있는 경우 더 효율적인 상태 및 전환 세트가 필요합니다.

이 방법은 단일 검색을 사전 계산 한 다음 여러 데이터 지점과 일치시키는 경우 유용합니다. 그래프를 끊임없이 재생성해야하는 경우에는 그리 유용하지 않습니다. 또한 상태 테이블이 클 경우 캐시가 비효율적 일 수 있습니다.

Answer 3

글쎄, 만약 당신이 주문에 관심이 있다면 조이드 버그 박사는 주문을 보존하고 쉽게 교체 할 수있는 구조로 데이터를 저장해야합니다. 파이썬에서는 목록이 할 것입니다.

목록의 가장 작은 요소를 찾은 다음 가장 작은 요소가 시작될 때까지 비교할 각 목록을 회전합니다. 참고 : 이것은 일종의 회전이 아니라 회전입니다. 비교를위한 모든 목록이 이렇게 정규화되어 있기 때문에, 어떤 두 사람이 똑같은지를 비교해 보면 똑같이 비교할 수 있습니다.

>>> def rotcomp(lst1, lst2): 
    while min(lst1) != lst1[0]: 
     lst1 = lst1[1:] + [lst1[0]] 
    while min(lst2) != lst2[0]: 
     lst2 = lst2[1:] + [lst2[0]] 
    return lst1 == lst2 

>>> rotcomp(list('ABCD'), list('CDAB')) 
True 
>>> rotcomp(list('ABCD'), list('CDBA')) 
False 
>>> 
>>> rotcomp(list('AABC'), list('ABCA')) 
False 
>>> def rotcomp2(lst1, lst2): 
    return repr(lst1)[1:-1] in repr(lst2 + lst2) 

>>> rotcomp2(list('ABCD'), list('CDAB')) 
True 
>>> rotcomp2(list('ABCD'), list('CDBA')) 
False 
>>> rotcomp2(list('AABC'), list('ABCA')) 
True 
>>> 

새 섹션 : 중복 사용?

입력에 중복이 포함될 수있는 경우 (질문에서 언급 된 가능한 쌍둥이 질문에서), 알고리즘은 하나의 목록이 다른 목록의 하위 목록이 두 번 반복되는지 확인하는 것입니다.

function rotcomp2는 해당 알고리즘과 목록 내용의 repr에 대한 텍스트 비교를 사용합니다.