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

最後に、base2 と base10 のパリンドロームである max 以下のすべての 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))]
    )
  )

これら 2 つの最後の関数のいずれかを 1000000 に適用すると、完了するまでに 10 秒以上かかります。再帰バージョンは、アキュムレータ バージョンよりも少し高速に見えますが、違いはごくわずかです。

このコードを改善する方法はありますか、それとも、これが Racket が特に適していない数計算のスタイルであることを受け入れる必要がありますか?

これまでのところ、integer->lon を同様の integer->vector に置き換える可能性を検討してきました。vector-append は append よりも高速であると予想されますが、後で逆を適用する必要があることに行き詰まっています。

4

2 に答える 2

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、
  • など、数値が大きくなりすぎるまで。

このリストはすべての 2 進回文であり、そのうちの一部のみが 10 進回文になります。ビットいじり手法を使用してバイナリ回文を生成できる場合 (つまり、実際に整数を操作している場合)、それらを文字列に書き込むのは簡単で、文字列が回文であるかどうかを確認する方が、リストが回文です。

于 2013-11-07T04:51:16.707 に答える
1

DrRacket でこれらのタイミングを実行していますか? 特に、たまたまデバッグやプロファイリングをオンにしている場合は、IDE の動作がかなり遅くなるため、コマンド ラインからこれらのテストを実行することをお勧めします。

また、通常はブルート フォース アプローチを改善できます。たとえば、奇数のみを考慮する必要があるとここで言うことができます。これは、2 進数として表現した場合、偶数は決して回文にならないためです (末尾の 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

Racket プロファイリングの経験が豊富な人は、より迅速な解決策を思いつくと確信しています。

そこで、次のヒントをお伝えできます。

NB あなたの10->bin関数は#f値0を返します。返すべきだと思い'(0)ます。

于 2013-11-06T22:36:58.830 に答える