提高将数字转换为列表以及将 base10 转换为 base2 的性能

本文介绍了提高将数字转换为列表以及将 base10 转换为 base2 的性能的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

Many Project Euler problems require manipulating integers and their digits, both in base10 and base2. While I have no problem with converting integers in lists of digits, or converting base10 into base2 (or lists of their digits), I often find that performance is poor when doing such conversions repeatedly.

这是一个例子:

首先，这是我的典型转化:

First, here are my typical conversions:

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

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

Next, I need a function to test whether a list of digits is a palindrome

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

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

Finally, I need to sum all base10 integers below some max that are palindromes in base2 and base10. Here's the accumulator-style function:

(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 多秒才能完成.递归版本似乎比累加器版本快一点，但差异可以忽略不计.

When I apply either of these two last functions to 1000000, I takes well over 10 seconds to complete. The recursive version seems a bit quicker than the accumulator version, but the difference is negligible.

有什么方法可以改进这段代码，还是我必须接受这是 Racket 不太适合的数字运算风格?

Is there any way I can improve this code, or do I just have to accept that this is the style of number-crunching for which Racket isn't particularly suited?

到目前为止，我已经考虑了用一个类似的 integer->vector 替换 integer->lon 的可能性，因为我希望 vector-append 比 append 快，但后来我被困在需要应用 reverse 之后.

So far, I have considered the possibility of replacing integer->lon by a similar integer->vector as I expect vector-append to be faster than append, but then I'm stuck with the need to apply reverse later on.

推荐答案

您是否有机会在 DrRacket 中运行这些计时?IDE 会大大降低运行速度，尤其是当您碰巧打开了调试和/或分析时，因此我建议您从命令行进行这些测试.

Are you running these timings in DrRacket by any chance? The IDE slows down things quite a bit, especially if you happen to have debugging and/or profiling turned on, so I'd recommend doing these tests from the command line.

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

Also, you can usually improve the brute-force approach. For example, you can say here that we only have to consider odd numbers, because even numbers are never a palindrome when expressed as binaries (a trailing 0, but the way you represent them there's never a heading 0). This divides the execution time by 2 regardless of the algorithm.

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

Your code runs on my laptop in 2.4 seconds. I wrote an alternative version using strings and build-in functions that runs in 0.53 seconds (including Racket startup; execution time in Racket is 0.23 seconds):

#!/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

而且我很确定在 Racket 分析方面有更多经验的人会想出更快的解决方案.

and I'm pretty sure that people with more experience in Racket profiling will come up with faster solutions.

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

So I could give you the following tips:

考虑如何改进蛮力方法
更好地了解您的语言.一些构造比其他构造更快，没有明显的原因
- 参见 http://docs.racket-lang.org/guide/performance.html 和 http://jeapostrophe.github.io/2013-08-19-reverse-post.html
注意你的 10->bin 函数返回 #f 的值 0，我想它应该返回 '(0).
N.B. Your 10->bin function returns #f for the value 0, I guess it should return '(0).
这篇关于提高将数字转换为列表以及将 base10 转换为 base2 的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！