Самый быстрый способ сравнить две структуры данных в Java

Question

Я хотел бы знать, какой самый быстрый способ в Java 1.5 сравнить две структуры данных.

Моя структура данных представляет собой дерево, которое может быть довольно большим. Я могу обойти всю структуру данных и сравнить 2 узла за узлом (что, я думаю, будет медленным). Или я могу вычислить хеш структуры данных, чтобы сделать это быстрее, верно?

Каков наилучший (эффективный и не слишком длинный) способ вычисления этого хеша?

Мне бы не хотелось слишком много времени для вычисления хэша ...

Надеюсь, я ясен ..: -) ...

Answer 1

Рассматривали ли вы сохранить работающий хэш-код, который постоянно обновляется по мере того, как элементы вставляются или удаляются из ваших деревьев? Таким образом, сравнение дерева в любой момент времени по hashCode будет мгновенным.

В зависимости от того, как вы реализуете свою хэш-функцию и как часто вы вставляете и удаляете узлы, это может быть ужасным решением. Если ваша хеш-функция работает быстро, вы не вносите много изменений, и вам нужно проводить много сравнений, это может сработать.

Answer 2

public void preOrderTraversal(Node r1, Node r2) {

       if (r1 != r2 )  { // implement equals here !!  

           System.exit(0); // exit and print not equal
       }

       preOrderTraversal(r1.left(),r2.left());
       preOrderTraversal(r1.right(),r2.right());
}

Answer 3

Если все объекты в графе реализуют сравнимо - вы можете просто вызвать CompareTo. Там, где это возможно, я всегда использую сопоставимые (а также хеш-код и равно) в POJOS.

Чтобы ускорить это, вы можете использовать ярлыки, чтобы объекты, которые не совпадают, возвращались как можно раньше. Мы делаем это, и это действительно помогает.

Я бы не стал пытаться преждевременно оптимизировать другие методы, пока вы не запустите над ним настоящий профилировщик (Netbeans бесплатен и имеет очень хороший профилировщик).

Хорошая вещь о добавлении CompareTo заключается в том, что он предоставляет вам универсальную функцию, которая полезна в других местах: TreeMaps, отсортированные коллекции и т. Д.

Answer 4

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

Answer 5

Как говорит gdm, вы можете сохранить работающий hashCode, который позволит вам быстро определить, являются ли два дерева различными (вам нужно будет сделать глубокое сравнение, как только вы определите, что есть такой же хэш). Вы можете использовать xor (например) для node.hashCode для всех узлов, что делает добавление и удаление очень простым вычислением:

this.hashcode ^= nodeInQuestion.hashCode;

Кроме того, вы можете создать неизменную структуру, которую вы можете intern . Опять же, это добавляет издержки к изменениям, но никакое сравнение не является более быстрым, чем эталонное равенство. Это зависит от того, оптимизируете ли вы для модификации или сравнения, нужна ли вам одинаковая скорость для позитивов и негативов и, что наиболее важно, действительно ли заметен размер ваших деревьев.

Answer 6

Чтобы вычислить хеш, вы должны полностью пройти оба дерева. Вы должны изучить свойства каждого узла и выполнить вычисление хеша. Например, если String находится в узле, вы должны перебрать его символы и выполнить некоторую математику. Затем вы должны объединить хеш узла с хешем других.

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

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

Answer 7

Каждый объект наследует .equals() и .hashCode() от Объект .

Стандартные структуры данных в Java уже должны реализовывать относительно быстрый метод .hashCode() для вас (хэш может вычисляться постепенно или может потребоваться перебор каждого элемента, проверьте источник структуры данных, которую вы используете будь уверен).

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

Чтобы получить точное сравнение, я бы выполнил обход дерева одновременно для обоих деревьев, сравнивая каждый элемент. Таким образом, форма дерева, а также содержащиеся в нем элементы будут сравниваться за время O(n), где n - это размер самого большого дерева.