Optimize khoản tiền không dồi dào thuật toán

Question

tôi đang cố gắng để giải quyết this Project Euler question:

Một số hoàn hảo là một con số mà tổng các ước thích hợp của nó là chính xác bằng số. Ví dụ: tổng số tiền thích hợp là số chia của 28 sẽ là 1 + 2 + 4 + 7 + 14 = 28, có nghĩa là 28 là số hoàn hảo.

Số n được gọi là thiếu nếu tổng số ước của nó là nhỏ hơn n và được gọi là dồi dào nếu tổng này vượt quá n.

Vì 12 là số nhỏ nhất, 1 + 2 + 3 + 4 + 6 = 16, số nhỏ nhất có thể được viết dưới dạng tổng của hai số phong phú là 24. Bằng cách phân tích toán học, nó có thể cho thấy rằng tất cả các số nguyên lớn hơn 28123 có thể được viết dưới dạng tổng của hai số dồi dào. Tuy nhiên, giới hạn trên không thể giảm thêm bằng cách phân tích mặc dù được biết rằng số lớn nhất không thể là được biểu thị bằng tổng của hai số dồi dào nhỏ hơn giới hạn này.

Tìm tổng của tất cả các số nguyên dương không thể được viết là tổng của hai số dồi dào.

Giải pháp của tôi:

#returns a list of the divisors of a given number 
def Divs(Number): 
    Divisors = [] 

    for i in range(2 , int(Number**0.5) + 1): 
     if Number % i == 0: 
      Divisors.append(i) 

    for q in range(len(Divisors)): 
     if Divisors[q] != (Number/Divisors[q]): 
      Divisors.append(Number/Divisors[q]) 

    Divisors.insert(0,1) 
    return Divisors 

#returns a list of abundant numbers up to and including the limit 
def AbList(limit): 
    Abundant = [] 

    for i in range(11,limit + 1): 
     if sum(Divs(i)) > i: 
      Abundant.append(i) 

    return Abundant 

#Finds the sum of all positive integers that cannot be written as the 
#sum of two abundant numbers... 
def AbSum(limit): 
    Abundant = AbList(limit) 
    NoAbSum = 0 
    for i in range(1 , limit): 
     AbSum = 0 
     x = 0 
     for x in Abundant: 
      if i - x in Abundant[:i]: 
       AbSum = 1 
       break 
     if AbSum == 0: 
      NoAbSum += i 
    return NoAbSum 

này đã xử lý 3,4 GHz của tôi khoảng 15 phút để giải quyết và tôi đang tìm kiếm một cách tốt hơn. Tôi không quan tâm đến hai chức năng đầu tiên vì chúng cùng nhau mất ít hơn một giây để chạy. Hàm thứ ba là kicker ở đây. Nó chạy qua phạm vi số lên tới giới hạn (trong trường hợp này là 20000-cái gì đó), và mỗi lần, nó chạy qua danh sách các số dồi dào, trừ số từ số hiện tại, sau đó kiểm tra câu trả lời đó số. Nếu có một kết quả phù hợp, vòng lặp ngắt và thử lại với số tiếp theo, tất cả các con đường sẽ đạt tới giới hạn.

Tôi biết rằng phải có cách tốt hơn để làm điều này nhưng tôi hơi mới để lập trình. Làm thế nào tôi có thể tăng tốc thuật toán này?

Answer 1

Bạn đang thử nghiệm mọi số từ 1 đến giới hạn (giả sử 30000) so với mọi số dồi dào, vì vậy bạn đang thực hiện khoảng 30000 * 7428 lần lặp; và bạn đang kiểm tra xem kết quả có nằm trong danh sách hay không, đó là một hoạt động rất chậm - nó sẽ kiểm tra mọi mục trong danh sách cho đến khi nó tìm thấy một kết quả phù hợp!

Thay vào đó, bạn nên tạo mọi số là tổng của hai số phong phú.Nhiều nhất, sẽ mất 7428 * 7428 lần lặp - ít hơn nếu được thực thi đúng cách (gợi ý: tránh kiểm tra cả a + b và b + a bằng cách đảm bảo rằng b luôn luôn> = a; và như người khác đã đề xuất, hãy nhớ dừng khi các khoản tiền quá lớn). Đánh dấu những con số đó ra khỏi danh sách các số bên dưới limit và tổng các số còn lại.

Nói cách khác:

[... 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 ...] 

trở thành

[... 31, 0, 33, 34, 35, 0, 37, 0, 39, 0, 41, 0, 43 ...] 

---

Edit: Sau khi chơi với triển khai trong một vài phút, tôi có thể tự tin nói rằng if i - x in Abundant[:i]: là vấn đề. Giải pháp python đầu tiên được đăng lên diễn đàn P23 của Project Euler là bản thực thi thuật toán thông minh của bạn, sự khác biệt lớn duy nhất là nó sử dụng đặt số lượng dồi dào thay vì danh sách. Nó giải quyết vấn đề trên một bộ vi xử lý Atom trong 15 giây; khi tôi thay đổi nó để sử dụng một danh sách, sau mười lăm phút, nó vẫn chưa giải quyết được vấn đề.

Đạo đức của câu chuyện: x in list là SLOW.

Tuy nhiên, tạo số tiền trực tiếp nhanh hơn trừ và kiểm tra. :)

Answer 2

Một điều có thể giúp bạn thoát khỏi vòng lặp bên trong của bạn khi số lượng phong phú lớn hơn số bạn đang thử nghiệm.

Tôi cũng không hiểu chút này của mã của bạn:

for q in range(len(Divisors)): 
    if Divisors[q] != (Number/Divisors[q]): 
     Divisors.append(Number/Divisors[q]) 

Một khi bạn đã xác nhận rằng modulo là 0, đó là một số chia. Tôi không biết tại sao bạn đang thực hiện kiểm tra nhận dạng bản chất.

Answer 3

Mã của bạn có vẻ như nó có thể hưởng lợi từ bản đồ, bộ lọc hoặc hiểu danh sách có lợi cho những vòng lặp đó.

Answer 4

for x in Abundant: 
     if i - x in Abundant[:i]: 
      AbSum = 1 
      break 

Lưu ý rằng biểu thức in ở đây mất O (i) thời gian và do đó vòng lặp là O (n²). Bạn có thể cải thiện điều này thành O (n) nếu bạn sử dụng số set thay vì số list.

Answer 5

Bạn có thể sử dụng một thủ thuật toán học đơn giản: Tổng số tất cả các số đó không thể được viết như một tổng của hai số dồi dào là tổng của tất cả các số trừ những con số mà có thể được viết như một tổng của hai số phong phú:

solution = sum(range(limit)) - sum(all_two_sums(abundant_numbers)) 

(sum(range(limit)) cũng có thể được đơn giản hóa với toán học, nhưng bạn có thể không tìm thấy nó, trừ khi bạn đang Gauss ;-))

bạn đã có một danh sách số lượng dồi dào, do đó, việc tạo các số có thể là có thể được ghi là tổng của hai số dồi dào và tổng số nhỏ hơn giới hạn. Chỉ cần chắc chắn rằng bạn không có số trùng lặp, một Python set làm điều đó.

Answer 6

Hãy bắt đầu bằng cách tìm kiếm một chút và tìm ra con số lớn nhất không thể hiển thị khi tổng của hai số dồi dào thực sự là 20161. Sau đó, chúng tôi có thể giải quyết vấn đề với thử nghiệm thành viên được thiết lập đơn giản. Thêm vào đó, nó chạy khá nhanh. :-)

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 
from math import sqrt 

def d(n): 
    sum = 1 
    t = sqrt(n) 
    # only proper divisors; start from 2. 
    for i in range(2, int(t)+1): 
     if n % i == 0: 
      sum += i + n/i 
    # don't count the square root twice! 
    if t == int(t): 
     sum -= t 
    return sum 

limit = 20162 
sum = 0 
# it's a set, after all. sets are faster than lists for our needs. 
abn = set() 
for n in range(1, limit): 
    if d(n) > n: 
     abn.add(n) 
    # if the difference of the number we're examining and every number in the set 
    # is in the set, then the number is the sum of two abundant numbers. 
    # otherwise, we must add it to our sum in question. 
    if not any((n-a in abn) for a in abn): 
     sum += n 

Chạy trong 0.6463340939061518 giây tính trung bình trên i5, dựa trên timeit.