在TreeMaps中存储多项式--为什么？

Question

今天，我为一门大学课程写了一篇试卷，内容是用Java实现数据结构。最后一个问题是这样说的：

解释为什么使用TreeMap来存储带积分系数的多项式，特别是当多项式应该以标准形式打印为字符串时。

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

假设我错了，并且使用(排序) TreeMap有一些好处，谁能向我解释一下这些好处吗？我认为，由于Matlab，Octave，Maple和其他经过测试的数值程序使用数组来存储多项式，所以不可能都是错误的。

Answer 1

我认为最引人注目的例子是x^10000 + 3x^2 + 2之类的。您希望创建一个new int[10000]，而不是TreeMap中的3个节点？:-)

当然，排序后，您可以迭代，以便更容易地构造和操作多项式。

你确定数字程序是用数组来实现的吗？如果你认为是这样的话，我希望看到他们内部实现的引文。

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

最小的例子是x^20，它有21个数组元素和一个数组引用，总共有22个单词，而TreeMap只有21个单词。

可以想象，我在实现中遗漏了一个引用，但我很好地研究了它。

Answer 2

当然，您可以使用像coefficientArray[exponent]这样的数组，并获得与TreeMap相同的按指数进行预排序的优势。TreeMap的主要优点是当您处理像x^60000 + 1 = 0这样的稀疏多项式时，与数组相比，在映射结构中存储它要小得多，因为您需要分配与最大指数一样大的数组。

Answer 3

我能想到两个原因：

1. Non-sequential (稀疏)系数在我看来，在系数从0开始并按n顺序继续的情况下，使用数组可能会很好，但在我看来，TreeMap (实际上应该是映射 imho)更适合于系数可能不是的情况。当您以无序的形式获取输入或被要求在不遵守订单的情况下交付内容时，Map实现将突出。

。