Python - Memoization và Collatz Sequence

Question

Khi tôi đang cố gắng làm Problem 14 in Project Euler, tôi phát hiện ra rằng tôi có thể sử dụng một điều được gọi là ghi nhớ để tăng tốc quá trình của mình (tôi để nó chạy trong 15 phút tốt, và nó vẫn chưa quay trở lại một câu trả lời). Vấn đề là, làm thế nào để thực hiện nó? Tôi đã cố gắng, nhưng tôi nhận được một keyerror (giá trị được trả về là không hợp lệ). Điều này lỗi tôi vì tôi tích cực tôi có thể áp dụng ghi nhớ này và nhận được điều này nhanh hơn.

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

Cảm ơn.

Answer 1

Ngoài ra còn có một cách đệ quy tốt để làm điều này, có thể sẽ chậm hơn giải pháp của poorsod, nhưng nó tương tự như mã ban đầu của bạn, do đó bạn có thể dễ hiểu hơn.

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

Điểm ghi nhớ, đối với chuỗi Collatz, là tránh tính toán các phần của danh sách mà bạn đã thực hiện. Phần còn lại của một chuỗi được xác định đầy đủ bởi giá trị hiện tại. Vì vậy, chúng tôi muốn kiểm tra bảng càng thường xuyên càng tốt, và bảo lãnh khỏi phần còn lại của phép tính ngay khi có thể.

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 

Có hoạt động không? Hãy thám vào nó để đảm bảo các yếu tố memoised đang được sử dụng:

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: Tôi biết nó có thể được tối ưu hóa! Bí mật là có hai vị trí trong hàm (hai điểm trả về) mà chúng ta biết là l và table không chia sẻ phần tử nào. Trong khi trước đây tôi tránh gọi table.update với các yếu tố đã có trong table bằng cách kiểm tra chúng, phiên bản này của hàm thay vì khai thác kiến ​​thức của chúng tôi về luồng điều khiển, tiết kiệm rất nhiều thời gian.

[collatz_sequence(x) for x in range(500001, 1000000)] giờ đây khoảng 2 giây trên máy tính của tôi, trong khi biểu thức tương tự với đồng hồ phiên bản @ welter trong 400 mili giây. Tôi nghĩ rằng điều này là bởi vì các chức năng không thực sự tính toán cùng một điều - phiên bản của tôi tạo ra toàn bộ chuỗi, trong khi @ welter chỉ tìm thấy chiều dài của nó. Vì vậy, tôi không nghĩ rằng tôi có thể nhận được thực hiện của tôi xuống đến cùng một tốc độ.

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 - phát hiện lỗi!

Answer 3

Đây là giải pháp của tôi để 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