4

リスト'aのすべての要素をリスト'bから除外し、フィルタリングされた'bを返します。これは私の機能です：

(defun filter (a b)
  "Filters out all items in a from b"
    (if (= 0 (length a)) b
      (filter (remove (first a) a) (remove (first a) b))))

私はLispに不慣れで、どのように削除するのかわかりません。このフィルターはどのような時間で実行されますか？

4

4 に答える 4

10

確認するには、次の 2 つの方法があります。

  • データでテストできます

  • ソースコードを分析できます

ソースコードを見てみましょう。

  • リストはリンクされたコンスセルで構築されています

  • 長さはリストを一度歩く必要があります

  • FILTER の再帰呼び出しごとに、a の長さを計算します。悪い！

    (代わりにENDPを使用してください。)

  • REMOVE は、リストを 1 回通過する必要があります

  • 再帰呼び出しごとに REMOVE を 2 回計算します。まずい!

    ( で REMOVE を使用する代わりにa、REST で再帰します。)

  • FILTER の呼び出しは、必ずしも最適化されたテール コールとは限りません。一部の実装では、テール コールを最適化する必要があることをコンパイラに伝える必要がある場合があります。一部の実装では、テール コールの最適化は使用できません。そうでない場合は、十分な長さのリストでスタック オーバーフローが発生します。

    (該当する場合は、再帰の代わりに、DO、DOLIST、DOTIMES、LOOP、REDUCE、MAPC、MAPL、MAPCAR、MAPLIST、MAPCAN、MAPCON などのループ構造を使用してください。)

要約: これは非常に単純なコードで、パフォーマンスが低下しています。

Common Lisp はこれを組み込みで提供します: SET-DIFFERENCE はあなたが望むことを行うべきです。

http://www.lispworks.com/documentation/HyperSpec/Body/f_set_di.htm#set-difference

于 2010-07-27T07:33:27.177 に答える
1

Rainer Joswigが言うように、私はこの関数を書きません。標準はすでにを提供していますSET-DIFFERENCE。それでも、関数の実装を提供する必要がある場合は、これを使用します。

(defun filter (a b)
  (let ((table (make-hash-table)))
    (map 'nil (lambda (e) (setf (gethash e table) t)) a)
    (remove-if (lambda (e) (gethash e table)) b)))

このようにすることで、いくつかの利点が得られます。最も重要なのは、1b回だけトラバースすることです。ハッシュテーブルを使用してどの要素が含まれているかを追跡すると、が長いa場合にパフォーマンスが大幅に向上する可能性がありaます。

MAPまた、などの汎用シーケンス関数を使用REMOVE-IFすると、この関数を文字列やベクトル、リストで使用できるため、標準SET-DIFFERENCE関数よりも優れています。このアプローチの主な欠点は:TEST、EQLCLハッシュテーブルが事前定義された少数の等式述語（EQ、、正確には）。EQLEQUALEQUALP

于 2010-07-29T19:11:20.620 に答える
1

Common Lisp は末尾呼び出しの最適化を (標準に従って)サポートしていないため、(実装によっては) ひどい呼び出しスタックでメモリが不足する可能性があります。

于 2010-07-27T07:05:52.360 に答える
1 
(defun filter (a b)
  "Filters out all items in a from b"
    (if (not (consp a)) b
      (filter (rest a) (rest b))))
于 2014-11-03T12:08:30.840 に答える