6

関数：

リスト lst が与えられると、正確に長さ k のリストの内容のすべての順列が返されます。指定されていない場合は、デフォルトでリストの長さに設定されます。

(defun permute (lst &optional (k (length lst)))
  (if (= k 1)
   (mapcar #'list lst)
   (loop for item in lst nconcing
     (mapcar (lambda (x) (cons item x)) 
             (permute (remove-if (lambda (x) (eq x item)) lst) 
                      (1- k))))))

問題: sbcl に接続された emacs で SLIME を使用していますが、まだあまりカスタマイズしていません。この関数は、lst = '(1 2 3 4 5 6 7 8) k = 3 のような小さな入力で問題なく動作します。これは、実際にはほとんどの場合に使用されます。ただし、大きな入力で2回続けて呼び出すと、2番目の呼び出しは返されず、sbclも上に表示されません。これらは REPL での結果です。

CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))
Evaluation took:
12.263 seconds of real time
12.166150 seconds of total run time (10.705372 user, 1.460778 system)
[ Run times consist of 9.331 seconds GC time, and 2.836 seconds non-GC time. ]
99.21% CPU
27,105,349,193 processor cycles
930,080,016 bytes consed

(2 7 8 3 9 1 5 4 6 0)
CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))

そして、2回目の呼び出しから戻ってくることはありません。なんらかの理由でガベージコレクターに恐ろしいことをしているとしか思えませんが、何がわかりません。誰にもアイデアはありますか？

4

3 に答える 3

4

コードで間違っていることの 1 つは、EQ の使用です。EQ は ID を比較します。

EQは数字を比較するためのものではありません。2 つの数値の EQ は、真または偽になります。

ID、数値、または文字で比較する場合は、EQL を使用します。EQではありません。

実際

(remove-if (lambda (x) (eql x item)) list)

ただです

(remove item list)

コードの場合、EQ バグは、リストから実際に番号を削除せずに、再帰呼び出しで permute が呼び出されることを意味する可能性があります。

それ以外では、SBCL はメモリ管理で忙しいだけだと思います。私の Mac の SBCL は大量のメモリ (1 GB 以上) を獲得し、何かをするのに忙しかった。しばらくして、結果が計算されました。

あなたの再帰関数は大量の「ガベージ」を生成します。LispWorks によると: 1360950192 バイト

たぶん、より効率的な実装を思いつくことができますか?

更新：ゴミ

Lisp はいくつかの自動メモリ管理を提供しますが、プログラマが空間効果について考えることから解放されるわけではありません。

Lisp はスタックとヒープの両方を使用してメモリを割り当てます。ヒープは、GC の特定の方法で構造化される場合があります。たとえば、ジェネレーション、ハーフ スペース、および/または領域です。正確なガベージ コレクタと「保守的な」ガベージ コレクタ (Intel マシンの SBCL で使用) があります。

プログラムを実行すると、さまざまな効果が見られます。

  1. 通常の再帰手順は、スタックにスペースを割り当てます。問題: 通常、スタック サイズは固定されています (一部の Lisp ではエラー ハンドラでスタック サイズを増やすことができますが)。

  2. プログラムは大量のメモリを割り当て、大きな結果を返す場合があります。PERMUTE はそのような関数です。非常に大きなリストを返す可能性があります。

  3. プログラムがメモリを割り当てて一時的に使用すると、ガベージ コレクタがそれをリサイクルできます。プログラムが大量の固定メモリを使用しない場合でも、作成と破棄の速度は非常に高くなる可能性があります。

ただし、さらに問題があります。しかし、上記のそれぞれについて、Lisp プログラマー (およびガベージ コレクションを使用する言語実装を使用する他のすべてのプログラマー) は、それを処理する方法を学ばなければなりません。

  1. 再帰を反復に置き換えます。再帰を末尾再帰に置き換えます。

  2. 結果の必要な部分のみを返し、完全なソリューションを生成しないでください。n 番目の順列が必要な場合は、すべての順列ではなく、それを計算します。オンデマンドで計算される遅延データ構造を使用します。ストリームに似ているが効率的な計算を使用できる SERIES のようなものを使用します。SICP、PAIP、およびその他の高度な Lisp の本を参照してください。

  3. リソース マネージャーでメモリを再利用します。オブジェクトを常に割り当てるのではなく、バッファを再利用します。一時的な (短命の) オブジェクトを収集するための特別なサポートを備えた効率的なガベージ コレクターを使用します。新しいオブジェクトを割り当てる代わりに、オブジェクトを破壊的に変更することが役立つ場合もあります。

上記は、実際のプログラムのスペースの問題を扱っています。理想的には、当社のコンパイラまたはランタイム インフラストラクチャが、これらの問題に対処するための自動サポートを提供する場合があります。しかし、実際にはこれはうまくいきません。ほとんどの Lisp システムはこれに対処するための低レベルの機能を提供し、Lisp は変更可能なオブジェクトを提供します - 実際の Lisp プログラムの経験から、プログラマーはそれらを使用してプログラムを最適化したいと考えていることがわかっているからです。タービン ブレードの形状を計算する大規模な CAD アプリケーションがある場合、非可変メモリに関する理論的/純粋な見方は適用されません。

于 2010-02-25T08:56:29.663 に答える
2

ほとんどのプラットフォームの SBCL は、世代別ガベージ コレクターを使用します。つまり、一定数以上のコレクションが残っている割り当てられたメモリは、コレクションの対象と見なされることはほとんどありません。特定のテストケースのアルゴリズムは非常に多くのガベージを生成するため、GC を何度もトリガーするため、実際の結果 (関数の実行時間全体を生き残る必要があることは明らかです) が保持されます。つまり、最終世代に移動されます。またはまったくありません。したがって、2 回目の実行では、32 ビット システムの標準設定では、ヒープが不足します (512 MB、ランタイム オプションで増やすことができます)。

古いデータは、 を使用して手動でコレクターをトリガーすることにより、ガベージ コレクションを実行できます(sb-ext:gc :full t)。これは明らかに実装依存です。

于 2010-02-25T12:06:42.300 に答える
1

出力を見ると、slime-repl ですね。

"*inferior-lisp*" バッファに変更してみてください。おそらく、SBCL が ldb (組み込みの低レベル デバッガ) に落ちていることがわかります。ほとんどの場合、コール スタックを吹き飛ばすことができました。

于 2010-02-25T10:56:56.063 に答える