16

ISO-Prolog は、しばしば「標準用語順序」と呼ばれる用語順序 (7.2) に依存するものを提供しsort/2ますkeysort/2。Elリストを異なる順序でソートする一般的な方法は、そのリストの各要素を何らかの形でペアのリストにマップしてから、XKey-Elそのリストをソートし、最後にキーを射影することです。例として、 をどのようkeysort/2に表現できるかを考えてみましょうsort/2(実装については注を参照してください)。

predsort(C_3, List, SortedList) 多くの場合、このアプローチは、SWIや SICStus などのユーザー定義の順序に依存する一般的な実装固有の並べ替え述語を使用するよりもはるかに高速ですsamsort(O_2, List, SortedList)。

私の質問は次のとおりです。

predsort/3respを使用したソートが行われる場合がありますか。samsort/3いくつかのマッピング、sort/2-ing、および投影に置き換えることはできませんか? 1

わかりやすくするために、有限の基底項に固執することをお勧めします。というのは、無限の基底項は、有限の場合の拡張として必要になるため、完全な辞書式順序を持たないからです。さらに、ISO/IEC 13211-1:1995 の 7.2.1 を考えると、実装に依存する 2 つの異なる変数の場合との変数の比較がどのようになるかは明確ではありません。

7.2.1 変数

XとYが同一でない変数の場合、
X term_precedes は 、ソートされたリスト ( 7.1.6.5、8.10.3.1 j) の作成中に順序が一定のままであることを除いて、Y実装に依存するものとします。

predsort/3そのため、ソートされたリストの作成としてまだ資格があるかどうかは明らかではありません。明らかなことは、 と の間 sort/2に順序が一定のままであることkeysort/2です。

1 @WillNess のおかげで、この射影には少なくともreverse/2線形変換も含まれている必要があります。また、重複した結果と一意の結果の両方を実装できることも意味します (keysort/2実装方法と同様)。

4

3 に答える 3

4

まず、Prolog アトムを「否定」することができます。それを呼びましょうatom_neg/2(ばかげた名前ですが、とにかくばかげたことをします):

atom_neg(A, NK) :-
    atom_codes(A, Cs),
    maplist(negate, Cs, NCs),
    append(NCs, [0], NK).

negate(X, N) :- N is -X.

これを行うことが実際的であると主張しているわけではありませんが、明らかに可能です。

全順序付けは弱い順序付けであり、セットTのキー関数fとfのコドメインでの全順序付けrは、弱い順序付けを定義しますwr(x, y) <==> r(f(x), f(y)) .

(そのコンテキストでの関数のコドメインは、関数が返す値のドメインです。)

私は完全に間違っているかもしれませんが、リレーションの存在にはキーの存在が必要です。リレーションを別のリレーションの観点から定義することはできますが、最終的には、単独でも存在できるもの、つまりキーを比較する必要があります。

ここでのポイントは、キーがソートしたいものと同じドメインにある必要はなく、同じドメインのオブジェクトに対して弱い順序付け (関係) が定義されていることです。Prolog はここで奇妙なことを行います:すべての可能な用語の用語の標準的な順序を定義します。Prolog には、「タイプ」または「ドメイン」の適切な概念もありません。私の直感では、同じドメインに属さないものをソートすることはあまり役に立たないということですが、Prolog は明らかに同意しません。

次の 2 つのケースではキー関数を定義できません。

  1. 比較述語は独自の状態を保持します。
  2. 比較関数を提供するがキー関数を提供しない「不透明な」オブジェクト (たとえば、C で定義) があります。

いずれにせよ、predsort役に立つ可能性がありますatom_neg/2。Will Ness によるソリューションよりも誰も好まないでしょう。ただし、現時点では重大な欠陥が 1 つあります。それは、安定した並べ替えができないことです。SWI-Prolog はすでにこの方法で使用できます。現在の動作を の仕様とドキュメントに追加するだけですpredsort/3。

于 2015-07-25T09:48:23.993 に答える
3

編集: @Boris による回答は、比較のためにアトムを「否定」する方法を示しているため、その場合、私の contr-argument は無効になります。そして、質問の新しい規定はそれを完全に無効にします。

複雑なソート基準の場合、複数のサブキーを配置する必要があります。重複の保持が必要な場合は、並べ替え用に構築された用語で、並べ替えサブキーに続いて、増分インデックスを元の用語の前に付ける必要がありsort/2ます。

ただし、構築されたサブキーの複雑さと数は手に負えなくなる可能性があります。いくつかの領域では昇順または降順で、最初に X でポイントを並べ替え、次に Y でポイントを並べ替えます。他の地域では、最初に Y で、次に X で並べ替えます。

次に、(おそらく計算量が多い) 比較の対数線形数を、標準的な項の順序でのキー構成の線形数と (おそらく軽い) 比較の対数線形数のみに置き換えるという利点を求めることができなくなります。

自明predsort/3なことですが、カスタム比較述語を使用して、アトムのリストを逆にします。

comp(<,A,B):- B @< A.

などは、 「標準的な用語の順序」sort/2で動作する ingでは実行できません(SWI ドキュメントを引用)。数字では符号を反転できますが、名前では反転できません。

reverseおそらく、許可されたアクションに追加したいと思うでしょう。

許可されてsort/4いるため、機能しないものは何もありません。また、安定しているため、二次パス (最初はマイナー基準、次にメジャー基準) によって、二次基準にも対応できます。

于 2015-07-23T22:33:29.860 に答える