jfo*_*erg 6 java polynomial-math data-structures
我今天写了一篇关于Java数据结构实施的大学课程的试卷.最后一个问题是这样的:
解释为什么使用TreeMap <Integer,Integer>来存储具有积分系数的多项式是很方便的,特别是当多项式应该以标准形式打印出来时,作为字符串.
意识到这是一个错误,我接着解释了为什么我认为这不是一个好主意.我反而主张使用一个简单的int []数组,因为数组在两个方向上都有O(1)随机访问,O(n)迭代,并且指针(引用)没有额外的内存占用.
假设我错了并且使用(排序的)TreeMap有一些好处,有人可以向我解释这些好处吗？我的理由是,由于Matlab,Octave,Maple和其他经过良好测试的数值程序使用数组来存储多项式,因此不可能完全错误.
我认为最引人注目的例子是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^2021个数组元素和1个数组引用,总共22个单词,而TreeMap只有21个单词.
可以想象我在实现中缺少一个参考,但我很好地完成了它.