Opublikowane w

Serial Dark

Recenzje serialu Dark wyrastają jak grzyby po deszczu w moim bąbelku sieci. Tak się składa, że wczoraj skończyłem oglądać całość serialu. Doczytałem też wszystkie zaległe wpisy i trochę dodatkowych faktów. Mogę więc z czystym sumieniem dorzucić moje trzy grosze w temacie. Jeśli ktoś boi się spoilerów to bez obaw – w tym wpisie ich nie będzie.

Krótko o serialu Dark

Jeśli weźmiemy naukę i religię, fizykę i metafizykę, podlejemy symbolami i nawiązaniami różnej maści, to powstanie albo coś dobrego, albo totalnie niestrawnego. Uważam, że w przypadku serialu Dark produkowanego przez Netflix[1] udało się to pierwsze. Zasługa ciekawego pomysłu, dobrej fabuły, bardzo dobrego dopracowania wizualnego i muzycznego. Mimo minimalizmu.

Trzeba jednak zauważyć, że jeśli ktoś oczekuje zamkniętej, w pełni logicznej opowieści, to może się zawieść. Serial zdecydowanie pozostawia pewne kwestie czy wątki niedopowiedziane lub wręcz nierozwiązane. Niemniej uważam, że ze względu na okoliczności jest to usprawiedliwione.

Co mamy w serialu Dark? Klimat trochę jak w serialu Twin Peaks. Tajemnica i jej stopniowe odkrywanie. Ciężki i mroczny i mroczny klimat, więc 16+ w pełni zasłużone. Całość dzieje się w Niemczech, w małej, fikcyjnej miejscowości Winden[2], ale bohaterów jest wielu, a ich losy mocno się nie tyle splatają, co wręcz plączą.

Świetnie zbudowany klimat, wiele nawiązań, zarówno do innych seriali, jak i do niemieckiej popkultury. Muzyka mocno wykorzystywana do budowania nastroju. W ogóle mam wrażenie, że Niemcy nauczyli się dobrze tworzyć klimat niedawnej przeszłości i wykorzystują to w kulturze, zwłaszcza w filmach. Jest to któryś z kolei film który oglądam lub czytam recenzję, gdzie jest to widoczne.

Recenzje i linki

W każdym razie polecam przymierzenie przynajmniej pierwszego sezonu Dark. Jest najlżejszy, chyba najłatwiejszy w odbiorze i dobrze oddaje to, co nas czeka. Potem jest i ciężej, i więcej wątków, i szybsza akcja. Zresztą nie tylko mi się pierwszy sezon najbardziej podobał. Co nie znaczy, że reszta jest zła. Za to na pewno jest bardziej, zakręcona, odjechana i skomplikowana.

Gdyby komuś nie wystarczyła taka recenzja to odsyłam – dopiero teraz, bo za brak spoilerów nie ręczę – do recenzji, które mógłbym podlinkować na początku wpisu. Przed obejrzeniem przeczytałem pierwszą część wpisu Cichego. Zdradza ona nieco więcej, niż napisałem, ale nic, czego nie dowiadujemy się w pierwszych odcinkach. IMO lektura pierwszej części wpisu nie psuje odbioru, ale YMMV. Drugą recenzję polecam odpuścić minimum do końca pierwszego sezonu. Tak naprawdę do końca trzeciego.

Na koniec jeszcze link do fandomowej wiki oraz oficjalnego przewodnika po serialu. W obu miejscach spoilery latają stadami[3], więc zaglądamy zdecydowanie dopiero po obejrzeniu całości.

[1] Tak, mam od jakiegoś czasu Netfliksa i wpis o nim w szkicach. Nie mam czasu dokończyć, oglądam seriale.

[2] Prawdziwe Winden też istnieją, niemniej to serialowe jest fikcyjne.

[3] No dobrze, na fandomowej wiki latają stadami. Oficjalny przewodnik niby jest wolny od spoilerów, ale… pewne rzeczy ujawnia, więc nie do końca się z tym zgodzę. Jeśli ktoś chce zupełnie od zera poznawać, to polecam odpuścić, tym bardziej, że w pierwszym sezonie jest zbędny.

Opublikowane w

711 wyrazów o optymalizacji – część 3

Była część pierwsza i część druga, pora na kolejną, niezupełnie planowaną. Jak pamiętamy w części drugiej udało się ograniczyć sprawdzane liczby do 49 sztuk. To, co chodziło mi od czasu do czasu po głowie to pytanie, czy da się rozwiązać tę zagadkę „na piechotę”, bez użycia komputera?

Rozejrzałem się za możliwymi uproszczeniami i zauważyłem kolejne potencjalne pole do optymalizacji, czyli zmniejszenia liczby potrzebnych obliczeń. Jak wiadomo, 711 jest liczbą nieparzystą. Aby suma dwóch liczb była nieparzysta, jedna z nich musi być parzysta, druga nieparzysta. Z kolei aby suma dwóch liczb była parzysta, albo obie muszą być parzyste, albo nieparzyste. Tu mamy do czynienia z sumą czterech liczb, więc są dwa przypadki. Albo jedna z liczb jest nieparzysta, a trzy są parzyste, albo odwrotnie.

Z naszych 49 liczb, 37 jest parzystych, a 12 nieparzystych. Jak to wpływa na przestrzeń rozwiązań? Z 49^4, czyli ok. 5,8 mln przechodzimy na 12*37^3 + 37*12^3 czyli ok. 672 tys. Nadal trochę dużo jak na ręczne liczenie, ale jak to wpłynie na czas obliczeń? Nasz skrypt będzie miał postać:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

for a in range(0, len(divs_even)-1):
    for b in range(a, len(divs_odd)-1):
        for c in range (0, len(divs_odd)-1):
            for d in range (c, len(divs_odd)-1):
                iterations += 1
                if divs_even[a] + divs_odd[b] + divs_odd[c] + divs_odd[d] == 711:
                    if divs_even[a] * divs_odd[b] * divs_odd[c] * divs_odd[d] == 711000000:
                        print("Solved: ", divs_even[a], divs_odd[b], divs_odd[c], divs_odd[d], iterations)
                        exit()

for a in range(0, len(divs_odd)-1):
    for b in range(0, len(divs_even)-1):
        for c in range (b, len(divs_even)-1):
            for d in range (c, len(divs_even)-1):
                iterations += 1
                if divs_odd[a] + divs_even[b] + divs_even[c] + divs_even[d] == 711:
                    if divs_odd[a] * divs_even[b] * divs_even[c] * divs_even[d] == 711000000:
                        print("Solved: ", divs_odd[a], divs_even[b], divs_even[c], divs_even[d], iterations)
                        exit()

Niezależnie od kolejności bloków (najpierw 1 liczba parzysta i 3 nieparzyste, co jest teoretycznie korzystniejszym wariantem, czy odwrotnie), potrzebować będziemy poniżej 95 tys. iteracji. Czas to 0,08 sekundy dla zwykłego interpretera Pythona lub 0,12 sekundy dla Pypy.

Możliwa jest też wersja „w dół”:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

for a in range(len(divs_even)-1, 0, -1):
    for b in range(len(divs_odd)-1, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs_even[a] + divs_odd[b] + divs_odd[c] + divs_odd[d] == 711:
                    if divs_even[a] * divs_odd[b] * divs_odd[c] * divs_odd[d] == 711000000:
                        print("Solved: ", divs_even[a], divs_odd[b], divs_odd[c], divs_odd[d], iterations)
                        exit()

for a in range(len(divs_odd)-1, 0, -1):
    for b in range(len(divs_even)-1, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs_odd[a] + divs_even[b] + divs_even[c] + divs_even[d] == 711:
                    if divs_odd[a] * divs_even[b] * divs_even[c] * divs_even[d] == 711000000:
                        print("Solved: ", divs_odd[a], divs_even[b], divs_even[c], divs_even[d], iterations)
                        exit()

Ilość potrzebnych iteracji waha się od 18 do 28 tys. w zależności od kolejności bloków. Natomiast czas wykonania to 0,06 sekundy dla zwykłego interpretera Pythona i 0,1 sekundy dla Pypy.

Nadal nie jest to optymalizacja powodująca, że da się policzyć „na piechotę”, ale… coraz bliżej.

Opublikowane w

711 wyrazów o optymalizacji – część 2

Tym, co nie czytali polecam lekturę części pierwszej. Tymczasem pojawił się wpis z rozwiązaniem i pojawiło się tam znacznie lepsze podejście do tematu. Optymalizacja polega na tym, że korzysta ono z właściwości, że wszystkie składowe muszą być dzielnikami 7,11 i wielokrotnością 0,01. W wersji całkowitej – muszą być liczbami całkowitymi będącymi dzielnikami. Następnie generuje kombinacje tych liczb i sprawdza właściwe warunki. Lekko dostosowany kod to:

import itertools
number = 711
iterations = 0
divs = list()
for i in range(1, number + 1):
    if 711000000 % i == 0:
        divs.append(i)

for i in itertools.combinations_with_replacement(divs, 4):
    iterations += 1
    if sum(i) == 711 and i[0] * i[1] * i[2] * i[3] == 711000000:
        print(i, iterations)

print(len(divs))

Dodałem wyświetlanie ilości dzielników – jest ich raptem 62, więc przeszukiwana przestrzeń to 62^4 czyli… niecałe 15 mln. Rozwiązanie jest znajdowane po nieco ponad 600 tys. iteracji w czasie… pomijalnym, bowiem ok. 0,2 sekundy, niezależnie od interpretera. Przy pomiarze tak niskich czasów wykonania wypadałoby się pobawić już w uśrednianie, ale chodzi o wartości orientacyjne.

W zasadzie dalsza optymalizacja nie ma sensu, ale pobawić się można. Przede wszystkim, można wyeliminować samo 711. Jeśli którakolwiek wartość byłaby taka, to pozostałe musiałyby być zerami, co jest sprzeczne z warunkami zadania. Kolejny całkowity dzielnik to połowa 711. Po uwzględnieniu tego, skrypt przyjmie postać:

import itertools
number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for i in itertools.combinations_with_replacement(divs, 4):
    iterations += 1
    if sum(i) == 711 and i[0] * i[1] * i[2] * i[3] == 711000000:
        print(i, iterations)

print(len(divs))

Ogranicza nam to liczbę sprawdzanych dzielników do 49, przestrzeń do niecałych 6 mln, a liczbę iteracji potrzebnych do znalezienia rozwiązania do 266 tys. Dla przypomnienia, w pierwszym rozwiązaniu, które było czystym brute force zaczynaliśmy od przestrzeni 225 miliardów, czyli 44 tys. razy większej.

A gdyby tak nadal korzystać z dzielników, ale zapomnieć o itertools i wrócić do starych, dobrych pętli, tym razem nie na wartościach, tylko na indeksach w liście divs? Wersja naiwna to:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(0, len(divs)-1):
    for b in range(0, len(divs)-1):
        for c in range (0, len(divs)-1):
            for d in range (0, len(divs)-1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Wyraźny krok wstecz – 3,6 mln iteracji i prawie sekunda (PyPy nadal ~0,2s). Ale otwiera nam to drogę do znanych już optymalizacji:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(0, len(divs)-1):
    for b in range(a, len(divs)-1):
        for c in range (b, len(divs)-1):
            for d in range (c, len(divs)-1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Jest tak dobrze, jak przy itertoolsach: ~0,2s oraz 246 tys. iteracji. Pamiętamy jednak, że najlepsze wyniki były dla sprawdzania od największych do najmniejszych, zatem:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(len(divs)-1, 0, -1):
    for b in range(a, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Wynik znajdowany jest już po 30 tys. iteracji, w czasie poniżej 0,1s na zwykłym interpreterze Pythona. Co ciekawe, w tym wariancie PyPy jest nieco wolniejsze, z czasem nieco ponad 0,1s, zapewne większy narzut na uruchomienie interpretera.

UPDATE Dostępna jest kolejna część traktująca o optymalizacji.