[python] 파이썬에서 두 목록이 원형으로 동일한 지 확인하는 방법

파이썬에서는 요청한 언어 로이 질문에 대답하기에 충분하지 않지만 C / C ++에서는 질문의 매개 변수가 주어지면 0과 1을 비트로 변환하여 uint64_t의 가장 중요하지 않은 비트로 푸시합니다. 이를 통해 한 번의 감소로 1 개의 클럭으로 55 비트를 모두 비교할 수 있습니다.

엄청나게 빠르며 모든 것이 온칩 캐시 (209,880 바이트)에 적합합니다. 55 명의리스트 멤버를 동시에 오른쪽으로 시프트하기위한 하드웨어 지원은 CPU 레지스터에서만 사용 가능합니다. 55 명의 멤버를 동시에 비교할 때도 마찬가지입니다. 이를 통해 소프트웨어 솔루션에 문제를 1 : 1로 매핑 할 수 있습니다. (필요한 경우 최대 256 개의 멤버까지 SIMD / SSE 256 비트 레지스터 사용) 결과적으로 코드는 즉시 독자에게 분명합니다.

파이썬에서 이것을 구현할 수 있을지 모르겠지만, 그것이 가능한지 또는 성능이 무엇인지 알기에 충분하지 않습니다.

그것에 자고 난 후에, 몇 가지가 분명 해졌고, 모든 것이 더 좋아졌습니다.

1.) Dali의 매우 영리한 트릭이 필요하지 않은 비트를 사용하여 원형으로 연결된 목록을 회전시키는 것은 매우 쉽습니다. 64 비트 레지스터 표준 비트 시프트에서는 비트 연산 대신 산술을 사용하여 회전을 매우 간단하게 수행하고 더 파이썬 친화적으로 만들기 위해 노력합니다.

2) 2로 나누기를 사용하면 비트 시프 팅을 쉽게 수행 할 수 있습니다.

3) 모듈러스 2를 사용하여 목록 끝에서 0 또는 1을 쉽게 확인할 수 있습니다.

4.) 꼬리에서리스트의 헤드로 0을 “이동”하는 것은 2로 나눌 수 있습니다. 이것은 실제로 0이 이동 된 경우 55 번째 비트를 거짓으로 만들 수 있기 때문에 이미 아무것도하지 않습니다.

5.) 꼬리에서 목록의 머리 부분으로 1을 “이동”하는 것은 2로 나누어 18,014,398,509,481,984를 추가하여 수행 할 수 있습니다. 이는 55 번째 비트를 true로 표시하고 나머지는 모두 false로 표시하여 생성 된 값입니다.

6.) 주어진 회전 후에 앵커와 구성된 uint64_t의 비교가 TRUE이면 TRUE를 중단하고 반환합니다.

전체 목록 배열을 uint64_ts 배열로 변환하여 반복적으로 변환하지 않아도됩니다.

코드를 최적화하려고 몇 시간을 보낸 후 어셈블리 언어를 연구하여 런타임에서 20 %를 줄일 수있었습니다. O / S 및 MSVC 컴파일러도 어제 정오에 업데이트되었다고 덧붙여 야합니다. 어떤 이유로 든, C 컴파일러가 생성 한 코드의 품질은 업데이트 후 (2014 년 11 월 15 일) 극적으로 향상되었습니다. 런타임은 이제 ~ 70 클럭, 17 나노초 로 구성되어 테스트 링의 모든 55 회전으로 앵커 링을 구성하고 비교합니다. 다른 링에 대한 모든 링의 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;
}

답변

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

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

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)

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