29

先日、プロローグでパズルを解いていて、別のプログラミング言語を使っていたら、ハッシュテーブル/辞書を使っていただろうと気づきましたが、私が知る限り、これはプロローグでは実際には不可能です。

だから私の最初の質問は、ハッシュテーブルのパフォーマンス特性を備えた辞書のようなデータ構造をサポートするプロローグはありますか？

次に、ほとんどのプロローグは述語を格納するためにハッシュテーブルを使用するため、ファクトをアサートおよびリトラクトするラッパー述語を記述して、述語の基になるハッシュテーブルを活用する辞書インターフェイスを作成できることに気付きました。しかし、ハッシュテーブルのパフォーマンス特性を取得するのでしょうか、それともインターフェイスがパフォーマンスを低下させるオーバーヘッドを追加するのでしょうか。

4

5 に答える 5

10

私はちょうどそれを見つけました：

SWI-Prologバージョン7は、メンバーにアクセスするための具体的な最新の構文と関数表記、およびユーザーが定義したアクセス関数を備えた抽象オブジェクトとしてdictを導入しています。

構文は次のとおりです。

Tag{Key1:Value1, Key2:Value2, ...}

詳細については、 Dicts：名前付き引数を持つ構造体を参照してください。

ご了承ください ：

  • これらは言語の一級市民です
  • dict間の統一のセマンティクスは将来変更される可能性があります
  • 以前はcons-ingに使用されていた./2演算子は、次のような式を介してdictメンバーにアクセスするために再利用されました。point{x:1,y:2}.x
  • ディクトは破壊的に変更できますが、機能しないことは言うまでもなく、「非論理的」であるため、これはお勧めできません。
  • 現在の基本的な実装は、「ファンクターを使用した複合用語dictです。最初の引数はタグです。残りの引数は、ソートされたキーと値のペアの配列を作成します」

現在の（2019）実装の操作の時間計算量は、SWI Prologマニュアルの「5.4.5：dictsに関する実装ノート」に記載されています。

ディクトは現在、ファンクターを使用して複合語として表されてい dictます。最初の引数はタグです。残りの引数は、ソートされたキーと値のペアの配列を作成します。この表現はコンパクトで、優れた局所性を保証します。ルックアップはorderlog （N）ですが、値の追加、値の削除、および他のdictとのマージの順序はNです。主な欠点は、大きなdictで値を変更すると、メモリと時間の両方の点でコストがかかることです。

将来のバージョンでは、キーを別の構造で共有するか、バイナリツリーを使用してより安価な更新を可能にする可能性があります。問題の1つは、表現を標準的に維持するか、代替表現を補正するために統合を拡張する必要があることです。

そしてまた

SWI-Prologdictは組み込みおよびSWI-Prolog拡張機能です。別の方法はlibrary(assoc)、ライブラリを介してAVLツリーに基づくマップを提供することです（したがって、他の実装で利用できる可能性があります）。

于 2014-11-23T01:07:58.980 に答える
8

一部のProlog環境には、辞書の作成と編集に使用できる連想リストがあります。

編集：

外国語で述語を実装することで、パフォーマンスを向上させることができる場合があります。次に例を示します。

于 2009-08-23T17:20:42.747 に答える
3

私はPrologの男ではありません（ただの外部のオブザーバーです）が、私はこれを見つけました：

http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html

「プロローグ有限マップバランスツリー」を検索したとき。アソシエーションリストの代替実装だと言っています。

（私がこれを考えた理由：連想リストやハッシュテーブルの代わりに、純粋に関数型言語であるHaskellでは、（永続的な）辞書や有限マップにツリーを使用するのが一般的です。ルックアップもO（log（N））です。を参照してください。バランスの取れたツリーを使用したマップの実装に関するいくつかのリファレンスについては、 Data.Mapを参照してください。）

于 2009-08-25T05:38:08.643 に答える
3

以下のコメントは、おおまかに「より具体的」から「より一般的」の順に質問に対応しています。

まず、具体的なコメントに対処します。

私はハッシュテーブル/辞書を利用したでしょうが、私が知る限り、これはPrologでは実際には不可能です。

すべての深刻なProlog実装では、たとえばを使用して、Prolog用語を破壊的に変更できますsetarg/3。を使用するarg/3とsetarg/3、用語の各引数にO（1）アクセスできます。これは、システムが用語のアリティに任意の制限を課していないことを前提として、他の言語とまったく同じようにハッシュテーブルを実装するのに十分です。

すべての用語で予期しない用語のコピーと共有を考慮に入れる必要があるため、これを自分で行うことはお勧めできません。代わりに、それを行うためにライブラリに依存します。

どの図書館？私は他の人が書いたことを2番目に説明します。ライブラリをハッシュする代わりに、などのツリーベースのライブラリを使用します。これらは平均的な場合のハッシュほど効率的ではありませんが、次のようになります。library(assoc)library(avl)

  • 彼らはしばしば十分に効率的です
  • それらは非常に予測可能にスケーリングします。最も重要な操作は常にO（log（n））にあります。

また、他の人が書いているように、破壊的な変更は論理プログラミングと互換性がなく、ツリーライブラリには、 ISO Prologで、漸近的に最適な効率で純粋な方法で実装できるという大きな利点があります。

最後に、SWI-Prologのdict拡張機能は、ISOに準拠しておらず、構文的にも準拠していないため、準拠したPrologシステムに移植できません。ISO準拠の方法で中置ドットを追加する方法については、UlrichNeumerkelのコメントを参照してください。

于 2016-02-15T08:38:17.273 に答える
2

SICStus Prologでは、assocまたはavlライブラリのいずれかを使用します。

于 2010-08-16T13:48:18.013 に答える