Python - Memoization i Collatz Sequence

Question

Kiedy miałem problemy z wykonaniem Problem 14 in Project Euler, odkryłem, że mogę użyć rzeczy zwanej memoization, aby przyspieszyć mój proces (pozwoliłem jej działać przez dobre 15 minut, i wciąż nie powrócił Odpowiedź). Chodzi o to, jak mogę to zaimplementować? Próbowałem, ale otrzymuję keyerror (zwracana wartość jest nieprawidłowa). To budzi mnie, ponieważ jestem pewien, że mogę zastosować do tego memoize i szybciej to zrobić.

lookup = {} 

def countTerms(n): 
    arg = n 
    count = 1 
    while n is not 1: 
     count += 1 
     if not n%2: 
     n /= 2 
     else: 
     n = (n*3 + 1) 
     if n not in lookup: 
     lookup[n] = count 

    return lookup[n], arg 

print max(countTerms(i) for i in range(500001, 1000000, 2)) 

Dzięki.

Answer 1

Istnieje również niezły sposób rekurencyjny, który prawdopodobnie będzie wolniejszy od rozwiązania poorsod, ale jest bardziej podobny do początkowego kodu, więc może być łatwiejszy do zrozumienia.

lookup = {} 

def countTerms(n): 
    if n not in lookup: 
     if n == 1: 
     lookup[n] = 1 
     elif not n % 2: 
     lookup[n] = countTerms(n/2)[0] + 1 
     else: 
     lookup[n] = countTerms(n*3 + 1)[0] + 1 

    return lookup[n], n 

print max(countTerms(i) for i in range(500001, 1000000, 2)) 

Answer 2

Celem zapamiętywania, dla sekwencji Collatza, jest uniknięcie obliczania części listy, które już wykonałeś. Pozostała część sekwencji jest w pełni określona przez bieżącą wartość. Dlatego chcemy sprawdzać tabelę tak często, jak to możliwe, i wyskakując z reszty obliczeń tak szybko, jak to możliwe.

def collatz_sequence(start, table={}): # cheeky trick: store the (mutable) table as a default argument 
    """Returns the Collatz sequence for a given starting number""" 
    l = [] 
    n = start 

    while n not in l: # break if we find ourself in a cycle 
         # (don't assume the Collatz conjecture!) 
     if n in table: 
      l += table[n] 
      break 
     elif n%2 == 0: 
      l.append(n) 
      n = n//2 
     else: 
      l.append(n) 
      n = (3*n) + 1 

    table.update({n: l[i:] for i, n in enumerate(l) if n not in table}) 

    return l 

Czy to działa? Załóżmy szpiegować na to, aby upewnić się, że memoised elementy są używane:

class NoisyDict(dict): 
    def __getitem__(self, item): 
     print("getting", item) 
     return dict.__getitem__(self, item) 

def collatz_sequence(start, table=NoisyDict()): 
    # etc 



In [26]: collatz_sequence(5) 
Out[26]: [5, 16, 8, 4, 2, 1] 

In [27]: collatz_sequence(5) 
getting 5 
Out[27]: [5, 16, 8, 4, 2, 1] 

In [28]: collatz_sequence(32) 
getting 16 
Out[28]: [32, 16, 8, 4, 2, 1] 

In [29]: collatz_sequence.__defaults__[0] 
Out[29]: 
{1: [1], 
2: [2, 1], 
4: [4, 2, 1], 
5: [5, 16, 8, 4, 2, 1], 
8: [8, 4, 2, 1], 
16: [16, 8, 4, 2, 1], 
32: [32, 16, 8, 4, 2, 1]} 

---

EDIT: wiedział mogło być zoptymalizowane! Sekretem jest to, że istnieją dwa miejsca w funkcji (dwa punkty zwrotne), które znamy: l i table nie udostępniają żadnych elementów. Podczas gdy poprzednio unikałem wywoływania table.update z elementami już w table przez testowanie ich, ta wersja funkcji wykorzystuje zamiast tego naszą wiedzę o strumieniu sterowania, oszczędzając dużo czasu.

[collatz_sequence(x) for x in range(500001, 1000000)] teraz około 2 sekund na moim komputerze, podczas gdy podobne wyrażenie z zegarkami wersji @ welter w ciągu 400ms. Myślę, że dzieje się tak dlatego, że funkcje nie obliczają dokładnie tego samego - moja wersja generuje całą sekwencję, podczas gdy @speed po prostu znajduje swoją długość. Nie sądzę więc, żebym mógł tak szybko wdrożyć moją implementację.

def collatz_sequence(start, table={}): # cheeky trick: store the (mutable) table as a default argument 
    """Returns the Collatz sequence for a given starting number""" 
    l = [] 
    n = start 

    while n not in l: # break if we find ourself in a cycle 
         # (don't assume the Collatz conjecture!) 
     if n in table: 
      table.update({x: l[i:] for i, x in enumerate(l)}) 
      return l + table[n] 
     elif n%2 == 0: 
      l.append(n) 
      n = n//2 
     else: 
      l.append(n) 
      n = (3*n) + 1 

    table.update({x: l[i:] for i, x in enumerate(l)}) 
    return l 

PS - znajdź błąd!

Answer 3

To jest moje rozwiązanie PE14:

memo = {1:1} 
def get_collatz(n): 

if n in memo : return memo[n] 

if n % 2 == 0: 
    terms = get_collatz(n/2) + 1 
else: 
    terms = get_collatz(3*n + 1) + 1 

memo[n] = terms 
return terms 

compare = 0 
for x in xrange(1, 999999): 
if x not in memo: 
    ctz = get_collatz(x) 
    if ctz > compare: 
    compare = ctz 
    culprit = x 

print culprit