Storing polynomials in TreeMaps --- Why?

Question

Today I wrote an exam paper for a university course on implementing data structures in Java. The final question was:

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

Realizing that this was a mistake, I nonetheless continued to explain why I did not think it was a good idea. Instead, I tried using a simple int [] array, since arrays have O (1) random access, O (n) iteration in both directions, and lack of additional memory for pointers (references).

Assuming I'm wrong and there is some benefit from using the (sorted) TreeMap, can anyone explain these benefits to me? I believe that since Matlab, Octave, Maple, and other proven numerical programs use arrays to store polynomials, this may not be all wrong.

Answer 1

I think the most striking example is x^10000 + 3x^2 + 2 or something like that. Do you want to make new int[10000] instead of three nodes in TreeMap ? TreeMap

And of course, by sorting, you can iterate to make it easier to create and manipulate your polynomial.

And are you sure arrays are used for numeric programs? I would like to see a quote from their internal implementation, if you think that is the case.

As for the memory problem, the standard implementation of java.util.TreeMap will give 7 additional links and primitives, one of which has a link inside it, the other of which contains 7 links inside it. So you are looking at 15 additional links for this. Each entry will have 5 references and a primitive, so instead of 2 + 1 * n for your array you have 15 + 6 * n. Thus, at any time when you have (14 + 5 * n) empty polynomials, using TreeMap uses less memory than using an array.

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

It is possible that I lack the link in the implementation, but I went through it pretty well.

Answer 2

You could use an array of type coefficientArray[exponent] and get the same advantage of index sorting that you get from TreeMap . The main advantage of TreeMap is that you are dealing with a sparse polynomial like x^60000 + 1 = 0 , which will be much smaller for storage in the map structure than an array, because you will need to allocate an array the size of your largest metric.

Answer 3

I can think of two reasons:

• Inconsistent (sparse) coefficients. It seems to me that using an array may work well for the case when the coefficients start at 0 and continue in sequence to n, but it seems to me that TreeMap (should really be just an imho map ) is better suited for situations where the coefficients may not be sequential.

• Order. The implementation of the Card will be different when you receive input in a non-ordered form or ask to deliver the contents without respect for the order.

Answer 4

What comes to my mind is what it can be:

• space-efficiency while preserving "sparse" polynomials (consider "x ^ 100 + 1" - this will require an array of 101 elements);
• it is easy to add polynomials in place (considering them mutable, which rarely should be a valid design).

I am not a very algebraic person, so please treat your thoughts with salt.

Answer 5

The main reason here for the tree map is that it allows the natural order of the keys. Using exponents as keys, you can quickly print a sparse polynomial in its natural form ( read standard ). If you use an array, you need to worry about disjoint polynomials and maintain some sort of order, while TreeMap will handle this for you.

 /** * 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()); } } 

Prints out:

 input : 7x^100 + 1 + 2x + 3x^2 standard form : 1x^0 + 2x^1 + 3x^2 + 7x^100