一个小的方案编程挑战

Question

我正在学习从编程语言中获得一些新的东西，下面的代码是Project问题21的解决方案，但是当我使用Chibi-Scheme时，代码运行速度比列出的Python代码慢10倍。为提高效率，任何一位计划工匠可以将代码重构成“计划”成语。

计划守则：

(define (sum-of-amicable-pairs n)
  (let ((sums (make-vector n)))
        (for-each
          (lambda (i) 
            (vector-set! sums i
                         (reduce + 0 
                                 (filter (lambda (j) (= (remainder i j) 0)) 
                                         (iota (+ 1 (quotient i 2)) 1 1))))) 
            (iota n 0 1))

        (let loop ((res (make-vector n 0))
                   (i 0))
          (cond
            ((= i n) (reduce + 0 (vector->list res)))
            ((and (< (vector-ref sums i) n) (not (= (vector-ref sums i) i)) 
                  (= (vector-ref sums (vector-ref sums i)) i))
             (begin
               (vector-set! res i i)
               (vector-set! res (vector-ref sums i) (vector-ref sums i))
               (loop res (+ 1 i))))
            (else
              (loop res (+ i 1)))))))

(display (sum-of-amicable-pairs 10000))
(newline)

Python代码：

def amicable_pairs(n):
    """returns sum of all amicable pairs under n. See project euler for 
    definition of an amicable pair"""
    div_sum = [None]*n
    amicable_pairs_set = set()
    for i in range(n):
        div_sum[i] = sum([j for j in range(1, i/2 + 1) if i%j == 0])
    for j in range(n):
        if div_sum[j] < n and div_sum[div_sum[j]] == j and div_sum[j] != j:
            amicable_pairs_set.add(j)
            amicable_pairs_set.add(div_sum[j])
    #print sum(amicable_pairs_set)
    return sum(list(amicable_pairs_set))

Answer 1

我将首先优化python代码，然后将其转换为方案(对不起，无法找到用于Windows的scheme编译器)。这里的python解决方案速度快了100到200倍(这个想法基于Eratosthenes算法的筛网)：

python25\python 21.py
amicable_pairs      : 31626  Time (s): 2.313000
amicable_pairs_fast : 31626  Time (s): 0.015000

python26\python 21.py
amicable_pairs      : 31626  Time (s): 1.969000
amicable_pairs_fast : 31626  Time (s): 0.016000

python27\python 21.py
amicable_pairs      : 31626  Time (s): 1.782000
amicable_pairs_fast : 31626  Time (s): 0.000000

python32\python 21.py
amicable_pairs      : 31626  Time (s): 3.157000
amicable_pairs_fast : 31626  Time (s): 0.015000

pypy\pypy 21.py
amicable_pairs      : 31626  Time (s): 0.157000
amicable_pairs_fast : 31626  Time (s): 0.015000

。

 import time

"""

    http://projecteuler.net/problem=21
    Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
    If d(a) = b and d(b) = a, where a !=  b, then a and b are an amicable pair and each of a and b are called amicable numbers.

    For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284.
    The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
    Evaluate the sum of all the amicable numbers under 10000.

    http://codereview.stackexchange.com/questions/13476/a-little-scheme-programming-challenge

"""

def amicable_pairs(n):
    """returns sum of all amicable pairs under n. See project euler for
    definition of an amicable pair"""
    div_sum = [None]*n
    amicable_pairs_set = set()
    for i in range(n):
        div_sum[i] = sum([j for j in range(1, int(i/2) + 1) if i%j == 0])
    for j in range(n):
        if div_sum[j] < n and div_sum[div_sum[j]] == j and div_sum[j] != j:
            amicable_pairs_set.add(j)
            amicable_pairs_set.add(div_sum[j])
    #print sum(amicable_pairs_set)
    return sum(list(amicable_pairs_set))

def amicable_pairs_fast(n):

    div_sum = [1]*n
    for i in range(2, int(n/2) + 1):
        for j in range(i, n, i):
            if j != i:
                div_sum[j] += i
    total = 0
    for i in range(1, n):
        s = div_sum[i]
        if s < n:
           s1 = div_sum[s]
           if  s1 == i and s != i:
              total += s1
    return total

t = time.time()
print("amicable_pairs      : %d " % amicable_pairs(10000) + " Time (s): %f " % (time.time()-t))

t1 = time.time()
print("amicable_pairs_fast : %d " % amicable_pairs_fast(10000) + " Time (s): %f " % (time.time()-t1))

Answer 2

首先，python代码为它的amicable_pair_set使用了一个集合，在这里，当您需要添加到集合时，使用一个大的向量并将n‘to元素设置为n。如果您的方案没有集合库，那么这是一种模仿集合的合理方法；但是，这种情况不需要真正的集语义。您可以使用一个简单的列表，因此您的命名let变成：

(let loop ((res '())
           (i 0))
      (cond
       ((= i n) (reduce + 0 res))
       ((and (< (vector-ref sums i) n) (not (= (vector-ref sums i) i)) 
         (= (vector-ref sums (vector-ref sums i)) i))
    (loop (cons i res) (+ 1 i)))
       (else
    (loop res (+ i 1)))))

这使它接近python代码，但是您可以更进一步，让res成为一个整数累加器，添加到它而不是缩进它，这样就不需要在末尾添加列表了。当然，对python版本也可以进行同样的优化。

不幸的是，我优化了代码中运行快速的部分:-)。当sums向量被填充时，真正的工作是在上面完成。因为这是一个非常直接的翻译，所以我认为这要归功于chibi的方案实现，而不是您所使用的python的任何实现(例如，PyPy可能会更快)。我使用的是jit编译的球拍方案。调用您的代码将为我返回一个以680 me为单位的答案。用默认的python2.7.3编译器调用它，我的结果是~1400 me。

这里有一个版本，它只计算所需数字的适当除数之和，然后将它们存储起来供将来使用。基本上是回忆录结果。对我来说，第一次运行稍微快一些

(define d
  (let ((cache (make-vector 10000 #f)))
    (lambda (n)
      (or (vector-ref cache n)
      (let ((val (reduce + 0 (filter (lambda (d) (= 0 (remainder n d)))
                     (iota (quotient n 2) 1)))))
        (vector-set! cache n val)
        val)))))

(define (sum-of-amicable-pairs n)
  (let loop ((a 0)
         (sum 0))
    (if (< a n)
      (let ((b (d a)))
        (loop (+ a 1)
          (if (and (< a b n) (= (d b) a))
              (+ sum a b)
              sum)))
      sum)))

(time (sum-of-amicable-pairs 10000))