Python에서 두 목록이 순환적으로 동일한지 확인하는 방법
예를 들어, 다음과 같은 목록이 있습니다.
a[0] = [1, 1, 1, 0, 0]
a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]
# and so on
그것들은 다른 것처럼 보이지만, 만약 그것이 시작과 끝이 연결되어 있다고 가정한다면, 그것들은 순환적으로 같습니다.
문제는 제가 가지고 있는 각 목록의 길이가 55이고 3개의 1과 52개의 0만 포함되어 있다는 것입니다.순환 조건이 없으면 26,235개(55개 선택 3)의 목록이 있습니다.그러나 '원형'이라는 조건이 존재하는 경우 순환적으로 동일한 목록이 매우 많습니다.
현재 저는 다음과 같은 방법으로 순환 신원을 확인하고 있습니다.
def is_dup(a, b):
for i in range(len(a)):
if a == list(numpy.roll(b, i)): # shift b circularly by i
return True
return False
이 기능은 최악의 경우 55번의 주기적인 시프트 작업이 필요합니다.그리고 26,235개의 목록을 서로 비교해야 합니다.간단히 말해서 55 * 26,235 * (26,235 - 1) / 2 = 18,926,847,225 계산이 필요합니다.거의 20기가 정도 됩니다!
더 적은 계산으로 그것을 할 수 있는 좋은 방법이 있습니까?또는 순환을 지원하는 데이터 유형이 있습니까?
우선, 이 작업은 다음 시간에 수행할 수 있습니다.O(n) 당신은 목록을 한다면 당신은 수 .[1, 2, 3]) 될 것입니다.[1, 2, 3, 1, 2, 3]그러면 당신의 새로운 목록은 확실히 모든 가능한 순환 목록을 보유할 것입니다.
따라서 검색 중인 목록이 시작 목록의 2배 안에 있는지 확인하기만 하면 됩니다.python에서는 다음과 같은 방법으로 이를 달성할 수 있습니다(길이가 같다고 가정).
list1 = [1, 1, 1, 0, 0]
list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))
라인에 몇 가지 : 나의한라대몇한가설명지인에:list * 2합니다. 자과목결것입니다합할록을신.map(str, [1, 2])모든 숫자를 문자열로 변환합니다.' '.join() 어이변환니다합를레를 변환합니다.['1', '2', '111'] 줄로'1 2 111'.
일부 사람들이 코멘트에서 지적한 바와 같이, 하나의 라이너는 잠재적으로 몇 가지 잘못된 긍정을 줄 수 있으므로 가능한 모든 에지 사례를 포함할 수 있습니다.
def isCircular(arr1, arr2):
if len(arr1) != len(arr2):
return False
str1 = ' '.join(map(str, arr1))
str2 = ' '.join(map(str, arr2))
if len(str1) != len(str2):
return False
return str1 in str2 + ' ' + str2
추신1 시간 복잡성에 대해 말할 때, 주목할 가치가 있습니다.O(n)하위 문자열을 찾을 수 있는 경우에 달성됩니다.O(n)시간. 항상 그렇지는 않으며 해당 언어의 구현에 따라 다릅니다(예를 들어 선형 시간 KMP로 수행될 수도 있음).
현 작동을 두려워하는 사람들을 위한 추신2는 이러한 사실 때문에 답이 좋지 않다고 생각합니다.중요한 것은 복잡성과 속도입니다.이 알고리즘은 잠재적으로 실행됩니다.O(n)과 간과시O(n)그것을 그 어떤 것보다 훨씬 더 좋게 만드는 공간.O(n^2)例의영 보기하면 첫 번째 됩니다).이를 직접 확인하려면 작은 벤치마크를 실행할 수 있습니다(랜덤 리스트를 작성하면 첫 번째 요소가 팝업되고 끝에 추가되므로 순환 리스트가 생성됩니다).당신은 당신 자신의 조작을 자유롭게 할 수 있습니다.)
from random import random
bigList = [int(1000 * random()) for i in xrange(10**6)]
bigList2 = bigList[:]
bigList2.append(bigList2.pop(0))
# then test how much time will it take to come up with an answer
from datetime import datetime
startTime = datetime.now()
print isCircular(bigList, bigList2)
print datetime.now() - startTime # please fill free to use timeit, but it will give similar results
내 기계에서 0.3초.얼마 안 남았어요.을 이제이비보십오시해교을과 .O(n^2)ㅠㅠㅠㅠ) 있습니다.비교하는 동안 미국에서 호주까지 여행할 수 있습니다(아마도 유람선을 이용할 것입니다).
요청한 언어로 답변할 수 있는 Python에 대한 지식이 부족하지만 C/C++에서는 질문의 매개 변수를 고려할 때 0과 1을 비트로 변환하여 unint64_t의 최하위 비트에 푸시합니다.이를 통해 한 번에 55비트를 모두 비교할 수 있습니다(1클럭).
엄청나게 빠르며 전체가 온칩 캐시(209,880바이트)에 들어갑니다.55개의 목록 멤버를 모두 동시에 이동할 수 있는 하드웨어 지원은 CPU의 레지스터에서만 사용할 수 있습니다.55명 전원을 동시에 비교하는 것도 마찬가지입니다.이를 통해 문제를 소프트웨어 솔루션에 1 대 1 매핑할 수 있습니다.(및 SIMD/SSE 256비트 레지스터 사용, 필요한 경우 최대 256개 멤버 사용) 따라서 코드는 독자에게 즉시 명백해집니다.
Python에서 이 기능을 구현할 수도 있지만, 저는 이 기능이 가능한지 또는 성능이 어떤지 알 수 없을 정도로 잘 알지 못합니다.
그 위에서 자고 나니 몇 가지가 분명해졌고, 모든 것이 좋아졌습니다.
1.) 비트를 사용하여 순환 연결된 목록을 회전하는 것은 매우 쉬워서 달리의 매우 영리한 트릭이 필요하지 않습니다.64비트 레지스터 내부의 표준 비트 이동은 비트옵스 대신 산술을 사용하여 매우 간단하게 회전을 수행하고 파이썬을 더욱 친숙하게 만들 수 있습니다.
2.) 비트 이동은 2로 나누기를 사용하여 쉽게 수행할 수 있습니다.
3.) 목록 끝에 0 또는 1이 있는지 확인하는 것은 모듈로 2로 쉽게 할 수 있습니다.
4.) 꼬리에서 목록의 선두로 0을 "이동"하는 것은 2로 나누어 수행할 수 있습니다.이것은 만약 0이 실제로 움직인다면 55번째 비트가 거짓이 될 것이기 때문입니다. 이것은 이미 완전히 아무것도 하지 않았기 때문입니다.
5.) 꼬리에서 목록의 선두로 1을 "이동"하는 것은 2로 나누고 55번째 비트를 true로 표시하고 나머지를 모두 false로 표시하여 생성된 값인 18,014,398,509,481,984를 더하면 됩니다.
6.) 임의의 회전 후 앵커와 구성된 unt64_t의 비교가 TRUE이면 중단하고 TRUE를 반환합니다.
반복적으로 변환할 필요가 없도록 목록의 전체 배열을 바로 앞에 있는 uint64_ts 배열로 변환할 것입니다.
코드를 최적화하기 위해 몇 시간을 보낸 후 어셈블리 언어를 공부하여 런타임을 20% 줄일 수 있었습니다.OS와 MSVC 컴파일러가 어제도 한낮에 업데이트되었다는 것을 덧붙여야 합니다.어떤 이유에서든 C 컴파일러가 생성한 코드의 품질은 업데이트 이후에 극적으로 향상되었습니다(2014년 11월 15일).런타임은 현재 ~ 70개의 클럭, 테스트 링의 55번 모두와 앵커 링을 구성하고 비교하는 데 17나노초가 소요되며 모든 링의 NxN은 12.5초 만에 완료됩니다.
이 코드는 너무 빡빡해서 4개의 레지스터를 제외한 모든 레지스터가 99%의 시간 동안 아무것도 하지 않고 앉아 있습니다.어셈블리 언어가 C 코드와 거의 일치합니다.매우 읽기 쉽고 이해하기 쉽습니다.누군가가 그것을 스스로 가르치고 있다면 훌륭한 조립 프로젝트입니다.
하드웨어는 Hazwell i7, MSVC 64비트, 전체 최적화입니다.
#include "stdafx.h"
#include "stdafx.h"
#include <string>
#include <memory>
#include <stdio.h>
#include <time.h>
const uint8_t LIST_LENGTH = 55; // uint_8 supports full witdth of SIMD and AVX2
// max left shifts is 32, so must use right shifts to create head_bit
const uint64_t head_bit = (0x8000000000000000 >> (64 - LIST_LENGTH));
const uint64_t CPU_FREQ = 3840000000; // turbo-mode clock freq of my i7 chip
const uint64_t LOOP_KNT = 688275225; // 26235^2 // 1000000000;
// ----------------------------------------------------------------------------
__inline uint8_t is_circular_identical(const uint64_t anchor_ring, uint64_t test_ring)
{
// By trial and error, try to synch 2 circular lists by holding one constant
// and turning the other 0 to LIST_LENGTH positions. Return compare count.
// Return the number of tries which aligned the circularly identical rings,
// where any non-zero value is treated as a bool TRUE. Return a zero/FALSE,
// if all tries failed to find a sequence match.
// If anchor_ring and test_ring are equal to start with, return one.
for (uint8_t i = LIST_LENGTH; i; i--)
{
// This function could be made bool, returning TRUE or FALSE, but
// as a debugging tool, knowing the try_knt that got a match is nice.
if (anchor_ring == test_ring) { // test all 55 list members simultaneously
return (LIST_LENGTH +1) - i;
}
if (test_ring % 2) { // ring's tail is 1 ?
test_ring /= 2; // right-shift 1 bit
// if the ring tail was 1, set head to 1 to simulate wrapping
test_ring += head_bit;
} else { // ring's tail must be 0
test_ring /= 2; // right-shift 1 bit
// if the ring tail was 0, doing nothing leaves head a 0
}
}
// if we got here, they can't be circularly identical
return 0;
}
// ----------------------------------------------------------------------------
int main(void) {
time_t start = clock();
uint64_t anchor, test_ring, i, milliseconds;
uint8_t try_knt;
anchor = 31525197391593472; // bits 55,54,53 set true, all others false
// Anchor right-shifted LIST_LENGTH/2 represents the average search turns
test_ring = anchor >> (1 + (LIST_LENGTH / 2)); // 117440512;
printf("\n\nRunning benchmarks for %llu loops.", LOOP_KNT);
start = clock();
for (i = LOOP_KNT; i; i--) {
try_knt = is_circular_identical(anchor, test_ring);
// The shifting of test_ring below is a test fixture to prevent the
// optimizer from optimizing the loop away and returning instantly
if (i % 2) {
test_ring /= 2;
} else {
test_ring *= 2;
}
}
milliseconds = (uint64_t)(clock() - start);
printf("\nET for is_circular_identical was %f milliseconds."
"\n\tLast try_knt was %u for test_ring list %llu",
(double)milliseconds, try_knt, test_ring);
printf("\nConsuming %7.1f clocks per list.\n",
(double)((milliseconds * (CPU_FREQ / 1000)) / (uint64_t)LOOP_KNT));
getchar();
return 0;
}
행간을 읽어보면 3개의 1과 52개의 0을 가진 문자열의 각 원형 등가 클래스를 하나씩 열거하려고 하는 것처럼 들립니다.range(55)).에서 )의 , 순에서이, 환동은현s타고k이해력에 의해 주어집니다.set((i + k) % 55 for i in s)클래스의 사전 작성 최소 대표자는 항상 위치 0을 포함합니다.양식 세트가 지정된 경우{0, i, j}와 함께0 < i < j은 반서최위다한은후들보자른에소입니다.{0, j - i, 55 - i}그리고.{0, 55 - j, 55 + i - j}그러므로, 우리는 필요합니다.(i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))원본이 최소가 되도록.여기 몇 가지 열거 코드가 있습니다.
def makereps():
reps = []
for i in range(1, 55 - 1):
for j in range(i + 1, 55):
if (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j)):
reps.append('1' + '0' * (i - 1) + '1' + '0' * (j - i - 1) + '1' + '0' * (55 - j - 1))
return reps
첫 번째 배열을 반복한 다음 Z 알고리즘(O(n) 시간)을 사용하여 첫 번째 배열 내부의 두 번째 배열을 찾습니다.
(참고: 첫 번째 어레이를 물리적으로 복사할 필요는 없습니다.매칭 중에는 그냥 랩으로 감으시면 됩니다.)
Z 알고리즘의 좋은 점은 KMP, BM 등에 비해 매우 간단하다는 것입니다.
하지만, 만약 당신이 야망을 느낀다면, 당신은 선형 시간과 일정한 공간에서 스트링 매칭을 할 수 있습니다.strstr예를 들어, 이렇게 합니다.하지만 그것을 시행하는 것은 더 고통스러울 것입니다.
Salvador Dali의 매우 현명한 솔루션에 이어, 이를 처리하는 가장 좋은 방법은 모든 요소의 길이와 두 목록의 길이가 동일한지 확인하는 것입니다.
def is_circular_equal(lst1, lst2):
if len(lst1) != len(lst2):
return False
lst1, lst2 = map(str, lst1), map(str, lst2)
len_longest_element = max(map(len, lst1))
template = "{{:{}}}".format(len_longest_element)
circ_lst = " ".join([template.format(el) for el in lst1]) * 2
return " ".join([template.format(el) for el in lst2]) in circ_lst
이것이 살바도르 달리의 대답에서 Ashwini Chaudhary가 추천한 정규식 솔루션보다 빠르거나 느리는지에 대한 단서는 없습니다.
import re
def is_circular_equal(lst1, lst2):
if len(lst2) != len(lst2):
return False
return bool(re.search(r"\b{}\b".format(' '.join(map(str, lst2))),
' '.join(map(str, lst1)) * 2))
목록을 쉽게 비교할 수 있는 일종의 표준 형식으로 변환하기 위해 목록을 초기 단계에서 검토하는 것이 가치가 있을 수 있습니다.
당신은 순환 고유 리스트 세트를 얻으려고 노력하고 있습니까?그렇다면 튜플로 변환한 후 세트로 던질 수 있습니다.
def normalise(lst):
# Pick the 'maximum' out of all cyclic options
return max([lst[i:]+lst[:i] for i in range(len(lst))])
a_normalised = map(normalise,a)
a_tuples = map(tuple,a_normalised)
a_unique = set(a_tuples)
David Eisenstat에게 그의 v.유사한 답변을 발견하지 못한 것에 대해 사과드립니다.
다음과 같이 하나의 목록을 롤할 수 있습니다.
list1, list2 = [0,1,1,1,0,0,1,0], [1,0,0,1,0,0,1,1]
str_list1="".join(map(str,list1))
str_list2="".join(map(str,list2))
def rotate(string_to_rotate, result=[]):
result.append(string_to_rotate)
for i in xrange(1,len(string_to_rotate)):
result.append(result[-1][1:]+result[-1][0])
return result
for x in rotate(str_list1):
if cmp(x,str_list2)==0:
print "lists are rotationally identical"
break
먼저 모든 목록 요소(필요한 경우 복사본)를 어휘적으로 가장 큰 회전 버전으로 변환합니다.
그런 다음 결과 목록을 정렬하고(인덱스를 원래 목록 위치로 유지) 정렬된 목록을 통합하여 필요에 따라 원래 목록의 모든 중복 항목을 표시합니다.
@SalvadorDali가 b+b의 a-length size slice에서 a와 일치하는 항목을 찾는 것에 대한 관찰을 바탕으로, 여기 목록 작업만 사용하는 솔루션이 있습니다.
def rollmatch(a,b):
bb=b*2
return any(not any(ax^bbx for ax,bbx in zip(a,bb[i:])) for i in range(len(a)))
l1 = [1,0,0,1]
l2 = [1,1,0,0]
l3 = [1,0,1,0]
rollmatch(l1,l2) # True
rollmatch(l1,l3) # False
두 번째 접근법: [계속]
완전하고 독립적인 대답은 아니지만, 비교를 줄임으로써 최적화하는 주제에 대해, 저도 정규화된 표현을 생각하고 있었습니다.
즉, 입력 알파벳이 {0, 1}인 경우 허용되는 순열 수를 크게 줄일 수 있습니다.첫 번째 목록을 (의사-) 정규화된 형식으로 회전합니다(질문의 분포를 고려할 때, 1비트 중 하나가 왼쪽 끝에 있고 0비트 중 하나가 오른쪽 끝에 있는 것을 선택합니다).이제 각 비교 전에 동일한 정렬 패턴을 가진 가능한 위치를 통해 다른 목록을 차례로 회전합니다.
예를 들어, 총 4개의 1비트가 있는 경우 이 정렬에는 최대 4개의 순열이 있을 수 있으며, 인접한 1비트의 클러스터가 있는 경우 이러한 클러스터의 각 추가 비트는 위치의 양을 줄입니다.
List 1 1 1 1 0 1 0
List 2 1 0 1 1 1 0 1st permutation
1 1 1 0 1 0 2nd permutation, final permutation, match, done
이는 더 큰 알파벳과 다양한 정렬 패턴으로 일반화됩니다. 주요 과제는 몇 가지 가능한 표현만으로 좋은 정규화를 찾는 것입니다.이상적으로는 하나의 고유한 표현으로 제대로 된 정상화가 되겠지만, 문제를 감안할 때 그것은 불가능하다고 생각합니다.
RocketRoy의 답변을 바탕으로 한 추가 구축: 앞에 있는 모든 목록을 부호 없는 64비트 숫자로 변환합니다.각 목록에 대해 55비트를 회전하여 가장 작은 숫자 값을 찾습니다.
이제 각 목록에 대해 부호 없는 64비트 값이 하나 남아 다른 목록의 값과 직접 비교할 수 있습니다.함수 is_circular_idental()은 더 이상 필요하지 않습니다.
(기본적으로 목록 요소의 회전에 영향을 받지 않는 목록에 대한 ID 값을 만듭니다.)목록에 임의의 숫자가 있는 경우에도 작동할 수 있습니다.
이것은 살바도르 달리와 같은 생각이지만 현으로 변환할 필요는 없습니다.그 이면에는 불가능한 시프트 검사를 피하기 위한 동일한 KMP 복구 아이디어가 있습니다.KPM Modified(list1, list2+list2)만 호출합니다.
public class KmpModified
{
public int[] CalculatePhi(int[] pattern)
{
var phi = new int[pattern.Length + 1];
phi[0] = -1;
phi[1] = 0;
int pos = 1, cnd = 0;
while (pos < pattern.Length)
if (pattern[pos] == pattern[cnd])
{
cnd++;
phi[pos + 1] = cnd;
pos++;
}
else if (cnd > 0)
cnd = phi[cnd];
else
{
phi[pos + 1] = 0;
pos++;
}
return phi;
}
public IEnumerable<int> Search(int[] pattern, int[] list)
{
var phi = CalculatePhi(pattern);
int m = 0, i = 0;
while (m < list.Length)
if (pattern[i] == list[m])
{
i++;
if (i == pattern.Length)
{
yield return m - i + 1;
i = phi[i];
}
m++;
}
else if (i > 0)
{
i = phi[i];
}
else
{
i = 0;
m++;
}
}
[Fact]
public void BasicTest()
{
var pattern = new[] { 1, 1, 10 };
var list = new[] {2, 4, 1, 1, 1, 10, 1, 5, 1, 1, 10, 9};
var matches = Search(pattern, list).ToList();
Assert.Equal(new[] {3, 8}, matches);
}
[Fact]
public void SolveProblem()
{
var random = new Random();
var list = new int[10];
for (var k = 0; k < list.Length; k++)
list[k]= random.Next();
var rotation = new int[list.Length];
for (var k = 1; k < list.Length; k++)
rotation[k - 1] = list[k];
rotation[rotation.Length - 1] = list[0];
Assert.True(Search(list, rotation.Concat(rotation).ToArray()).Any());
}
}
이것이 도움이 되길 바랍니다!
문제 단순화
- 이 문제는 주문 품목 리스트로 구성되어 있습니다.
- 은 이진법입니다.
(0,1) - 우리는 연속적으로 매핑함으로써 문제를 줄일 수 있습니다.
1이 되어 - 연속적인 그고연으로적속.
0의 카운트로 마를스카너운트로이▁s를로트.
예
A = [ 1, 1, 1, 0, 0, 1, 1, 0 ]
B = [ 1, 1, 0, 1, 1, 1, 0, 0 ]
~
A = [ +3, -2, +2, -1 ]
B = [ +2, -1, +3, -2 ]
- 이 프로세스를 수행하려면 첫 번째 항목과 마지막 항목이 달라야 합니다.
- 이렇게 하면 전체적으로 비교의 양이 줄어듭니다.
프로세스 확인
- 중복된다고 가정하면, 우리가 찾는 것이 무엇인지 가정할 수 있습니다.
- 기본적으로 첫 번째 목록의 첫 번째 항목은 다른 목록의 어딘가에 있어야 합니다.
- 첫 번째 목록의 뒤에 이어지는 내용 및 동일한 방식
- 이전 항목은 첫 번째 목록의 마지막 항목이어야 합니다.
- 순환이라 순서가 같습니다.
더 그립
- 여기서의 문제는 기술적으로 알려진 어디서부터 시작해야 하는가 하는 것입니다.
lookup그리고.look-ahead - 우리는 단지 두 번째 목록을 통해 첫 번째 목록의 첫 번째 요소가 어디에 있는지 확인할 것입니다.
- 리스트를 히스토그램에 매핑한 경우 빈번한 요소의 확률은 더 낮습니다.
유사 코드
FUNCTION IS_DUPLICATE (LIST L1, LIST L2) : BOOLEAN
LIST A = MAP_LIST(L1)
LIST B = MAP_LIST(L2)
LIST ALPHA = LOOKUP_INDEX(B, A[0])
IF A.SIZE != B.SIZE
OR COUNT_CHAR(A, 0) != COUNT_CHAR(B, ALPHA[0]) THEN
RETURN FALSE
END IF
FOR EACH INDEX IN ALPHA
IF ALPHA_NGRAM(A, B, INDEX, 1) THEN
IF IS_DUPLICATE(A, B, INDEX) THEN
RETURN TRUE
END IF
END IF
END FOR
RETURN FALSE
END FUNCTION
FUNCTION IS_DUPLICATE (LIST L1, LIST L2, INTEGER INDEX) : BOOLEAN
INTEGER I = 0
WHILE I < L1.SIZE DO
IF L1[I] != L2[(INDEX+I)%L2.SIZE] THEN
RETURN FALSE
END IF
I = I + 1
END WHILE
RETURN TRUE
END FUNCTION
기능들
MAP_LIST(LIST A):LIST연결 는 새 목록에 .LOOKUP_INDEX(LIST A, INTEGER E):LIST가 요가인의반목인E에 합니다.ACOUNT_CHAR(LIST A , INTEGER E):INTEGER를 세어 .E에서 발생AALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEAN확인할 경우B[I]는 다과같음에 합니다.A[0]N-GRAM
마침내.
목록 크기가 매우 크거나 주기를 확인하기 시작하는 요소가 자주 높은 경우 다음을 수행할 수 있습니다.
첫 번째 목록에서 가장 빈도가 낮은 항목을 찾습니다.
n-그램 N 모수를 증가시켜 선형 검사를 통과할 확률을 낮춥니다.
문제의 목록에 대한 효율적이고 신속한 계산이 가능한 "규준 형식"은 다음과 같습니다.
- 세 개의 숫자를 얻으려면 두 숫자 사이의 0(반올림 무시)을 세십시오.
- 가장 큰 숫자가 첫 번째가 되도록 세 개의 숫자를 돌립니다.
- 번째숫자 (첫번 숫자째(자숫▁(▁the▁first첫
a.18그리고.52(). 사로다인딩코 사이로 다시 합니다.0그리고.34. - 수 (두번째숫자(자숫▁(▁the▁second두번
b.0그리고.26하지만 그것은 별로 중요하지 않습니다. - 세 번째 숫자는 버려, 그냥.
52 - (a + b)를 추가하지 않습니다.
표준형정니다입수은식▁the입니다.b * 35 + a사에이 사이에 0그리고.936입니다. (으)ㄹ 수 있습니다.477전체적으로 순환적으로 정렬된 목록)
저는 두 목록을 비교하고 각 반복에 대해 비교된 값의 인덱스를 증가시키는 간단한 솔루션을 작성했습니다.
제가 파이썬을 잘 몰라서 자바로 썼는데, 정말 간단해서 다른 언어에 적응하기 쉬울 것 같습니다.
이를 통해 다른 유형의 목록을 비교할 수도 있습니다.
public class Main {
public static void main(String[] args){
int[] a = {0,1,1,1,0};
int[] b = {1,1,0,0,1};
System.out.println(isCircularIdentical(a, b));
}
public static boolean isCircularIdentical(int[] a, int[]b){
if(a.length != b.length){
return false;
}
//The outer loop is for the increase of the index of the second list
outer:
for(int i = 0; i < a.length; i++){
//Loop trough the list and compare each value to the according value of the second list
for(int k = 0; k < a.length; k++){
// I use modulo length to wrap around the index
if(a[k] != b[(k + i) % a.length]){
//If the values do not match I continue and shift the index one further
continue outer;
}
}
return true;
}
return false;
}
}
다른 사용자가 언급했듯이 목록의 정규화된 회전을 찾으면 목록을 비교할 수 있습니다.
이를 수행하는 몇 가지 작업 코드는 다음과 같습니다. 기본 방법은 각 목록에 대한 정규화된 회전을 찾아 비교하는 것입니다.
- 각 목록에서 정규화된 회전 지수를 계산합니다.
- 두 목록을 오프셋으로 루프하여 각 항목을 비교하고 일치하지 않으면 반환합니다.
이 방법은 숫자에 의존하지 않으며 문자열 목록(비교할 수 있는 모든 값)을 전달할 수 있습니다.
목록 내 검색을 수행하는 대신 최소 값으로 목록을 시작해야 한다는 것을 알고 있습니다. 따라서 최소 값을 반복하여 가장 낮은 연속 값을 가진 값을 찾을 때까지 검색한 다음 최상의 값이 될 때까지 추가 비교를 위해 이 값을 저장할 수 있습니다.
인덱스를 계산할 때 조기 종료할 수 있는 기회가 많습니다. 일부 최적화에 대한 자세한 내용은 다음과 같습니다.
- 최적 최소값이 하나만 있을 때는 검색을 건너뜁니다.
- 이전 값도 최소값인 경우 최소값 검색을 건너뜁니다. 이보다 더 잘 일치하지는 않습니다.
- 모든 값이 동일한 경우 검색을 건너뜁니다.
- 목록의 최소값이 서로 다른 경우 조기 실패.
- 간격띄우기가 일치하는 경우 정기적인 비교를 사용합니다.
- 비교 중에 목록 중 하나에서 인덱스 값이 래핑되지 않도록 오프셋을 조정합니다.
Python에서 목록 검색이 더 빠를 수 있지만 다른 언어에서도 사용할 수 있는 효율적인 알고리즘을 찾고 싶었습니다.또한 새 목록을 만드는 것을 피하는 것도 몇 가지 이점이 있습니다.
def normalize_rotation_index(ls, v_min_other=None):
""" Return the index or -1 (when the minimum is above `v_min_other`) """
if len(ls) <= 1:
return 0
def compare_rotations(i_a, i_b):
""" Return True when i_a is smaller.
Note: unless there are large duplicate sections of identical values,
this loop will exit early on.
"""
for offset in range(1, len(ls)):
v_a = ls[(i_a + offset) % len(ls)]
v_b = ls[(i_b + offset) % len(ls)]
if v_a < v_b:
return True
elif v_a > v_b:
return False
return False
v_min = ls[0]
i_best_first = 0
i_best_last = 0
i_best_total = 1
for i in range(1, len(ls)):
v = ls[i]
if v_min > v:
v_min = v
i_best_first = i
i_best_last = i
i_best_total = 1
elif v_min == v:
i_best_last = i
i_best_total += 1
# all values match
if i_best_total == len(ls):
return 0
# exit early if we're not matching another lists minimum
if v_min_other is not None:
if v_min != v_min_other:
return -1
# simple case, only one minimum
if i_best_first == i_best_last:
return i_best_first
# otherwise find the minimum with the lowest values compared to all others.
# start looking after the first we've found
i_best = i_best_first
for i in range(i_best_first + 1, i_best_last + 1):
if (ls[i] == v_min) and (ls[i - 1] != v_min):
if compare_rotations(i, i_best):
i_best = i
return i_best
def compare_circular_lists(ls_a, ls_b):
# sanity checks
if len(ls_a) != len(ls_b):
return False
if len(ls_a) <= 1:
return (ls_a == ls_b)
index_a = normalize_rotation_index(ls_a)
index_b = normalize_rotation_index(ls_b, ls_a[index_a])
if index_b == -1:
return False
if index_a == index_b:
return (ls_a == ls_b)
# cancel out 'index_a'
index_b = (index_b - index_a)
if index_b < 0:
index_b += len(ls_a)
index_a = 0 # ignore it
# compare rotated lists
for i in range(len(ls_a)):
if ls_a[i] != ls_b[(index_b + i) % len(ls_b)]:
return False
return True
assert(compare_circular_lists([0, 9, -1, 2, -1], [-1, 2, -1, 0, 9]) == True)
assert(compare_circular_lists([2, 9, -1, 0, -1], [-1, 2, -1, 0, 9]) == False)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["World", "Hello" "Circular"]) == True)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["Circular", "Hello" "World"]) == False)
자세한 테스트/예는 이 토막글을 참조하십시오.
리스트 A가 예상 O(N) 시간에 리스트 B의 주기적 이동과 동일한지 쉽게 확인할 수 있습니다.
저는 다항식 해시 함수를 사용하여 목록 A의 해시와 목록 B의 모든 순환 시프트를 계산할 것입니다.목록 B의 이동이 목록 A와 동일한 해시를 갖는 경우, 실제 요소를 비교하여 동일한지 확인합니다.
이 속도가 빠른 이유는 다항식 해시 함수(매우 일반적임!)를 사용하면 이전의 해시와 일정한 시간에 각 주기적인 해시를 계산할 수 있으므로 O(N) 시간의 모든 주기적인 해시를 계산할 수 있습니다.
다음과 같이 작동합니다.
B가 N개의 원소를 가지고 있다고 가정하면, 소수 P를 사용하는 B의 해시는 다음과 같습니다.
Hb=0;
for (i=0; i<N ; i++)
{
Hb = Hb*P + B[i];
}
이것은 P에서 다항식을 평가하는 최적화된 방법이며 다음과 같습니다.
Hb=0;
for (i=0; i<N ; i++)
{
Hb += B[i] * P^(N-1-i); //^ is exponentiation, not XOR
}
모든 B[i]에 P^(N-1-i)을 곱하는 방법에 주목합니다.만약 우리가 B를 왼쪽으로 1을 옮기면, 첫 번째 B[i]를 제외한 모든 B[i]에 추가 P를 곱하게 됩니다.곱셈이 덧셈보다 많이 분포하기 때문에 전체 해시를 곱하는 것만으로 모든 구성 요소를 한 번에 곱한 다음 첫 번째 요소에 대한 인자를 고정할 수 있습니다.
B의 왼쪽 시프트 해시는 그냥
Hb1 = Hb*P + B[0]*(1-(P^N))
두 번째 왼쪽 이동:
Hb2 = Hb1*P + B[1]*(1-(P^N))
등등...
참고: 위의 모든 연산은 일부 기계어 크기에 대해 모듈식으로 수행되며, P^N을 한 번만 계산하면 됩니다.
가장 단순한 방법으로 접착시키려면, 세트를 사용하세요!
from sets import Set
a = Set ([1, 1, 1, 0, 0])
b = Set ([0, 1, 1, 1, 0])
c = Set ([1, 0, 0, 1, 1])
a==b
True
a==b==c
True
언급URL : https://stackoverflow.com/questions/26924836/how-to-check-whether-two-lists-are-circularly-identical-in-python
'programing' 카테고리의 다른 글
| Python 클래스 파일 이름도 camelCase로 해야 합니까? (0) | 2023.07.24 |
|---|---|
| R에서 "<-"(범위 지정)을 어떻게 사용합니까? (0) | 2023.07.19 |
| 부분 문자열 형식 지정 (0) | 2023.07.19 |
| Python 3에서 수백만 개의 정규식 교체 속도 향상 (0) | 2023.07.19 |
| Python 생성기 패턴에 해당하는 C++ (0) | 2023.07.19 |