問題タブ [equivalence-classes]

ツリーのノードに同値類を構築するための優れたデータ構造を探しています。理想的な構造では、次の操作は高速（必要に応じてO（1）/ O（n））で簡単（ミステリーコードの段落なし）である必要があります。

• （A）根から木を歩きます。各ノードで->子遷移は子ノードのすべての同等のバージョンを列挙します
• （B）2つの同値類をマージする
• （C）既存のノード（子）およびその他のデータのリストから新しいノードを作成します
• （D）ノードと構造的に同等のノードを見つけて（つまり、同じ数の子を持ち、対応する子は同じ同値類に属し、それらの「他のデータ」は等しい）、新しい（または新しく変更された）ノードを配置できるようにします正しい同値類（マージを介して）

これまで私が検討した（これらのいくつかは組み合わせて使用​​できる）：

• 子がノードではなくノードのコレクションへの参照であるパフェ。（A）高速、（B）マージされたコレクションを指すようにツリーをウォークしてノードを更新する必要がある、（C）新しいノードの各子を含むコレクションを見つける必要がある、（D）ツリーをウォークする必要がある
• ノードの特性によってノードのハッシュを維持します。これにより、（D）ははるかに高速になりますが、（B）は遅くなります（等価クラスがマージされたときにハッシュを更新する必要があるため）
• ノードをまとめて循環リンクリストにまとめます。（A）は高速です、（B）は高速ですが、循環リストの「マージ」部分が実際にリストを分割するという事実のために、（C）は高速であり、（D）はツリーを歩く必要があります
• 上記と同様ですが、各ノードに追加の「上」ポインターがあり、循環リストの正規メンバーを見つけるために使用できます。

私は甘い代替品を逃していますか？

あるデータベースを別のデータベースに変換するプロジェクトがあります。元のデータベース列の1つは、行のカテゴリーを定義します。この列は、新しいデータベースの新しいカテゴリにマップする必要があります。

たとえば、元のカテゴリが次のとおりであると仮定します。parrot, spam, cheese_shop, Cleese, Gilliam, Palin

これは私にとって少し冗長です。そして、これらの行を次のように分類したいと思いますsketch, actor。つまり、すべてのスケッチとすべてのアクターを2つの同値類として定義します。

それはかなり厄介です-私は次のようなものを持っていることを好みます：

しかし、もちろん、これはタプル全体をキーとして設定します。

Pythonでエレガントな多対1の辞書を作成する方法はありますか？

多くの要素があり、それらの間の同値関係を追跡する必要があると仮定します。要素Aが要素Bと同等である場合、それは他のすべての要素Bと同等です。

この情報をエンコードするための効率的なデータ構造を探しています。既存の要素との同等性を通じて動的に新しい要素を追加することが可能であり、その情報から、新しい要素が同等であるすべての要素を効率的に計算できる必要があります。

たとえば、要素[0,1,2,3,4]の次の等価セットについて考えてみます。

ここで、等号は同等性を示します。次に、新しい要素を追加します5

等価性を適用すると5=3、データ構造は次のようになります。

このことから、任意の要素に設定された等価性を効率的に反復できるはずです。5の場合、このセットは[3,4,5]になります。

disjoint_setsBoostは、私の要件のほとんどを満たしているように見える、と呼ばれる便利なデータ構造をすでに提供しています。上記の例を実装する方法を示すこの単純なプログラムについて考えてみます。

上で見たように、要素を効率的に追加し、互いに素な集合を動的に拡張することができます。すべての要素を反復する必要なしに、単一の互いに素なセットの要素を効率的に反復するにはどうすればよいでしょうか。

VS 2008、.net 3.5、C# プロジェクトを使用しています。Microsoft.VisualBasic.FileIO.FileSystem.DeleteDirectory と同じ機能を実行する必要があります。

多くの場合、C# 内から Microsoft.VisualBasic を参照することは望ましくないと誰もが言います。C# コード内からの VB との関連付けは望ましくないと思います。

FileSystem クラスを使用すると、これは完全に優れたソリューションですが、Microsoft.VisualBasic ライブラリを参照しないことを好みます。それは私が避けるだろう。

その他のサンプル: ファイルを削除する代わりにごみ箱に入れるにはどうすればよいですか?

Java には、クラス自体の外部にあるオブジェクトの比較を提供するための があります。これにより、順序付けられた比較Comparator<T>を行うための複数または代替の方法が可能になります。

しかし、順序付けられていない比較を行う唯一の標準的な方法は、クラスequals() 内でオーバーライドすることです。

クラスの外部で複数の/代替の順序付けられていない比較を提供したい場合はどうすればよいですか? (明らかな使用例は、特定のプロパティに基づいてコレクションを等価クラスに分割することです。)

最終用途が順序付けされていないチェック (たとえば、並べ替えやインデックス作成ではない) であると仮定すると、Comparator<T>2 つのオブジェクトが等しい場合は 0 を返し、2 つのオブジェクトが等しくない場合は値 != 0 を返し、等しいかどうかをチェックするだけを実装しても問題ありませんか? （注：私がこの解決策に飛びつかない唯一の理由は、技術的には、Comparator推移性と対称性を満たす関係を提供しないことで契約を破ることができるからです。）

EqualsComparator<T>標準クラスか何かがあったはずのようです。

(Guava はこのような処理を行いますか?)

次のような整数のリストがあると考えてください。

問題は、少なくとも1つの共通要素を持つリストをマージすることです。したがって、特定の部分のみの結果は次のようになります。

大きなデータ（要素は単なる数値）でこれを行う最も効率的な方法は何ですか？tree構造について考えることはありますか ？私は今、リストを交差点に変換して反復することで仕事をしていますがsets、遅いです！さらに、とても初歩的な感じがします！さらに、一部のリストはいつかマージされないままであるため、実装には何か（不明）が欠けています！そうは言っても、自己実装を提案する場合は、寛大で、簡単なサンプルコード[明らかにPythonが私のお気に入りです:)]または疑似コードを提供してください。
更新1： これが私が使用していたコードです：

関数は（バグあり!!）：

結果は次のとおりです。

更新2： 私の経験では、以下のNiklas Baumstarkによって提供されたコードは、単純なケースでは少し速いことが示されました。「Hooked」によって与えられた方法は完全に異なるアプローチであるため、まだテストされていません（ちなみにそれは興味深いようです）。これらすべてのテスト手順は、結果を保証するのが非常に難しいか、不可能である可能性があります。私が使用する実際のデータセットは非常に大きく複雑であるため、繰り返すだけではエラーを追跡することはできません。つまり、モジュールとして大きなコード内でメソッドをその場所にプッシュする前に、メソッドの信頼性に100％満足する必要があります。単純に今のところ、 Niklasの方法はより高速であり、単純集合の答えはもちろん正しいです。
しかし、実際の大規模なデータセットでうまく機能することをどのように確認できますか？エラーを視覚的に追跡することができないので！

更新3： この問題では、メソッドの信頼性が速度よりもはるかに重要であることに注意してください。最終的に最大のパフォーマンスを得るために、PythonコードをFortranに変換できるようになることを願っています。

更新4：
この投稿には多くの興味深い点があり、寛大に答え、建設的なコメントが与えられています。すべてをよく読むことをお勧めします。質問の展開、驚くべき答え、建設的なコメントと議論に感謝します。

C ++で「==」演算子をオーバーロードする場合、同等性が明示的に意味するものに関する標準的な定義、または「==」がどのように動作するかに関する一連のガイドラインはありますか？

私は現在、自分自身全体をメモリに保存しないクラスを持っています。基本的に、優先キューを使用して、内部のオブジェクトが使用されている頻度を決定し、オブジェクトがキューの最後からポップされると、メモリから削除されてディスクに書き込まれます。

したがって、問題は平等で発生します。これらのオブジェクトの2つが等しいとはどういう意味ですか。すべての点で同じオブジェクトAとBから始めることができるため、それらは同じデータをメモリにロードし、ディスク上に同じデータを持っています。しかし、AとBで一連の関数を呼び出した後、それらは異なる可能性があります。AとBはまだディスク上に同じデータを持っていますが、それらはメモリにロードされた異なるデータを持っています。それで、問題はA == B真か偽かを解決する必要があるかどうかです。

これがどのように機能するかを定義する一連のルールまたはガイドラインはありますか？それとも、これは、プログラムにとって何が最も理にかなっているのかを判断し、「==」が何をするのかを文書化するだけの状況ですか？

等価クラスを作成し、境界値分析を行う必要があるプログラムがあります。私の問題は、私のコースで説明したのは、整数または文字列を直接入力するプログラムの等価クラスを作成することだけだということです。

プログラムは、カレンダー付きのシンプルな To Do リストです。ユーザーからの唯一のキーボード入力は、タスクの文字列とリマインダーの時間の整数です。

整数の処理方法は知っていますが、文字列の最大サイズがばかげているようで、わかりません。また、その入力には任意の記号などを含めることができます。

プログラムの唯一の他の側面は、日付を選択できるボタンと、月と年を選択できるドロップダウン メニューです。

境界値分析はもちろん、ボタンやドロップダウン メニューの等価クラスを作成するにはどうすればよいですか? また、無効な入力がないように見える文字列に対して、どのように等価クラスを作成し、境界値分析を行うのですか?

オートマトン アルゴリズムの場合、関数型言語による高速の Union-Find データ構造が必要です。データ構造の正しさを正式に証明する必要があるため、単純な構造を好みます。

私がやろうとしているのはS、関係に関するセット内の要素の等価クラスを計算することR ⊆ S × Sです。最後に知りたいのは、 の任意の要素をその等価クラスの (正規の) 代表にf: S → Sマップする関数です。「標準的」とは、1 つの等価クラスのすべての要素で同じである限り、つまり保持したい限り、どの代表であってもかまわないことを意味します。SRf x = f y ⟺ (x,y) ∈ R

関数型言語でこれに最適なデータ構造とアルゴリズムは何でしょうか? 「通常の」機能コード、つまり可変性/状態変換モナドが本当に必要であることを付け加えておきます。

編集：その間、私はこのアルゴリズムを思いつきました：

Sこれにより、 の任意の要素をその等価クラスの代表にマップするマップが作成されます。ここで、代表は、 の反復によって到達する最初の要素ですS。これには実際には線形時間があると思います（マップ操作が一定の場合）。ただし、これが実際にどれほど効率的であるかがわからないため、他のソリューションにまだ興味があります。

(私の関係は内部的に "S → (S Set) オプション" として表現されているため、{t | (s,t) ∈ R} に対する反復 - これはその構造に対する安価な操作です。)

私はこのトピックを理解しようとしており、非常に基本的なトピック (個別のドメインではない) から始めていますが、これは正しくないと思います。

まだ画像を投稿できないので、説明は次のようになります。

彼らは、負の数に対して無効なクラスを定義し、0-500 および 500 から 1300 に対して有効であり、1300 から 5000 に対して INVALID を定義しています。
私はそれが間違いであり、無効なクラスが 5000 に制限され、無限大になると考えています。私は正しいですか？