[To pytanie jest kontynuacją do obliczenia ciągów ]
Okres
p
łańcuchaw
jest dowolną liczbą całkowitą dodatnią,p
taką, żew[i]=w[i+p]
za każdym razem , gdy zdefiniowane są obie strony tego równania. Niechper(w)
oznacza rozmiar najmniejszego okresuw
. Mówimy, że ciągw
jest okresowy iffper(w) <= |w|/2
.
Tak więc nieformalnie ciąg okresowy jest po prostu ciągiem, który składa się z innego ciągu powtórzonego co najmniej raz. Jedyną komplikacją jest to, że na końcu łańcucha nie wymagamy pełnej kopii powtarzanego ciągu, o ile jest on powtarzany w całości przynajmniej raz.
Na przykład rozważ ciąg x = abcab
. per(abcab) = 3
jak x[1] = x[1+3] = a
, x[2]=x[2+3] = b
i nie ma mniejszy okres. Łańcuch nie abcab
jest zatem okresowy. Jednak ciąg ababa
jest okresowy jak per(ababa) = 2
.
Jako więcej przykładów abcabca
, ababababa
i abcabcabc
są również okresowe.
Dla tych, którzy lubią wyrażenia regularne, ten wykrywa, czy ciąg jest okresowy, czy nie:
\b(\w*)(\w+\1)\2+\b
Zadaniem jest znalezienie wszystkich maksymalnych okresowych podciągów w dłuższym ciągu. Są one czasami nazywane działa w literaturze.
Podciąg
w
jest maksymalnym podciągiem okresowym (uruchomionym), jeśli jest okresowy i aniw[i-1] = w[i-1+p]
aniw[j+1] = w[j+1-p]
. Nieoficjalnie „przebieg” nie może być zawarty w większym „przebiegu” z tym samym okresem.
Ponieważ dwa przebiegi mogą reprezentować ten sam ciąg znaków występujących w różnych miejscach całego ciągu, będziemy reprezentować przebiegi według przedziałów. Oto powyższa definicja powtarzana w kategoriach odstępów.
Przebieg (lub maksymalny okresowy podłańcuch) w ciągu
T
jest interwałem[i...j]
zj>=i
takim, że
T[i...j]
to okresowe słowo z kropkąp = per(T[i...j])
- Jest maksymalny. Formalnie ani
T[i-1] = T[i-1+p]
aniT[j+1] = T[j+1-p]
. Nieoficjalnie przebieg nie może być zawarty w większym przebiegu z tym samym okresem.
Oznacz przez RUNS(T)
zestaw przebiegów w ciągu T
.
Przykłady przebiegów
Cztery maksymalne okresowe podciągi (uruchamia) w ciągu znaków
T = atattatt
sąT[4,5] = tt
,T[7,8] = tt
,T[1,4] = atat
,T[2,8] = tattatt
.Łańcuch
T = aabaabaaaacaacac
zawiera 7 następujących maksymalnych okresowych podciągi (uruchamia):T[1,2] = aa
,T[4,5] = aa
,T[7,10] = aaaa
,T[12,13] = aa
,T[13,16] = acac
,T[1,8] = aabaabaa
,T[9,15] = aacaaca
.Ciąg
T = atatbatatb
zawiera następujące trzy przebiegi. Są to:T[1, 4] = atat
,T[6, 9] = atat
iT[1, 10] = atatbatatb
.
Tutaj używam 1-indeksowania.
Zadanie
Napisz kod, aby dla każdej liczby całkowitej n rozpoczynającej się od 2 wypisałeś największą liczbę przebiegów zawartych w dowolnym ciągu binarnym o długości n
.
Wynik
Twój wynik jest najwyższy, n
jaki osiągniesz w 120 sekund, dzięki czemu k <= n
nikt inny nie opublikował lepszej poprawnej odpowiedzi niż ty. Oczywiście, jeśli masz wszystkie optymalne odpowiedzi, otrzymasz wynik za najwyższą, n
którą opublikujesz. Jednak nawet jeśli twoja odpowiedź nie jest optymalna, nadal możesz uzyskać wynik, jeśli nikt inny go nie pokona.
Języki i biblioteki
Możesz użyć dowolnego dostępnego języka i bibliotek, które ci się podobają. Tam, gdzie jest to wykonalne, dobrze byłoby móc uruchomić kod, więc proszę podać pełne wyjaśnienie, jak uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe.
Przykładowe optima
W następujących przypadkach: n, optimum number of runs, example string
.
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
Co dokładnie powinien wypisać mój kod?
Dla każdego n
kodu należy wypisać pojedynczy ciąg znaków i liczbę zawartych w nim uruchomień.
Moja maszyna Czasy zostaną uruchomione na moim komputerze. Jest to standardowa instalacja ubuntu na ośmiordzeniowym procesorze AMD FX-8350. Oznacza to również, że muszę być w stanie uruchomić Twój kod.
Wiodące odpowiedzi
- 49 Anders Kaseorg w C . Jednowątkowy i działający z L = 12 (2 GB pamięci RAM).
- 27 przez cdlane w C .
źródło
{0,1}
-ciągi, wyraźnie to zaznacz. W przeciwnym razie alfabet może być nieskończony i nie rozumiem, dlaczego twoje przypadki testowe powinny być optymalne, ponieważ wygląda na to, że przeszukałeś tylko{0,1}
łańcuchy.n
poprzedzającym12
i nigdy nie pokazał się alfabetu binarnego. Heurystycznie spodziewałbym się, że ciąg binarny powinien być optymalny, ponieważ dodanie większej liczby znaków zwiększa minimalną długość przebiegu.Odpowiedzi:
do
Odbywa się to rekurencyjnie w poszukiwaniu optymalnych rozwiązań, mocno przycinanych przy użyciu górnej granicy liczby przebiegów, które mogłyby zostać zakończone przez nieznaną pozostałą część łańcucha. Obliczenia w górnej granicy używają gigantycznej tabeli odnośników, której rozmiar jest kontrolowany przez stałą
L
(L=11
: 0,5 GiB,:L=12
2 GiB,:L=13
8 GiB).Na moim laptopie zwiększa się o n = 50 w 100 sekund; następna linia przychodzi za 142 sekundy.
Wydajność:
Oto wszystkie optymalne sekwencje dla n ≤ 64 (nie tylko leksykograficznie pierwsze), wygenerowane przez zmodyfikowaną wersję tego programu i wiele godzin obliczeń.
Niezwykła prawie optymalna sekwencja
Przedrostki nieskończonej sekwencji fraktalnej
który jest niezmienny w przypadku transformacji 101 × 10100, 00 × 101:
wydają się mieć bardzo prawie optymalną liczbę przebiegów - zawsze w granicach 2 optymalnych dla n ≤ 64. Liczba przebiegów w pierwszych n znakach podzielona przez n podejść (13 - 5√5) / 2 ≈ 0,90983. Ale okazuje się, że nie jest to optymalny stosunek - patrz komentarze.
źródło
Ponieważ nie jest to wyścig, jeśli jest tylko jeden koń, przedstawiam moje rozwiązanie, choć jest to tylko ułamek prędkości Andersa Kaseorga i tylko jedna trzecia jako tajemnicza. Połącz z:
Sercem mojego algorytmu jest prosta zmiana i schemat XOR:
Ciąg zer w wyniku XOR, który jest większy lub równy bieżącemu okresowi / zmianie, wskazuje bieg w oryginalnym ciągu dla tego okresu. Na podstawie tego możesz określić, jak długi był bieg i gdzie zaczyna się i kończy. Reszta kodu jest narzutem, konfigurowaniem sytuacji i dekodowaniem wyników.
Mam nadzieję, że po dwóch minutach na maszynie Lembika przyniesie co najmniej 28. (Napisałem wersję pthread, ale udało mi się ją uruchomić jeszcze wolniej).
Wydajność:
źródło
-O3
nie ma być „niebezpieczne”. Umożliwia automatyczną wektoryzację, ale prawdopodobnie nie ma tutaj wektoryzacji. Czasami może spowolnić kod, np. Jeśli używa bezgałęziowego cmov do czegoś, co gałąź bardzo dobrze przewidziała. Ale zwykle powinno to pomóc. Zazwyczaj warto też spróbować clang, aby zobaczyć, które z gcc lub clang tworzą lepszy kod dla określonej pętli. Ponadto prawie zawsze pomaga w użyciu-march=native
, a przynajmniej-mtune=native
jeśli chcesz, aby plik binarny działał w dowolnym miejscu.