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.

Leger

@wrschneider99 Well, it's not homework per se. I've already handed in the exam so I don't have anything to gain, academically, by posting this question. I'm simply trying to understand the reasoning behind it. – Leger

Wouldn't an array be limited in what polynomial you could express, and take up unnecessary memory for smaller values? – Persnickety

Hm, maybe it has to do with that one usually multiplies polynomials together., which boils down to "how easy is it to multiply by x^n"? – Woodson

@Paxinum True, but in that case it would be better to store, say, the roots of the polynomial and let them define it. – Leger

@Leger I address the memory footprint issue in my post. You'll find that it is easy to find the cases that provide you with a smaller map than an array to represent the same information, and that it's smaller than you might think! – Togs

@glowcoder Thanks. What you say is true, there are situations where an array will be insufficient. But for most situtations, I think it is a better solution. – Leger

@Leger Here's a question for you then: which do you think would be the easiest code to read? Which do you think would cause the programmer to make the fewest number of mistakes? When it comes to real world coding, MOST (not all) of our code does not concern ourselves with a couple bytes here or a couple there, or a couple CPU cycles here or there. We concern ourselves with what is convenient because programmer time is expensive the most expensive cost in software development. – Togs

@glowcoder Well, but it's also important to provide the least amount of surprise. To an engineering student like me it seems natural to go the way of Matlab, the numerical environment which engineers (at least in my parts) are most likely to be familiar with. I agree that you should not normally care about a few bytes and milliseconds here and there, but that was precisely what this course was about. – Leger

@Leger Let's consider what is surprising to who though. You would expect programmers to be looking in this code, not engineers. If you are an engineer looking at Java code, you should be prepared for surprises, expecting that the code is setup for programmers. – Togs

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.

Togs

Not only that. Adding x^100 to an array with largest polynom x^99 would be O(n) and you'd be copying lots of stuff around. As a general rule I think: Most actions (at least in a simple implementation) are in the size of the array and not number of coefficients. I'd think that randomly accessing one specific coefficient isn't that useful in practice anyhow. – Kodiak

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.

Beka

Answer 3

I can think of 2 reasons:

1. Non-sequential (sparse) coefficients. It seems to me that utilizing an array may work well for the case where the coefficients began at 0 and continue in sequence to n but it seems to me that the TreeMap (should really just be Map imho) is better suited for situations where the coefficients may not be sequential.

2. Ordering. The Map implementation will excel when you are getting the input in an un-ordered form, or being asked to deliver the contents without respect to order.

Gunyah

You say it "should really just be Map". I would contend that the sorting is essential to the behavior and the most appropriate type would be SortedMap. – Togs

Answer 4

The things that come to my mind are that it can be:

• space-effective while storing "sparse" polynomials (consider "x^100 + 1" - this would require a 101-element array);
• easy to add polynomials in-place (considering them mutable, which should rarely be a valid design).

I'm not a highly algebraic person, so please treat my thoughts with a grain of salt.

Gorges

Answer 5

The main reason here for a tree map is that it allows for natural ordering of the keys. By using the exponents as keys you can quickly print out a sparse polynomial in natural (read standard) form. If you are using an array you need to worry about non contiguous polynomials and maintain some kind of ordering, whereas a TreeMap will handle that 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

Larvicide