0

スキーム言語を使用して、効率の高い特別なリストを作成したいと思います。例えば:

関数名:make-list
パラメーター:max
(make-list max) -> (1 2 3 4 5 6 7 ... max)

再帰メソッドを使用してこのタスクを完了することができます。

#lang racket

(define (make-list max)
(define lst '())
(define count 1) 
(make-list-helper lst max count))

(define (make-list-helper lst max count) 
 (cond  
 [(> count max) lst]
 [else 
  (set! lst (append lst (list count))) 
  (make-list-helper lst max (add1 count)]))

ただし、この方法は低いと見なすことができます。リスト作成の効率を上げる方法がわかりません。誰かが私を助けることができますか?

4

3 に答える 3

2

重要な原則は、画家のアルゴリズムであるSchlemielappendを回避することです。これは、リストが長くなるにつれて、繰り返し使用するのに時間がかかります。要素の前に付けるのはO(1)で、追加するのはO(リストの長さ)です。したがって、最も内側のmake-list-helper戻り値を単一のリストにし、再帰で要素を付加するために(max)使用します。cons

(私は反復的な解決策を好みますが、私は一般的なリスパーなので、スキームのために何かを主張することは避けたほうがいいです)。

学習の楽しさを損なうことを避けるためのコードは含まれていません。

于 2013-01-10T17:40:01.403 に答える
2
(define (make-list max)
  (let f ((i max)(a '()))
    (if (zero? i)
        a
        (f (- i 1) (cons i a)))))

これは、反復のための簡単な演習のようです。

上記は簡単で、Schemeのどこでも使用できます。

スニペット全体がどのように機能するかを理解してください。

于 2013-01-10T17:46:13.447 に答える
1

「効率」のもう1つの定義は、最小限のコードでプロシージャを作成することです。そのことを念頭に置いて、質問の最短の解決策は、既存の手順を使用して問題を解決することです。たとえば、次の場合max = 10

(define (make-list max-val)
  (build-list max-val add1))

(make-list 10)
=> '(1 2 3 4 5 6 7 8 9 10)

上記は、Racketの一部であるビルドリスト手順を利用しています。

0fromからtoまでの整数にprocを(sub1 n)順番に適用して、n個の要素のリストを作成します。lstが結果のリストである場合、(list-ref lst i)はによって生成される値(proc i)です。

ラケットの場合のさらに別のオプションは、反復と理解を使用することです。

(define (make-list max-val)
  (for/list ([i (in-range 1 (add1 max-val))]) i))

(make-list 10)
=> '(1 2 3 4 5 6 7 8 9 10)

いずれにせよ、プロシージャが言語のコアライブラリの一部であることを考えると、それらのパフォーマンスは非常に優れていると確信できます。プロファイラーがボトルネックであると示さない限り、それについて心配する必要はありません。

于 2013-01-10T21:19:15.267 に答える