6

我今天写了一篇试卷，是关于在 Java 中实现数据结构的大学课程。最后一个问题是这样的：

解释为什么使用 TreeMap<Integer, Integer> 来存储具有整数系数的多项式很方便，尤其是当多项式应该以标准格式打印为字符串时。

意识到这是一个错误，我仍然继续解释为什么我认为这不是一个好主意。相反，我主张使用简单的 int[] 数组，因为数组具有 O(1) 随机访问、O(n) 双向迭代，并且指针（引用）没有额外的内存占用。

假设我错了并且使用（排序的）TreeMap 有一些好处，任何人都可以向我解释这些好处吗？我的理由是，由于 Matlab、Octave、Maple 和其他经过充分测试的数值程序使用数组来存储多项式，所以不会全错。

4

5 回答 5

6

我认为最引人注目的例子是x^10000 + 3x^2 + 2什么。您想在 a 中制作 anew int[10000]而不是 3 个节点TreeMap？:-)

当然，排序后您可以进行迭代，以便更轻松地构造和操作多项式。

你确定数值程序为此使用数组吗？如果您认为是这种情况，我希望看到对他们内部实施的引用。

至于内存占用问题，标准实现java.util.TreeMap会产生 7 个额外的引用和原语，其中一个内部有一个引用，另一个内部有 7 个引用。因此，您正在为此查看 15 个额外的参考资料。每个条目将有 5 个引用和一个原语，因此您的数组不是 2 + 1*n，而是 15 + 6*n。所以任何时候你有 (14 + 5*n) 个空多项式，使用 a比使用数组TreeMap使用更少的内存。

最小的例子是x^20它有 21 个数组元素和 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

我能想到2个原因：

  1. 非序列（稀疏）系数。在我看来，使用数组可能适用于系数从 0 开始并按顺序继续到n的情况，但在我看来，TreeMap（实际上应该只是Map imho）更适合系数的情况可能不是顺序的。

  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 回答