711 wyrazów o optymalizacji

Tytuł jest przekorny – raczej nie będzie to 711 wyrazów, ale liczba na początku tytułu dobrze wpływa na klikalność. Poza tym, liczba 711 jak najbardziej jest na miejscu, a sam wpis będzie o optymalizacji.

Mianowicie pojawił się pod koniec zeszłego roku Sekurak Book Simple CTF, gdzie było pewne zadanie. Jeśli chcesz pobawić się w zrobienie tego CTF samodzielnie, choć jest już zakończony[1], to dobry moment na przerwanie lektury wpisu. Zadanie jest na tyle proste i znane, że publikacja rozwiązania nie spowoduje krzywdy, a przy tym podczas dyskusji z kolegą z pracy pojawiły się ciekawe zagadnienia natury optymalizacyjnej, więc postanowiłem opisać.

Zmodyfikowana treść zadania, z zachowaniem pierwotnego sensu, pojawiła się jako wpis zagadka o siódmej jedenaście na zaprzyjaźnionym blogu. Z moją niewielką pomocą. Jeśli ktoś nie chce się bawić w całą CTFową otoczkę, a ma ochotę wytężyć mózg, zapraszam tamże. Tym bardziej, że jest więcej zagadek.

Całość daje się sprowadzić do układu dwóch równań z czterema niewiadomymi:
a + b + c + d = 7,11
a * b * c * d = 7,11
WolframAlpha – być może niewprawnie użyty – protestował Standard computation time exceeded, ale przecież to się da policzyć… W końcu chodzi o wartości nieciągłe, bo ceny muszą być wielokrotnością jednego grosza. Wiemy zatem, że każda z wartości jest większa od zera, mniejsza od 711 i jest wielokrotnością 0,01. Tu pauza – komputery znacznie lepiej radzą sobie z wartościami całkowitymi[2], więc przemnóżmy wartości przez 100 i przejdźmy w tym momencie na resztę czasu równoważną formę:
a + b + c + d = 711
a * b * c * d = 711000000

Przy naiwnym brute force, korzystając jedynie z faktu, że wszystkie zmienne muszą być liczbami całkowitymi, mamy do sprawdzenia maksymalnie 711^4 kombinacji. Czyli 225 miliardów. Jest to wersja wyjściowa, bez żadnych optymalizacji. Można to zapisać w Pythonie w postaci:

limit = 712
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit):
        for c in range(1, limit):
            for d in range(1, limit):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Jak widać zliczam też ilość iteracji, i dzięki temu wiem, że komputer musi – w różnych pętlach – policzyć w sumie prawie do 43 miliardów, zanim znajdzie rozwiązanie. Czas znalezienia rozwiązania litościwe pominę – spokojnie można wybrać się na spacer czy zakupy.

Mamy jednak dwie dodatkowe własności: iloczyn czterech liczb oraz ich sumę. Jeśli ktoś bawił się w sprawdzanie, czy dana liczba jest pierwsza, to pamięta zapewne, jeśli liczba jest złożona, to mniejszy dzielnik będzie co najwyżej równy pierwiastkowi danej liczby. W naszym przypadku iloczyn dwóch niewiadomych będzie co najwyżej równy pierwiastkowi z 711000000, czyli 26665. Z kolei któraś z niewiadomych będzie mniejsza od pierwiastka z 26665, czyli nieco ponad 163. Można więc ograniczyć jedną ze zmiennych – oczywiście tę najczęściej używaną – do 163.
Dodatkowo, niewiele myśląc, można skorzystać z własności sumowania i ograniczyć pozostałe zmienne do 711-163=548. Czyli zmniejszyć przeszukiwaną przestrzeń do niecałych 27 miliardów. Oblekając to w skrypt, pierwsza optymalizacja wygląda następująco:

limit = 549
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit):
        for c in range(1, limit):
            for d in range(1, 164):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Czas potrzebny na rozwiązanie nadal pomijam, ale jest to raczej tyle, ile potrzeba na zrobienie kawy czy herbaty, niż zakupów. Ilość iteracji potrzebnych do znalezienia rozwiązania to niecałe 6 mld.

Jeśli nie pamiętamy o ciekawej własności związanej z dzielnikami danej liczby, to nadal możemy zoptymalizować pętle tak, żeby automatycznie uwzględniać w nich warunek związany z sumą . Daną zmienną zwiększamy do wartości zależnej od wartości pozostałych zmiennych. Dzięki temu można zaobserwować, że w miarę wzrostu wartości zmiennej a sprawdzenia pozostałych są coraz szybsze.

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

Rozwiązanie jest znajdowane nawet nieco szybciej, niż w poprzednim przypadku – ok. 5,5 mld iteracji.

Tu pojawił się pomysł: co gdyby zapisać to w taki sposób, by program działał na początku bardzo szybko i zwalniał? Czyli nie zaczynamy od niskich wartości zmiennych i zwiększamy, tylko zaczynamy od wysokich i zmniejszamy? Można to zapisać następująco:

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

Przyznaję, że efekty tego podejścia mnie zaskoczyły. Tylko 1 mld operacji potrzebnych do znalezienia rozwiązania. Na moim sprzęcie skrypt wykonał się poniżej 3 minut na Pythonie 3.8.3. Co ciekawe dla Pythona 2.7.18 był to czas poniżej 2 minut, więc znacznie szybciej. Oba z paczek z repo Debiana unstable. Ale to raczej tylko ciekawostka, Python 2 jest martwy.

Dochodzimy jednak do sedna. Widać, że interpreter Pythona ma znaczenie. Jeśli zależy nam na szybkości, to warto zainteresować się alternatywną implementacją Pythona, czyli projektem PyPy. PyPy w wersji 7.3.1 (kompatybilna z Pythonem 3.6.9) wykonuje powyższy program w… nieco ponad 3 sekundy. Czyli jakieś pięćdziesiąt razy szybciej. Jeśli wrócimy do rozwiązania drugiego, to okaże się, że z użyciem PyPy można je znaleźć w 17 sekund. Natomiast wersja naiwna to… raptem 2 minuty.

Jak widać, szybkie narzędzia mogą prowadzić do lenistwa umysłowego – skoro działa szybko, to po co optymalizować? Optymalizacja algorytmu w powyższych przykładach nie jest skończona, da się lepiej. Znacznie lepiej. Na razie zostawię pole do popisu czytelnikom w komentarzach, za jakiś tydzień zaktualizuję wpis.

[1] Jest to naprawdę prosty CTF, jeśli ktoś nie miał okazji się bawić – polecam przymierzyć.
[2] Jak mawiają: real programmers use integers.

UPDATE Dostępne są kolejne wpisy na ten temat.

Aktualizacja do Catalina 10.15.5

Dawno nie było nic o macOS. Jest stabilnie, czyli korzystam i zbyt zadowolony nie jestem. Ostatnio zrobiłem aktualizację do 10.15.5, więc jest okazja do narzekania.

Przede wszystkim, robiłem aktualizację z 10.15.3, nie z 10.15.4, który był wydany pod koniec marca. Co też świadczy w jakiś sposób o tym, że te aktualizacje nie są wcale takie lekkie, łatwe i przyjemne, bo lubię mieć aktualny soft. Czynników było oczywiście więcej, taki drobiazg jak średnia wygoda by mnie nie powstrzymał. A to zespół opiekujący się systemami w firmie nie dał zielonego światła od razu, a to pandemia, więc trochę strach, że nie pójdzie i co wtedy, a to dyżury i wypada mieć sprzęt działający. Koniec końców, zdążyli wydać 10.15.5, nim zaktualizowałem.

Sama aktualizacja przypomniała mi, czemu nie jest to miły proces – stąd notka. 5 GB danych do pobrania, więc dużo. Wiedziałem, że to trwa, więc załączyłem i poszedłem precz. Gdy wróciłem, system marudził, że nie umie zamknąć programów. Znaczy głaszcz mnie użytkowniku, pozamykaj i try again. Zamknąłem kilka programów, dłuższą chwilę trwała walka z edytorem Atom. Bardzo nie chciał się zamknąć i koniec końców używałem force quit. Jeśli ktoś jest przyzwyczajony do podejścia linuksowego, gdzie system robi co mu się każe, bez szemrania i dodatkowego popychania – bardzo słabo to wygląda.

Jak już wszystko pozamykałem i w końcu się zrestartował, przypomniała mi się anegdotka o tym jak Windows liczy czas/postęp: ostatnie 5 min/5% trwa kwadrans/jedną trzecią czasu. Jak podczas pobierania wiało optymizmem, że będzie pół godziny, tak pół godziny to zbierał się po reboocie. To już nawet nie tylko Linux, ale nawet Windows jakoś szybciej sobie radzi z aktualizacjami.

Potem, po uruchomieniu, było z górki, za wyjątkiem jednego ostrzeżenia, które wyglądało tak:

Informacja o przestarzałym rozszerzeniu systemowym

Existing software on your system loaded system extension signed by „Fumihiko Kakayama”, which will be incompatible with a future version of macOS. Contact the developer for support.

Zgadza się, nie jest napisane o jaki program chodzi. Za to jest imię i nazwisko developera, który podpisał rozszerzenie systemowe. Nie wiem jak czytelnicy, ale ja kojarzę jakiego softu używam, nie kto go jest developerem, a już o rozszerzeniach i osobach je podpisujących nie mam pojęcia. No ale ja truskawki cukrem… Odnośnika brak, w learn more również pustka.

W każdym razie szybkie wyszukanie ujawniło, że chodzi o Karabiner. I jestem trochę przerażony, bo bez tego softu macbook będzie dla mnie nieużywalny praktycznie. Przynajmniej w zakresie pisania z pl-znakami. Mam nadzieję, że poprawią lub będzie inna opcja na przemapowanie klawiszy[1].

Trochę jestem zdziwiony, że nie jest napisane o którą wersję chodzi. Dużą? Małą? Najbliższą? Którąś kolejną?

[1] UPDATE Po czasie okazało się, że można przemapować klawisze bez Karabiner Elements.

Niedoszła afera z Brave

Wszystko zaczęło się od wpisu o nieco przydługim tytule The Brave web browser is hijacking links, and inserting affiliate codes, który podrzucił kumpel z pracy. Z tytułu wynika, że Brave podmienia linki tak, aby używane były jego kody afiliacyjne.

Krótko o afiliacji – serwisy internetowe płacą za ruch, albo, dokładniej, za określone akcje użytkowników. Np. rejestracja w serwisie czy zakup produktu. Zwykle wejście od określonego polecającego jest identyfikowane przez odpowiedni parametr w URL, zliczana jest liczba interakcji, a na koniec okresu rozliczeniowego podmiot kierujący użytkowników do serwisu dostaje pieniądze. Takie płatne polecanie.

Z kolei Brave to przeglądarka, która reklamuje się jako szybka, bezpieczna. Blokuje reklamy i trackery, w zamian oferując użytkownikom możliwość zarabiania za oglądanie reklam i dzielenia się z twórcami stron WWW. Brzmi nieco utopijnie i podchodziłem nieco sceptycznie, ale… sprawdziłem, faktycznie jest szybka i bardzo łatwo pozwala na blokowanie reklam, bez konieczności zabawy z rozszerzeniami typu uBlock. Nie jestem fanem, ale przyznaję, że to świetna kombinacja do niektórych zastosowań.

Jak widać w artykule kręcona jest afera, jakoby przeglądarka Brave podmieniała linki i wstawiała swoje kody. Tak naprawdę użytkownikowi końcowemu jest raczej obojętne, kto skorzysta na jego rejestracji w jakimś serwisie. Oczywiście cicha podmiana psułaby biznes afiliacyjny, ale byłby to raczej problem wydawców. I żeby doszło do podmiany, użytkownik i tak musiałby wykonywać interakcję z portalem, na którym uruchomiona jest afiliacja. Biorąc pod uwagę, że chodzi o kilka portali związanych z krytpowalutami, szansa na to jest
niewielka. Więc nawet gdyby o to chodziło, to wpływ na użytkownika końcowego jest dyskusyjny i nie widzę powodu by rezygnować z dobrej przeglądarki. Choć oczywiście takie działanie byłoby kontrowersyjne od strony etycznej i ingerowałoby w wolność użytkowników.

Trochę dziwne byłoby jednak trzymanie listy „cichych podmian” publicznie w źródłach na GitHubie, prawda? No właśnie… Używam od pewnego czasu trybu przypuszczającego, bo tak naprawdę nie o podmienianie linków tak naprawdę chodzi. Z tego co sprawdziłem, nie chodzi o cichą podmianę bez wiedzy użytkownika, tylko o… wyświetlenie w sugerowanych stron z linkiem afiliacyjnym w ramach podpowiedzi, gdy użytkownik wpisuje odpowiedni ciąg w adresie strony.

Podpowiedź w pasku adresu w przeglądarce Brave

Użytkownik musi samodzielnie, ręcznie wybrać URL będący linkiem afiliacyjnym. Co więcej, opcję podpowiadania można w ogóle wyłączyć w ustawieniach, po prostu klikając, nie trzeba używać żadnych ukrytych opcji.

Wiadomo, że Brave to projekt komercyjny, więc jakoś zarabiać musi, ale w tym przypadku w mojej ocenie nie dzieje się nic złego. Nadal spokojnie można używać Brave, jeśli komuś zależy na szybkiej przeglądarce z wbudowanym blokowaniem reklam. Z racji tego, że źródła Brave są dostępne na GitHubie, ciche nadużycia będą raczej trudne do przeprowadzenia.

UPDATE: Dodałem screenshot poglądowy jak to wygląda. Ale przyznaję, że sprawdziłem niedokładnie i trochę racji w zarzutach jest – jeśli wpiszemy cały ciąg binance.us to jako podpowiedź wskakuje pierwszy URL, więc wciśnięcie klawisza enter w tym momencie spowoduje wejście z linkiem afiliacyjnym od Brave:

Podpowiedź w pasku adres w przeglądarce Brave – pełna nazwa, podświetlony link, który będzie użyty po wciśnięciu enter.
Podpowiedź w pasku adres w przeglądarce Brave – pełna nazwa plus spacja, podświetlony link, który będzie użyty po wciśnięciu enter.

Jak widać jest to widoczne dla użytkownika, jak widać powyżej dodanie jakiegokolwiek znaku (spacja, /) po binance.us spowoduje wejście bezpośrednie, bez podpowiedzi, ale… jest.