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.