Python - Memoization e Collatz Sequence

Question

Quando ho faticato a fare Problem 14 in Project Euler, ho scoperto che potevo usare una cosa chiamata memoization per accelerare il mio processo (l'ho lasciato funzionare per ben 15 minuti, e non era ancora tornato una domanda). Il fatto è, come posso implementarlo? Ho provato a, ma ottengo un keyerror (il valore restituito non è valido). Questo mi infastidisce perché sono sicuro di poter applicare la memoization a questo e ottenerlo più velocemente.

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)) 

Grazie.

Answer 1

C'è anche un bel modo ricorsivo per farlo, che probabilmente sarà più lento della soluzione di Poorsod, ma è più simile al tuo codice iniziale, quindi potrebbe essere più facile da capire.

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

Il punto di memoising, per la sequenza di Collatz, è di evitare di calcolare parti della lista che hai già fatto. Il resto di una sequenza è completamente determinato dal valore corrente. Quindi vogliamo controllare la tabella il più spesso possibile, e salvare il resto del calcolo il prima possibile.

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 

Funziona? Diamo spiare su di esso per assicurarsi che gli elementi memoised vengono utilizzati:

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: io sapevo potrebbe essere ottimizzato! Il segreto è che ci sono due punti nella funzione (i due punti di ritorno) che sappiamo l e table non condividere elementi. Mentre precedentemente evitavo di chiamare table.update con elementi già in table testandoli, questa versione della funzione sfrutta invece la nostra conoscenza del flusso di controllo, risparmiando un sacco di tempo.

[collatz_sequence(x) for x in range(500001, 1000000)] ora circa 2 secondi sul mio computer, mentre un'espressione simile con la versione di @ welter ha un clock di 400 ms. Penso che questo sia dovuto al fatto che le funzioni in realtà non calcolano la stessa cosa: la mia versione genera l'intera sequenza, mentre @ welter trova solo la sua lunghezza. Quindi non penso di poter ridurre la mia implementazione alla stessa velocità.

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 - individuare l'errore!

Answer 3

Questa è la mia soluzione a 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