10

多項式、特にその乗算をモデル化しようとしているときに、次の問題に遭遇します。乗算中、2 つの多項式の個々の単項式が乗算され、もちろん、(3x^2 y + 5x y^2) * (x + y) が発生する可能性があります。結果には 3x^2 y^2 と 5 x^2 y^2 が含まれており、これらをすぐに足し算で結合したいと考えています。

当然、単項式の x^2 y^2 の部分を (ハッシュ) マップのキーとして使用して、さまざまな係数 (例では 3 と 5) を合計したいと思います。しかし、私が想定する単項オブジェクトには、マップ キーの一部であってはならない係数も当然含まれているはずです。

もちろん、係数を無視するように単項式オブジェクトの equals/hashcode を書くこともできます。しかし、数学的に単項式が別の単項式と明らかに等しいのは、係数も等しい場合に限られるため、これはまったく間違っているように感じます。

中間演算に係数のない単項式オブジェクトを導入することも正しくないように見えます。

マップを使用する代わりに、リストを使用して、係数を無視する専用のコンパレーターで二分探索を使用できます。

キーの equals/hashcode を使用せず、専用のマップを実装する以外に、単項式を融合する方法についてより良いアイデアはありますか?

4

4 に答える 4

5

の JDK 実装では/実装[Linked]HashMapをオーバーライドできないため、他の方法は次のとおりです。equalshashCode

  • 次のようなラッピング オブジェクト:

      class A {
    private final String fieldA; // equals/hashCode based on that field.
    private final String fieldB; // equals/hashCode based on that field.
  }

  class B {
    private A a;
    public int hashCode() {return a.fieldA.hashCode();} 
    public boolean equals(Object o) {... the same ... }
  }

  Map<B, Value> map = new HashMap<B, Value>();
  map.put(new B(new A("fieldA", "fieldB")), new Value(0));

    さて、より多くのゲッター/コンストラクターを使用します。

    Comparatorこれは面倒な場合があり、 toを指定できるように equals/hashCode メソッドを指定できるライブラリ (Guava など) が存在する可能性がありますTreeMap。

    以下に、既存のマップを装飾するために何をすべきかを指摘する実装例を示します。

  • TreeMapaを特定の とともに使用しComparatorます。Comparator他の答えはそれを指摘していますが、これは問題につながる可能性があるため、 a を正しく定義する必要があると思いますcompareTo.同等に達したときにメソッドが 0 を返し、それ以外の場合は 1 を返す場合、これは自然な順序付けがないことを意味します. 探してみるか、ラッパー オブジェクトを使用してください。

挑戦したい場合は、委譲/別の装飾を使用して基本的な実装を作成できますHashMap(これは、 のような別の種類のマップである可能性がありますLinkedHashMap)。

public class DelegatingHashMap<K,V> implements Map<K,V> {
  private final BiPredicate<K,Object> equalsHandler;
  private final IntFunction<K> hashCodeHandler;
  private final Map<Wrapper<K>,V> impl = new HashMap<>();

  public DelegatingHashMap(
    BiPredicate<K,Object> equalsHandler,
    IntFunction<K> hashCodeHandler
  ) {
    this.equalsHandler = requireNonNull(equalsHandler, "equalsHandler");
    this.hashCodeHandler= requireNonNull(hashCodeHandler, "hashCodeHandler");
  }

  public Object get(K key) {
    Wrapper<K> wrap = new Wrapper<>(key);
    return impl.get(wrap);
  }  

  ...

  static class Wrapper<K2> {
    private final K2 key;
    private final BiPredicate<K> equalsHandler;
    private final IntFunction<K> hashCodeHandler;
    public int hashCode() {return hashCodeHandler.apply(key);}
    public boolean equals(Object o) {
      return equalsHandler.test(key, o);
    }
  }
}

そして、マップを使用したコード:

DelegatingHashMap<String, Integer> map = new DelegatingHashMap<>(
  (key, old) -> key.equalsIgnoreCase(Objects.toString(o, "")),
  key -> key.toLowerCase().hashCode()
);
map.put("Foobar", 1);
map.put("foobar", 2);

System.out.println(map); // print {foobar: 2}

しかし、おそらく (メモリにとって) 最善のHashMap方法は、ラッパーの代わりにハンドラーを直接使用するように を書き直すことです。

于 2014-09-10T20:00:05.047 に答える
3

TreeMapaでありSortedMap、したがって a でもあるa の使用を検討してくださいMap。Comparatorコンストラクターに を指定できます。Comparatorソートされたマップは、マップ キーのソートにそれを使用します。しかし重要なことは、あなたのケースでは、Comparatorが 0 を返す場合Comparator、キーが等しいと見なされることです。

もう 1 つのオプションは、別のクラスを導入することです。このクラスは、 のアダプターとして機能し、Mononomial適切なプロパティを持つマップ キーとして使用できます。

于 2014-09-10T20:05:04.707 に答える
3

TreeMapカスタムコンパレータで a を使用できます。

TreeMap(Comparator<? super K> comparator)

指定されたコンパレータに従って並べ替えられた、新しい空のツリー マップを構築します。

（ソース）

于 2014-09-10T20:02:01.930 に答える
1

単項式を係数と変数の 2 つの部分に分けた方がよいと思います。そうすれば、マップの変数部分をキーとして使用し、係数を値として使用できます (これを更新できます)。

このコードはすべて、Polynomialオブジェクト内の実装の詳細である必要があります

係数のない単項式が正しくないように見える理由がわかりません。必要がなければ、オブジェクトを外部に公開する必要はありません。Polynomialしかし、各単項式の係数を取得するためにゲッターを使用するのは良い方法かもしれません。

于 2014-09-10T20:02:49.600 に答える