1

私はこのコードを持っています:

(define tree `(A (B (C)) (D (E)) (C (E))))

(define (prog1 graph)
    (let ([seen `()])
      (define (sub g)
          (cond 
              [(member (car g) seen) `()]
              [else 
               (set! seen (cons (car g) seen))
               (cond
                 [(null? (cdr g)) (list (car g))]
                 [else
                  (cons (car g) (map sub (cdr g)))])])) 
    (delete `() (sub graph))))

(define delete
  (lambda (x y)
      (if (null? y )
            `()
      (if (eqv? (car y) x)
           (delete x (cdr y))
      (cons (car y) (delete x (cdr y)))))))

すべてのノードが 1 回表示される接続グラフを出力します。

ランニング(prog1 tree)

プリント:(A (B (C)) (D (E)))

私はLispでさまざまな深さ優先検索（私がやろうとしていることと似ているもの）を見てきましたが、それらはこれよりもはるかにエレガントに見え、反復アプローチを使用しているものもあります。プログラムがあまり効率的ではないことは承知しています (巨大なツリーでは実行速度がかなり遅くなります)。このコードの効率を改善するにはどうすればよいでしょうか?

ありがとう、ジェームズ

4

2 に答える 2

1

ほとんどの場合、このコードのボトルネックはツリー トラバーサルではなく、memberルックアップです。関数の複雑さはおおよそ O(M*N) のようです。ここで、M は個別のノードの数、N はノードの総数です。M が要因としてこれに入る理由は、線形リストでノードを検索しているためです。これには、リストの長さに比例して時間がかかります(この場合、個別のノードの数に比例します)。

M を取り除く方法は、ルックアップにより効率的なデータ構造を使用することです。たとえば、R6RS はハッシュ テーブルを定義します。

于 2012-12-27T20:13:37.170 に答える
1

このmemberプロシージャは、O(n)呼び出されるたびにリストのルックアップを実行します。これは、セット メンバーシップをすばやくテストするために必要なことではありません。そのため、O(1)要素を追加してコレクション内の要素メンバーシップをテストするための複雑さを提供するデータ構造、理想的にはセット データ構造またはその代わりにハッシュ テーブルを使用する必要があります。たとえば、Racket でこれらの行を置き換えてみてください (または、Scheme インタープリターでデフォルトのハッシュ テーブル実装を使用します)。

(let ([seen `()]) => (let ([seen (make-hash)])

[(member (car g) seen) `()] => [(hash-has-key? seen (car g)) '()]

(set! seen (cons (car g) seen)) => (hash-set! seen (car g) 'ok)

また、一般に、コードで引用符を使用する必要があります。 quasiquotes :'()の代わりに、リンクを参照して違いを理解し、準引用符を使用するのが適切な場合を確認してください。`()

最後に、組み込みのプロシージャを使用できます。remove独自の を実装する必要はありませんdelete。

于 2012-12-27T20:40:18.233 に答える