6

私は今日、Java でのデータ構造の実装に関する大学のコースの試験問題を書きました。最後の質問は次のようなものでした。

TreeMap<Integer, Integer> を使用して整数係数を含む多項式を格納すると便利な理由を説明してください。特に、多項式が標準形式で文字列として出力されることになっている場合はそうです。

それが間違いだったことに気づきましたが、それにもかかわらず、なぜそれが良い考えではないと思ったのかを説明し始めました. 代わりに、単純な int[] 配列を使用することを主張しました。これは、配列には O(1) のランダム アクセスがあり、双方向で O(n) の反復があり、ポインター (参照) 用の余分なメモリ フットプリントがないためです。

私が間違っていて、(ソートされた) TreeMap を使用する利点があると仮定すると、誰でもそれらの利点を説明してもらえますか? Matlab、Octave、Maple、およびその他の十分にテストされた数値プログラムは配列を使用して多項式を格納するため、すべてが間違っているわけではありません。

4

5 に答える 5

6

x^10000 + 3x^2 + 2最も顕著な例は、または何かだと思います。new int[10000]の代わりに 3 つのノードを作成しTreeMapますか? :-)

もちろん、ソートされているため、多項式を簡単に構築および操作するために反復できます。

そして、数値プログラムがそのために配列を使用していると確信していますか? そうだと思われる場合は、内部実装の引用を見たいと思います。

メモリ フットプリントの問題に関しては、 の標準実装でjava.util.TreeMapは 7 つの追加の参照とプリミティブが生成されます。そのうちの 1 つは内部に参照があり、もう 1 つは内部に 7 つの参照があります。つまり、そのための 15 の追加参照を見ています。各エントリには 5 つの参照と 1 つのプリミティブがあるため、配列の 2 + 1*n ではなく、15 + 6*n になります。したがって、(14 + 5*n) 個の空の多項式がある場合は常に、配列を使用するよりも使用するメモリがTreeMap少なくなります。

この最小の例は、x^2021 個の配列要素と 1 個の配列参照を持ち、合計 22 語であるのに対し、TreeMap には 21 語しかありません。

実装で参照が欠落している可能性がありますが、かなりうまくいきました。

于 2011-12-14T17:08:11.073 に答える
2

確かに のような配列を使用して、coefficientArray[exponent]から得られる指数による事前ソートと同じ利点を得ることができますTreeMap。の主な利点はTreeMap、 のようなスパース多項式を扱う場合です。x^60000 + 1 = 0これは、最大指数と同じ大きさの配列を割り当てる必要があるため、配列よりもマップ構造に格納する方がはるかに小さくなります。

于 2011-12-14T17:08:25.967 に答える
2

I can think of 2 reasons:

  1. Non-sequential (sparse) coefficients. It seems to me that utilizing an array may work well for the case where the coefficients began at 0 and continue in sequence to n but it seems to me that the TreeMap (should really just be Map imho) is better suited for situations where the coefficients may not be sequential.

  2. 注文。Mapの実装は、順序付けされていない形式で入力を取得する場合、または順序に関係なくコンテンツを配信するように求められている場合に優れています。

于 2011-12-14T17:09:49.760 に答える
1

私の頭に浮かぶのは、次のことができるということです。

  • 「スパース」多項式を格納する際のスペース効率 (「x^100 + 1」を考慮 - これには 101 要素の配列が必要です)。
  • 多項式をその場で簡単に追加できます (それらは可変であると見なされ、有効な設計になることはめったにありません)。

私は高度な代数的人間ではないので、私の考えを一粒の塩で扱ってください。

于 2011-12-14T17:08:33.640 に答える
1

ここでツリー マップを使用する主な理由は、キーの自然な順序付けを可能にすることです。指数をキーとして使用することにより、スパース多項式を自然な (標準を読む) 形式ですばやく出力できます。配列を使用している場合は、連続していない多項式について心配し、ある種の順序を維持する必要がありますが、TreeMap がそれを処理します。

/**
 * Example only! only dealing with + (ignoring -)
 */
public class PolynomialExample {

  public static void main(String[] args) {
    TreeMap<Integer,Integer> polynomial = new TreeMap<Integer, Integer>();

    // not in natural order
    String input = "7x^100 + 1 + 2x + 3x^2";

    String[] parts = input.split("[\\+]");
    for (int i = 0; i < parts.length; i++) {
      String part = parts[i].trim();
      String[] val = part.split("\\^");
      String base = val[0];
      String exp = "0";
      if(base.contains("x")){
        base = base.replaceAll("x", "");
        if(val.length > 1){
          exp = val[1].trim();
        } else {
          exp = "1";
        }
      }
      polynomial.put(Integer.valueOf(exp), Integer.valueOf(base));
    }

    Iterator<Integer> exponentIterator = polynomial.keySet().iterator();
    StringBuilder standardForm = new StringBuilder();
    while(exponentIterator.hasNext()){
      Integer exp = exponentIterator.next();
      Integer base = polynomial.get(exp);
      standardForm.append(base.toString()).append("x^").append(exp.toString());
      if(exponentIterator.hasNext()){
        standardForm.append(" + ");
      }
    }

    System.out.println("input         : "+input);
    System.out.println("standard form : "+standardForm.toString().trim());
  }
}

プリントアウト:

input         : 7x^100 + 1 + 2x + 3x^2
standard form : 1x^0 + 2x^1 + 3x^2 + 7x^100
于 2011-12-14T17:23:04.383 に答える