1

Javaで等価クラスを実装する簡単な方法は何ですか? その目的のためのライブラリはありますか？

厄介な部分は、効率的でナイーブでない "equal" 演算子の書き方です。

しましょうS = {x,y,z,w,h}。x->1, y->1, z->1, w->2, h->2S の等価クラスのマッピングを使用する場合、マッピングをx->10, y->10, z->10, w->20, h->20同じ等価クラスと見なす必要があります。

セット S の基数が大きくなると、素朴な「等しい」演算子はすぐに時間がかかるようになります。

簡単な方法は何でしょうか？何か案が？

[編集]明確にするために、特定の問題は次のように形式化できます。

S を空でない集合とします。V から整数への部分写像の集合を M で表す。以下で定義される二項関係 \sim が M 上の同値関係を導出することを示すのは比較的簡単です。

m1 と m2 の場合、M の 2 つの部分写像 m1 \sim m2

  1. V の任意の a に対して、m2(a) が定義されている場合にのみ、m1(a) が定義されます。

  2. V の任意の a,b について、m2(a) と m2(b) が両方とも同じ整数値に定義されている場合に限り、m1(a) と m1(b) は両方とも同じ整数値 'z1' であると定義されます。 'z2' ('z1' と異なる場合とない場合があります)

    例。

    a->9,b->9,w->1 \sim a->10,b->10,w->0

    しかし、言うのは正しくありません

    a->5 \sim b->9

ありがとう。

4

3 に答える 3

2

私があなたが正しいと理解しているなら、あなたはベクトル正規化を適用することができます。たとえば、3Dベクトルは、そのすべてのコンポーネントをベクトルの長さで個別に除算することにより、長さ1に正規化されます。2つの正規化されたベクトルの成分が等しい場合、それらの元の（正規化されていない）ベクトルは同じ方向を指します（これは、「等しい」と定義すると思います）

x、y、z、w、hは、あなたの場合、5次元のベクトルになります。同じ方向にショーをするとき、それらは同じクラスに属しますが、任意の長さを持つことができます。

于 2013-02-17T22:25:23.560 に答える
2

あなたの質問から私が理解していることから、セットの最大公約数（ユークリッドのアルゴリズムを再帰的に）を一度見つけて、代わりに商をそれでマッピングできます-それらが別のセットと正確に等しい場合は等しいですが、そうでない場合はそうではありません。これは、セットのサイズとマッピングが等しい場合にのみ機能します。

于 2013-02-17T22:04:47.040 に答える
0

余談ですが、あなたの定義では、セット S は実際にはセット V であると思います。

Set(Set(E)). equals() があなたの目的にとって効率的であるとは思いませんが、Uliは正しい軌道に乗っていると思います。(申し訳ありませんが、lt または gt 記号を取得できませんでした)

Set(E).equals() のデフォルトの実装は、おそらく O(n log n) または O(n^2) です。Set(E). equals() には、ほぼ確実に並べ替えが含まれます。O(n log n) は最高です。基数ソートを見ることをお勧めします。O(n*log n) ですが、非常にゆっくりと成長します。

于 2016-10-22T04:06:17.187 に答える