Nie posiadam wystarczającej wiedzy w Pythonie, aby odpowiedzieć na to pytanie w żądanym języku, ale w C / C ++, biorąc pod uwagę parametry twojego pytania, zamieniłbym zera i jedynki na bity i wypchnąłbym je na najmniej znaczące bity uint64_t. Umożliwi to porównanie wszystkich 55 bitów za jednym zamachem - 1 zegar.
Niesamowicie szybko, a całość zmieści się w wbudowanych pamięciach podręcznych (209880 bajtów). Wsparcie sprzętowe dla przesunięcia wszystkich 55 elementów listy w prawo jednocześnie jest dostępne tylko w rejestrach CPU. To samo dotyczy jednoczesnego porównywania wszystkich 55 członków. Pozwala to na mapowanie problemu 1 do 1 na rozwiązanie programowe. (i przy użyciu 256-bitowych rejestrów SIMD / SSE, w razie potrzeby do 256 członków) W rezultacie kod jest od razu widoczny dla czytelnika.
Możesz być w stanie zaimplementować to w Pythonie, po prostu nie znam tego wystarczająco dobrze, aby wiedzieć, czy to możliwe lub jaka może być wydajność.
Po spaniu na nim kilka rzeczy stało się oczywistych i wszystko na lepsze.
1.) Tak łatwo jest obrócić listę połączoną cyklicznie za pomocą bitów, że bardzo sprytna sztuczka Dalego nie jest konieczna. Wewnątrz 64-bitowego rejestru standardowe przesunięcie bitów spowoduje bardzo prostą rotację i usiłuje uczynić to wszystko bardziej przyjaznym dla Pythona, używając arytmetyki zamiast operacji bitowych.
2.) Przesunięcie końcówki można łatwo wykonać za pomocą dzielenia przez 2.
3.) Sprawdzenie końca listy na 0 lub 1 można łatwo zrobić za pomocą modulo 2.
4.) „Przeniesienie” 0 na początek listy z ogona można wykonać dzieląc przez 2. Dzieje się tak, ponieważ gdyby zero zostało faktycznie przesunięte, 55-ty bit byłby fałszywy, co już jest, nie robiąc absolutnie nic.
5.) „Przeniesienie” 1 na początek listy z ogona można wykonać dzieląc przez 2 i dodając 18 014 398 509 481 984 - co jest wartością utworzoną przez oznaczenie 55. bitu jako prawda, a cała reszta jako fałszywa.
6.) Jeśli porównanie zakotwiczenia i złożonego uint64_t jest PRAWDA po dowolnym podanym obrocie, przerwij i zwróć PRAWDA.
Przekonwertowałbym całą tablicę list na tablicę uint64_ts na samym początku, aby uniknąć konieczności wielokrotnego wykonywania konwersji.
Po spędzeniu kilku godzin na optymalizacji kodu i nauce języka asemblera udało mi się skrócić o 20% czas pracy. Powinienem dodać, że kompilator O / S i MSVC również został wczoraj zaktualizowany w południe. Z jakiegoś powodu jakość kodu, który utworzył kompilator C, znacznie się poprawiła po aktualizacji (15.11.2014). Czas działania wynosi teraz ~ 70 zegarów, 17 nanosekund na skomponowanie i porównanie pierścienia kotwicy ze wszystkimi 55 zwojami pierścienia testowego, a NxN wszystkich pierścieni ze wszystkimi pozostałymi zajmuje 12,5 sekundy .
Ten kod jest tak ciasny, że wszystkie rejestry oprócz 4 siedzą wokół, nie robiąc nic w 99% przypadków. Język asemblera pasuje do kodu C prawie wiersz po wierszu. Bardzo łatwe do odczytania i zrozumienia. Świetny projekt montażowy, gdyby ktoś się tego uczył.
Sprzęt to Hazwell i7, 64-bitowy MSVC, pełna optymalizacja.
#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;
}
