1

値の長いリストを含む可能性のある不変オブジェクトを比較する一般的に受け入れられている方法はありますか?

これまでのところ、私のインターフェースは次のとおりです。

interface Formula : IEquatable<Formula> {
   IList<Symbol> Symbols {get;}
}

interface Symbol : IEquatable<Symbol> {
   String Value {get;}
}

ここで、不変データ型Formulaは一連の を表しSymbolます。したがって、式では：

x -> y

記号はx、、、->ですy。

内容 (シンボルのリストなど) に基づいて 2 つの数式を比較したいと考えています。したがって、シンボルの任意のリストにnew Formula(symbols)等しくなります。new Formula(symbols)

ただし、常に 2 つのリストを繰り返し比較したくはありません。

実装では、初期化中にある種の計算値を作成し、Formulaそれを比較に使用することを考えていました。ただし、そのためには、何らかのメソッドをインターフェイスに追加する必要があります。私はその方法を何と呼ぶでしょうか？

整数に限定されているように見えるため、これにハッシュ コードを使用することが適切かどうかはわかりません。

助けていただければ幸いです-不明な点がある場合は、質問を修正します。ありがとうございました！

4

5 に答える 5

5

これには間違いなくハッシュコードを使用できます。ハッシュコードは一意である必要はないことを忘れないでください。衝突（同じハッシュコードを持つ2つの等しくないシーケンス）がひどく頻繁に発生しない場合に役立ちます。（少なくとも、明らかな状況で等しいハッシュコードを回避するアプローチを考え出すようにしてください。）

したがって、構築時にハッシュコードを1回計算し（各シンボルのハッシュコードを順番に組み合わせることにより）、GetHashCode毎回再計算せずにからハッシュコードを返すことができます。つまり、等しいハッシュコードを持つシーケンスを比較するだけで済みます。これは、等しくないシーケンスではめったに発生しません。

于 2012-05-29T20:40:17.003 に答える
2

いいえ、すべての要素を比較する必要があります。可能な数式のセットは無限ですが、可能なハッシュ コードのセットは有限であるため、ハッシュ コードまたは同様のアプローチを使用することはできません。

Jon Skeet が指摘しているように、ハッシュ コードを使用して数式を要素ごとに比較する必要性を減らすことはできますが、その必要性をなくすことはできません。2 つの数式のハッシュ コードが等しくない場合、数式が等しくないことがわかりますが、ハッシュ コードが等しい場合は、要素ごとに比較して等しいかどうかを確認する必要があります。

于 2012-05-29T20:41:46.410 に答える
1

これは、GetHashCodeをオーバーライドするための他の答えと少し似ていますが、私には別のアプローチがあります。式には文字列表現があるように見えるので...。

GetHashCodeをオーバーライドできません。オーバーライドでは、

foreach(char c in ToString().ToCharArray()){

int hashCode |= c;

}

この結果、方程式のシンボルをパックした表現である4バイトのコードが生成されます。

各シンボルにHashTableで検索できる特定のOpCodeがある場合、これはさらに進む可能性があります。

各SymbolがプロパティOpCodeを宣言する必要がないように、各OpCodeのエイリアスを使用してHashTableを構築します。

次に、上記のHashTableでルックアップを実行したSymbolクラスで拡張ToOpCodeを作成します。

次に、GetHashCodeのExtensionメソッドを利用します。

方式....

public override int GetHashCode(){

    foreach(Symbol c in Symbols){

       int hashCode |= c.ToOpCode();

    }

}

シンボル....

public override int GetHashCode(){
    retuurn Extensions.ToOpCode(this);

}

この実装では、a+bとb+aに対して同じハッシュが生成されます。これは、質問ごとに非常に重要です...

さらに、OpCodeを正しく連続して指定した場合、技術的には次の形式で方程式を比較できます。

(a) + (b)==(a+b)

これは、括弧OpCodesに数値とは異なる場所のHashCodeの値が指定されていることを確認することで実現されます...

たとえば、4バイト（整数）の場合、スコープの深さは最初のバイトに保持でき、スタック内の前または次の方程式/シンボルへのインデックスは次になり、次の2バイトは符号データと方程式の値/継続または変数の数（排他的）。

これにより、ネストレベルの数などの特定の情報を伝えることができるため、基本的にEqualsをオーバーライドして、必要に応じa + bてとb + aを区別できるようになります((a) + (b))。

たとえば、方程式が特定の方法でまったく同じであるかどうかを知りたい場合がありますが、別の方法では、方程式が同じことを行っているが、まったく同じ方法で記述されていないかどうかを知りたい場合があります。

これにより、ハッシュコードに基づいて単純に仮定するのではなく、スコープの深さが一致するかどうか、方程式にまったく同じステップ数があるかどうかを確認するなど、さまざまな方法で同等性を判断することもできます。

たとえば、次のようにシフトして、次のようなものを決定できます。

hash<<8はparensの部門になりますhash<<16はスタックハッシュの前または次の方程式のポインターになります<<24は、方程式の符号またはコード値の連続または変数の数になります（排他的）

hash == anotherHashを実行することもできますが、この方法では、文字通りオーバーヘッドがなく、柔軟性が大幅に向上します。

ハッシュにさらにスペースが必要な場合は、longを返す新しいメソッドGetExtendedHashCodeを作成してから、シフト/ダウンキャストするか、GetHashCodeのExtendedHashCodeを再フォーマットして、CLRで必要なint形式に一致させます。

また、シンボルをスタックに残し、CLRと同じように使用することで、この方法で変数と値を表すことができるという利点もあります。

于 2012-05-29T21:00:31.543 に答える
1

私はそれがあなたがする必要があるすべてではないと信じています...

a+b = (a+b)

あなたのアプローチでは誤りになります。

両側の式のAST（抽象構文木）を作成してから、式を比較する必要があると思います。ASTは、ASTで階層として表現されるため、parnthesisを廃止します。

hth

マリオ

于 2012-05-29T20:41:12.097 に答える
0

まず第一に、私はIEquatable<T>どんな非封印されたタイプにも実装することを勧めませんT。封印されていない型に実装する唯一の安全な方法IEquatable<T>.Equalsは、通常、仮想メソッドを呼び出すことObject.Equalsです。そうしないと、親クラスIEquatable<T>が1つ以上の型に対して実装するクラスが、すべてのインターフェースを再実装せずにTオーバーライドする可能性があります。したがって、再実装されていないそのようなインターフェースはすべて壊れます。Object.EqualsObject.GetHashCodeIEquatable<T>

次に、2つのインスタンスのリストを比較しているときに、同等であるが別個のインスタンスを参照しているFormula対応する参照のペアが見つかった場合は、各インスタンスを呼び出すと役立つ場合があります。一方が他方よりも大きい場合は、大きい値の参照をもう一方のリストの参照に置き換えます。これにより、これらのリストの将来の比較が加速されます。さらに、同じアイテムを持つ複数のリストを繰り返し比較すると、すべてのリストが同じインスタンスを持つように「重力」します。SymbolSystem.Runtime.CompilerServices.RuntimeHelpers.GetHashCode()RunTimeHelpers.GetHashCode()Symbol

最後に、リストが等しいことがわかり、リストが「意味的に」不変であると想定される場合、同じRuntimeHelpers.GetHashCode()トリックを使用してListインスタンスを選択できます。これにより、将来の比較が容易になります。

于 2012-06-01T21:14:15.997 に答える