3

Clojure は本当に私の興味をかき立てたので、それに関するチュートリアルを始めました: http://java.ociweb.com/mark/clojure/article.html

「Set」の下に記載されている次の 2 行を検討してください。

(def stooges (hash-set "Moe" "Larry" "Curly")) ; not sorted
(def more-stooges (conj stooges "Shemp")) ; -> #{"Moe" "Larry" "Curly" "Shemp"}

私が最初に考えたのは、2 番目の操作が完了するまで一定の時間がかかるはずだということでした。そうでなければ、関数型言語はオブジェクト指向言語よりもほとんど利点がないかもしれません。[ほぼ]空のセットから始めて、それにデータを入力して縮小する必要があることは容易に想像できます。したがって、新しい結果をより多くの手先に割り当てる代わりに、それ自体に再割り当てすることができます。

さて、関数型言語のすばらしい可能性により、副作用は気にする必要がなくなりました。そのため、これまでお互いに設定stoogesして動作するべきではありません。more-stoogesしたがって、 の作成more-stoogesは線形操作であるか、共通のバッファー (Java の のStringBufferような) を共有しますが、これは非常に悪い考えのように見え、不変性と競合します (その後stooges、要素を 1 つずつドロップする可能性があります)。

私はおそらくここで車輪を再発明しています。空のセットから始めて一度に 1 つずつ成長させるのではなく、最大数の要素から始めて、空のセットになるまで一度に 1 つずつ削除すると、hash-setパフォーマンスが向上するようです。clojure

上記の例はあまり実用的ではないように見えたり、回避策があったりするかもしれませんが、Java/C#/Python/etc のようなオブジェクト指向言語. 一度に1つまたはいくつかの要素を拡大または縮小しても問題はなく、高速に実行できます。

不変性を保証する（または約束するだけの）[関数型]言語では、セットをそれほど速く成長させることはできません。それを回避するのに役立つ別の慣用句はありますか?

に精通している人のためにPython、セット内包表記と同等のループ アプローチについて言及します。2 つの実行時間はわずかに異なりますが、それはC, Python, インタープリターの相対的な速度に関係しており、複雑さに起因するものではありません。私が見ている問題は、セット内包表記がより良いアプローチであることが多いということですが、常に最良のアプローチであるとは限りません。

質問が明確でない場合はお知らせください。

4

2 に答える 2

8

コアの不変データ構造は、私にとっても言語の最も魅力的な部分の 1 つです。彼らはこの質問に答えるために多くのことをしており、リッチはこのビデオで本当に素晴らしい仕事をしています:

http://blip.tv/file/707974

コアデータ構造:

  • 実際には完全に不変です
  • 古いコピーも不変です
  • 古いコピーのパフォーマンスは低下しません
  • アクセスは一定です (実際には制限 <= 定数)
  • すべてが効率的な追加、連結 (リストと seq を除く)、およびチョッピングをサポートします。

彼らはこれをどのように行うのですか？

  • 秘密:ボンネットの下にはほとんどすべての木があります (実際にはトライです)。

しかし、本当にその場で何かを編集したい場合はどうすればよいでしょうか?

  • clojure のトランジェントを使用して構造をその場で編集し、それを共有する準備ができたら (一定時間で) 不変バージョンを生成できます。

少し背景として: Trieは、キーのすべての共通要素がツリーの一番上まで持ち上げられるツリーです。clojure のセットとマップは、インデックスが探しているキーのハッシュであるトライを使用します。次に、ハッシュを小さなチャンクに分割し、各チャンクをハッシュ トライの 1 つのレベルのキーとして使用します。これにより、新しいマップと古いマップの両方の共通部分を共有でき、アクセス時間は制限されます。これは、入力として使用されるハッシュのサイズが固定されているため、固定数のブランチしか存在できないためです。

これらのハッシュ試行を使用すると、他の多くの永続的なデータ構造で使用される再調整中の大幅な速度低下を防ぐこともできます。したがって、実際にはかなり一定のウォールクロックアクセス時間が得られます。

(比較的短い)_本を本当にお勧めします: Purely Functional Data Structures その中で、彼は多くの非常に興味深い構造と概念をカバーしており、「償却の削除」など、キューへの真の一定時間アクセスを可能にします。遅延永続キューのようなものです。著者はここでpdfで無料のコピーを提供しています

于 2010-09-09T22:31:08.660 に答える
3

Clojure のデータ構造は永続的です。つまり、データ構造は不変ですが、構造共有を使用して効率的な「変更」をサポートします。より完全な説明については、Clojure ドキュメントの不変データ構造に関するセクションを参照してください。特に、

具体的には、これは完全なコピーを使用して新しいバージョンを作成できないことを意味します。これには線形時間が必要になるためです。必然的に、永続的なコレクションはリンクされたデータ構造を使用して実装されるため、新しいバージョンは以前のバージョンと構造を共有できます。

これらの 投稿やRich Hickey の講演では、永続データ構造の実装の概要がよくわかります。

于 2010-09-09T22:30:01.017 に答える