Хранение полиномов в TreeMaps --- Почему?

Question

Сегодня я написал экзаменационную работу для университетского курса, посвященного реализации структур данных в Java.Последний вопрос звучал так:

Объясните, почему удобно использовать TreeMapхранить многочлен с целыми коэффициентами, особенно когда предполагается, что многочлен должен быть распечатан в стандартной форме, в виде строкиНе думаю, что это была хорошая идея.Вместо этого я утверждал, что должен использовать простой массив int [], поскольку массивы имеют O (1) произвольный доступ, O (n) итерацию в обоих направлениях и не требуют дополнительной памяти для указателей (ссылок).Я неправ, и есть некоторая польза от использования (отсортированного) TreeMap. Может кто-нибудь объяснить мне эти преимущества?Я полагаю, что, поскольку Matlab, Octave, Maple и другие хорошо протестированные числовые программы используют массивы для хранения полиномов, все не может быть неправильно.

Answer 1

Я думаю, самый яркий пример - x^10000 + 3x^2 + 2 или что-то в этом роде. Вы хотите сделать new int[10000] вместо 3 узлов в TreeMap? : -)

И, конечно, после сортировки вы можете выполнять итерации, чтобы легче создавать и манипулировать вашим полиномом.

А вы уверены, что числовые программы используют для этого массивы? Я хотел бы видеть цитату из их внутренней реализации, если вы считаете, что это так.

Что касается проблемы занимаемой памяти, стандартная реализация java.util.TreeMap даст 7 дополнительных ссылок и примитивов, одна из которых имеет ссылку внутри, а другая - 7 ссылок внутри. Итак, вы смотрите на 15 дополнительных ссылок для этого. Каждая запись будет иметь 5 ссылок и примитив, поэтому вместо 2 + 1 * n для вашего массива у вас будет 15 + 6 * n. Таким образом, каждый раз, когда у вас есть (14 + 5 * n) пустых полиномов, использование TreeMap использует меньше памяти, чем использование массива.

Наименьшим примером этого будет x^20, который будет иметь 21 элемент массива и 1 ссылку на массив в общей сложности на 22 слова, тогда как TreeMap будет иметь только 21 слово.

Возможно, мне не хватает ссылки в реализации, но я прошел ее довольно хорошо.

Answer 2

Я могу придумать 2 причины:

1. Непоследовательные (разреженные) коэффициенты. Мне кажется, что использование массива может работать хорошо для случая, когда коэффициенты начинаются с 0 и продолжаются последовательно до n , но мне кажется, что TreeMap (должно действительно be Map imho) лучше подходит для ситуаций, когда коэффициенты не могут быть последовательными.

2. Заказ. Реализация Map будет успешной, когда вы получаете ввод в неупорядоченной форме или когда вас просят доставить содержимое без учета порядка.

Answer 3

Вы, конечно, можете использовать массив типа coefficientArray[exponent] и получить то же преимущество предварительной сортировки по показателю, что и TreeMap.Основное преимущество TreeMap заключается в том, что вы имеете дело с разреженным полиномом, таким как x^60000 + 1 = 0, который будет гораздо меньше для хранения в структуре карты, чем в массиве, потому что вам нужно будет выделить массив размером с самый большойпоказатель.

Answer 4

Основная причина для древовидной карты состоит в том, что она обеспечивает естественное упорядочение ключей. Используя показатели в качестве ключей, вы можете быстро распечатать разреженный полином в натуральной ( read standard ) форме. Если вы используете массив, вам нужно беспокоиться о несмежных полиномах и поддерживать какой-то порядок, тогда как TreeMap справится с этим за вас.

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

Распечатывает:

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

Answer 5

То, что приходит мне в голову, это то, что это может быть:

• эффективен при сохранении «разреженных» полиномов (рассмотрим «x ^ 100 + 1» - для этого потребуется массив из 101 элемента);
• легко добавлять полиномы на месте (считая их изменяемыми, что редко должно быть допустимым дизайном).

Я не очень алгебраический человек, поэтому, пожалуйста, отнесите мои мысли крошке соли.