Storing polynomials in TreeMaps --- Why?

Question

I wrote an exam paper today, for a university course concerned with the implementation of data structures in Java. The last question was along these lines:

Explain why it's convienient to use a TreeMap<Integer, Integer> to store a polynomial with integral coefficients, especially when the polynomial is supposed to be printed out in standard form, as a String.

Realising that it was a mistake, I nevertheless proceeded to explain why I did not think it was a good idea. I instead argued to use a simple int[] array, since arrays have O(1) random access, O(n) iteration in both directions and no extra memory footprint for pointers (references).

Assuming I'm wrong and there is some benefit to using a (sorted) TreeMap, can anyone please explain those benefits to me? I reason that since Matlab, Octave, Maple and other well-tested numerical programs use arrays to store polynomials, it can't be all wrong.

Answer 1

I think the most striking example is x^10000 + 3x^2 + 2 or something. You want to make a new int[10000] instead of 3 nodes in a TreeMap? :-)

And of course being sorted you can iterate in order to construct and manipulate your polynomial easier.

And are you sure that numerical programs use arrays for that? I'd like to see a citation of their internal implementation if you believe that's the case.

As for the memory footprint issue, the standard implementation of java.util.TreeMap will yield 7 extra references and primitives, one of which has a reference inside it, another of which has 7 references inside it. So you're looking at 15 extra references for that. Each entry will have 5 references and a primitive, so instead of 2 + 1*n for your array, you have 15 + 6*n. So any time you have (14 + 5*n) empty polynomials, using a TreeMap uses less memory than using an array.

The smallest example of this would be x^20 which would have 21 array elements and 1 array reference for a total of 22 words, while the TreeMap would only have 21 words.

It's conceivable I'm missing a reference in the implementation but I went over it pretty good.

Answer 2

You could certainly use an array like coefficientArray[exponent] and get the same advantage of pre-sorting by exponent that you get from TreeMap. The main advantage of TreeMap is when you're dealing with a sparse polynomial like x^60000 + 1 = 0, which would be much smaller to store in a map structure than an array because you'd need to allocate the array as big as your biggest exponent.