2

许多Project Euler问题都需要在 base10 和 base2 中处理整数及其数字。虽然我在转换数字列表中的整数或将 base10 转换为 base2（或它们的数字列表）方面没有问题，但我经常发现重复进行此类转换时性能很差。

这是一个例子：

首先，这是我的典型转换：

#lang racket
(define (10->bin num)
  (define (10->bin-help num count)
    (define sq
      (expt 2 count))
    (cond
      [(zero? count) (list num)]
      [else (cons (quotient num sq) (10->bin-help (remainder num sq) (sub1 count)))]
      )
    )
  (member 1 (10->bin-help num 19)))

(define (integer->lon int)
  (cond
    [(zero? int) empty]
    [else (append (integer->lon (quotient int 10)) (list (remainder int 10)))]
    )
  )

接下来，我需要一个函数来测试一个数字列表是否是回文

(define (is-palindrome? lon)
  (equal? lon (reverse lon)))

最后，我需要将低于某个最大值的所有 base10 整数相加，这些整数是 base2 和 base10 中的回文数。这是累加器样式的函数：

(define (sum-them max)
  (define (sum-acc count acc)
    (define base10
      (integer->lon count))
    (define base2
      (10->bin count))
    (cond
      [(= count max) acc]
      [(and
           (is-palindrome? base10)
           (is-palindrome? base2))
          (sum-acc (add1 count) (+ acc count))]
         [else (sum-acc (add1 count) acc)]))
  (sum-acc 1 0))

和常规递归版本：

(define (sum-them* max)
  (define base10
    (integer->lon max))
  (define base2
    (10->bin max))
  (cond
    [(zero? max) 0]
    [(and
      (is-palindrome? base10)
      (is-palindrome? base2))
     (+ (sum-them* (sub1 max)) max)]
    [else (sum-them* (sub1 max))]
    )
  )

当我将最后两个函数中的任何一个应用于 1000000 时，我需要 10 多秒才能完成。递归版本似乎比累加器版本快一点，但差异可以忽略不计。

有什么办法可以改进这段代码，还是我只需要接受这是 Racket 并不特别适合的数字运算风格？

到目前为止，我已经考虑过用类似的 integer->vector 替换 integer->lon 的可能性，因为我希望 vector-append 比 append 更快，但是我坚持需要稍后应用 reverse。

4

2 回答 2

1

您是否有机会在 DrRacket 中运行这些计时？IDE 会减慢速度，特别是如果您碰巧打开了调试和/或分析功能，因此我建议您从命令行进行这些测试。

此外，您通常可以改进蛮力方法。例如，您可以在这里说我们只需要考虑奇数，因为偶数在表示为二进制时永远不是回文（尾随 0，但您表示它们的方式永远不会有标题 0）。无论算法如何，这都会将执行时间除以 2。

您的代码在 2.4 秒内在我的笔记本电脑上运行。我使用字符串和内置函数编写了一个替代版本，运行时间为 0.53 秒（包括 Racket 启动；Racket 中的执行时间为0.23 秒）：

#!/usr/bin/racket
#lang racket

(define (is-palindrome? lon)
  (let ((lst (string->list lon)))
    (equal? lst (reverse lst))))

(define (sum-them max)
  (for/sum ((i (in-range 1 max 2))
             #:when (and (is-palindrome? (number->string i))
                         (is-palindrome? (number->string i 2))))
    i))

(time (sum-them 1000000))

产量

pu@pumbair: ~/Projects/L-Racket  time ./speed3.rkt
cpu time: 233 real time: 233 gc time: 32
872187

real    0m0.533s
user    0m0.472s
sys     0m0.060s

而且我很确定在球拍分析方面有更多经验的人会提出更快的解决方案。

所以我可以给你以下提示：

注意你的10->bin函数返回#f值0，我猜它应该返回'(0)。

于 2013-11-06T22:36:58.830 回答
1

使您现有的代码更高效

您是否考虑过使用 Racket 的任何按位运算来获取位列表？例如，

(define (bits n)
  (let loop ((n n) (acc '()))
    (if (= 0 n) 
        acc
        (loop (arithmetic-shift n -1) (cons (bitwise-and n 1) acc)))))

> (map bits '(1 3 4 5 7 9 10))
'((1) (1 1) (1 0 0) (1 0 1) (1 1 1) (1 0 0 1) (1 0 1 0))

看看这是否会加快速度会很有趣。我希望它会有所帮助，因为您的10->bin过程当前调用 expt、quotient和remainder，而根据编译器使用的表示，位移可能会更有效。

您integer->lon还使用了比所需更多的内存，因为append在每一步都复制了大部分结果。这很有趣，因为您已经在bin->10. 像这样的东西更有效：

(define (digits n)
  (let loop ((n n) (acc '()))
    (if (zero? n)
        acc
        (loop (quotient n 10) (cons (remainder n 10) acc)))))

> (map digits '(1238 2391 3729))
'((1 2 3 8) (2 3 9 1) (3 7 2 9))

更有效的方法

说了这么多，也许你应该考虑你正在使用的方法。现在看来，您正在遍历数字 1...MAX，检查每个是否是回文，如果是，则将其添加到总和中。总而言之，这意味着您正在使用 MAX 数字做某事。与其检查回文数，不如直接在一个碱基中生成它们，然后检查它们是否是另一个碱基中的回文数。即，不要检查 1…MAX，而是检查：

  • 1
  • 11
  • 101 和 111
  • 1001 和 1111
  • 10001、10101、11011 和 11111，
  • 依此类推，直到数字太大。

这个列表是所有的二进制回文，只有其中一些是十进制回文。如果您可以使用位旋转技术生成二进制回文（因此您实际上是在使用整数），那么将它们写入字符串很容易，并且检查字符串是否为回文可能比检查列表是否快得多是回文。

于 2013-11-07T04:51:16.707 回答