問題タブ [partial-ordering]

おそらく、小さな例で最もよく説明されています。
関係を考えると

正しい出力は

つまり、特定の関係が成立する順序はすべて有効です。

実装が最も簡単なソリューションに最も興味がありますが、速度と時間の点で最高のO（n）も興味深いものです。

別の質問を読んでいるときに、半順序の問題が発生しました。これを次のテストケースに切り詰めました。

どちらの関数テンプレートでも、オーバーロード解決に入る特殊化の関数タイプはですvoid(int, void*)。しかし、半順序（comeauとGCCによる）は、2番目のテンプレートがより特殊化されていることを示しています。しかし、なぜ？

半順序を見て、質問がある場所を示しましょう。に従ってQ半順序を決定するために使用される一意の構成タイプである可能性があり14.5.5.2ます。

• T1（Qが挿入された）の変換されたパラメータリスト： (Q, typename Const<Q>::type*)。引数のタイプは次のとおりですAT=(Q, void*)
• T2（Qが挿入された）の変換されたパラメータリスト： BT= (Q, void*)、これは引数のタイプでもあります。
• 変換されていないパラメータリストT1：(T, typename Const<T>::type*)
• 変換されていないパラメータリストT2：(T, void*)

C ++ 03はこれを過小評価しているので、私はいくつかの欠陥レポートで読んだ意図を使用しました。上記のT1（私が呼び出した）の変換されたパラメータリストは、 「関数呼び出しからテンプレート引数を推測する」ATの引数リストとして使用されます。14.8.2.1

14.8.2.1AT変換する必要も、それ自体を変換する必要もありBTません（たとえば、参照宣言子を削除するなど）。これは、 /ペア14.8.2.4ごとに独立して型演繹を行います。AP

• ATに対してT2：。ここでの唯一のテンプレートパラメータであり、それはである必要があります。型の演繹は、に対して自明に成功します。{ (Q, T), (void*, void*) }TTQATT2

• BTに対してT1：。それもここにあります。は推論されていないコンテキストであるため、何も推論するために使用されることはありません。{ (Q, T), (void*, typename Const<T>::type*) }TQtypename Const<T>::type*

これが私の最初の質問です：これTは最初のパラメータに推定された値を使用しますか？答えが「いいえ」の場合、最初のテンプレートはより特殊化されています。GCCとComeauの両方が、2番目のテンプレートはより特殊化されていると言っており、それらが間違っているとは思わないため、これは当てはまりません。したがって、「はい」と想定し、に挿入void*しTます。段落（14.8.2.4）には、「推論はペアごとに個別に実行され、結果が結合されます」および「ただし、特定のコンテキストでは、値は型の推論に関与せず、代わりに推定されたテンプレート引数の値を使用します」と記載されています。他の場所または明示的に指定されています。」これも「はい」のように聞こえます。

したがって、すべてのA / Pペアについて、控除も成功します。現在、各テンプレートは少なくとも他のテンプレートと同じように特殊化されています。これは、控除が暗黙の変換にも依存せず、両方向で成功したためです。結果として、呼び出しはあいまいになるはずです。

それで私の2番目の質問：では、なぜ実装は2番目のテンプレートがより専門的であると言うのですか？どの点を見落としましたか？

編集：明示的な特殊化とインスタンス化をテストしましたが、最近のGCCバージョン（4.4）では、特殊化への参照があいまいであると教えてくれましたが、古いバージョンのGCC（4.1）ではそのあいまいさのエラーは発生しません。これは、最近のGCCバージョンでは、関数テンプレートの半順序に一貫性がないことを示しています。

半順序関係を持つアイテムのリストがあります。e、リストは半順序集合と見なすことができます。この質問と同じ方法でこのリストを並べ替えたいと思います。そこで正しく答えられているように、これはトポロジカルソートとして知られています。

問題を解決するためのかなり単純な既知のアルゴリズムがあります。LINQのような実装が必要です。

すでにOrderBy拡張法を使ってみましたが、トポロジカルソートはできないと思います。問題は、IComparer<TKey>インターフェースが半順序を表すことができないことです。これは、Compareメソッドが基本的に3種類の値を返すことができるために発生します。つまり、ゼロ、負、正の3種類の値を返します。つまり、それぞれ、等しい、より小さい、より大きいという意味 です。有効な解決策は、関係のないものを返す方法があった場合にのみ可能です。

私の偏った見方からすると、私が探している答えは、次のIPartialOrderComparer<T>ようなインターフェースと拡張メソッドによって構成されている可能性があります。

これはどのように実装されますか？IPartialOrderComparer<T>インターフェイスはどのようになりますか？別のアプローチをお勧めしますか？見たいです。半順序を表すためのより良い方法があるかもしれませんが、私にはわかりません。

環境：

小さい (現在は 100 未満) ですが、正規表現のコレクションが増えています。特定のテキスト文字列に対して、コレクション内のどの正規表現がテキスト文字列と一致するかを判断するプロセスを最適化したいと考えています。

一部の RE には順序関係があります。たとえば、文字列 $t が /windows/i に一致することがわかっている場合、$t が /windows.*2000/i に一致することもわかっています。したがって、コレクション内の RE に対して $t をテストするとき、/windows.*2000/i に対して $t を既にテストして一致が見つかった場合は、/windows/i のテストをスキップできます (ただし、/windows.*2000/i が一致する場合)。一致しない場合、もちろん/windows/i に対するテストをスキップできません)。

私のコレクションの RE はどれも完全に同等ではないことに注意してください (RE の任意のペアには、一方に一致し、他方に一致しないテキスト文字列が少なくとも 1 つ存在します)。

ストラテジー：

コレクション内の各 RE のノードと、順序関係 (A -> B は「A との一致は B との一致を意味する」という意味) を持つ RE の各ペアの有向エッジを持つ有向グラフ G を構築し、グラフのノードの「最小スパニング セット」(G 内のすべてのノードが S から始まる有向パス上にあるようなノード S の最小セット)。

簡単な部分:

有向非巡回グラフを操作するための自由に利用できるアルゴリズムが多数あります。したがって、グラフ G が RE のコレクションに対して構築されると (G が非巡回であることは明確であることが保証されるはずです)、G の最小スパン集合を見つけるための適切なアルゴリズムを見つけるのにそれほど苦労することはないと思います。

助けが必要な場所:

コレクション内の RE 間のすべての順序関係を見つける効率的な方法を見つけたいと考えています。また、コレクション内の 2 つの RE が同等でないことを確認するためにも必要です (新しい RE が同じであるため、これを自動的に検証する方法が必要になります)。追加した）。

したがって、私の (基本的にランダムな) Web 検索では、2 つの RE 間に存在する順序関係 (存在する場合) を計算する合理的な方法が実際に存在するというもっともらしい主張が少なくとも 1 つ見つかりましたが、完全なアルゴリズムの説明はまだ見つかっていません。

合理的に効率的で、自由に利用でき、(理想的には) 一般的なスクリプト言語または C/C++ のいずれかで実装されている (RE を比較するための) 既存の実装を知っている人はいますか?

依存関係のリストがあります（またはサイクルのないDAGの方が良いです）：

入力（例）：

私が探しているのは、「アイテムの最良の*並列注文は何ですか？」です。

*最良の意味：最大同時実行レベル

結果（例）：

最善のアプローチは、依存関係に基づいて順序を取得するための擬似コードのようですが、これに関する基本的なアルゴリズムが欠けていると思います。

次のコード

Python 2では正常に動作しますが、Python3ではエラーが発生します。

とに対してのみ機能し==ます!=。

ここに私の問題があります：私は（空ではないがおそらく明確ではない）セットs_iのシーケンスSを持っており、各s_iについて、S内のセットs_j（i≠j）がs_iのサブセットである数を知る必要があります。

また、インクリメンタル パフォーマンスも必要です。すべてのカウントを取得したら、1 つのセット s_i を s_i のサブセットに置き換えて、カウントをインクリメンタルに更新します。

純粋に機能的なコードを使用してこれらすべてを実行すると、大きなプラスになります (私は Scala でコーディングしています)。

セットの包含は半順序付けであるため、私の問題を解決する最善の方法は、セットのハッセ図を表す DAG を作成し、エッジが包含を表し、整数値を各ノードのサイズを表す結合することであると考えました。ノードの下のサブダグに 1 を加えたものです。ただし、半順序付けからハッセ図を作成するアルゴリズムを開発しようとして数日間行き詰まりました (インクリメンタリティについては話さないでください!)。標準的な学部の資料。

ここに私のデータ構造があります:

私の DAG は、ルートのリストといくつかの半順序によって定義されます。

私はここでかなり立ち往生しています。DAG に新しい値 v を追加するために最後に思いついたのは次のとおりです。

1. DAG 内の v のすべての「ルート サブセット」rs_i、つまり、rs_i のスーパーセットが v のサブセットではないような v のサブセットを見つけます。これは、グラフで検索 (BFS または DFS) を実行することによって非常に簡単に行うことができます (collect関数、おそらく最適ではないか、欠陥がある可能性さえあります）。
2. 新しいノード n_v を構築します。その子ノードは以前に見つかった rs_i です。
3. 次に、n_v をどこに付けるかを調べましょう: 与えられたルートのリストについて、v のスーパーセットを見つけます。何も見つからない場合は、ルートに n_v を追加し、ルートから n_v のサブセットを削除します。それ以外の場合は、スーパーセットの子に対してステップ 3 を再帰的に実行します。

私はまだこのアルゴリズムを完全に実装していませんが、明らかに単純な問題に対して不必要に回旋しており、最適ではないようです。利用可能な単純なアルゴリズムはありますか (Google はこれについて無知でした)。

常に次のように定義する必要があるようですscala.math.PartialOrdering.lteq（または、少なくとも、と同じ結果が得られます）。

scala.math.PartialOrderingこの実装がトレイトに指定されていない理由はありますか？

なぜこれがあいまいなのですか？

これは部分的な順序付けのコンテキストであることを理解しています。そして、おそらく間違っていると思いますが、#2 の T& を #1 に入れることはできますが、#1 の T を #2 に入れることはできません。したがって、部分的な順序付けが機能するはずです。

私のコードでは、有向非巡回グラフを表すクラスを使用しています。私は自分でコードを書きました、それは難しくありませんでした。しかし、後で私は自分のアプリにもっと多くの要件があることに気付きました。グラフは推移簡約である必要があります。つまり、部分的なオードラーの一意の表現である必要があります。ユーザーがグラフのビジュアルGUI表現でドラッグアンドドロップまたはカット/コピー/貼り付けを行うたびに、それを検証してこの要件に適合させる必要があります。今、物事はより複雑になります。そこで、すべてのグラフ操作を安全に実行する方法などを計画しましたが、実際にコードに飛び込む前に、次のことを知りたいと思います。

半順序の既知のC/C ++インターフェースはありますか？（できればC ++）

グラフ用のライブラリをたくさん見つけましたが、私はすでに単純な非巡回有向グラフコードを持っています。推移簡約グラフを具体的に扱うものは見つかりませんでした（隣接行列は必要ありません。データはユーザーから取得されるため、ここでは非効率的です...これはユーザーデータ用の小さなグラフであり、数学的な使用）

不要な接続を自動的に検出して削除し、ノードのコピー/移動操作が半順序で有効かどうか、つまり半順序のプロパティを保持するかどうかを確認するためのテストを行うインターフェイスを探しています。