Я немного читал о деревьях двоичного поиска и о том, как они были разработаны для быстрого поиска, и это заставило меня задуматься. Как бы выглядел поиск из простого хеш-набора по сравнению с одним из этих деревьев.
Давайте определимся с этим вопросом немного лучше:
Учитывая структуру данных ‹int› длины n - сколько времени нужно, чтобы найти известное значение в этой структуре и сделать вывод, что значение не существует в этой структуре.
Рассмотрим массив длиной 5:
[1,2,3,4,5] - Сколько времени потребуется, чтобы найти значение 4 в этом массиве и выяснить, что 6 нет в массиве.
Старое доброе вбрасывание было единственным способом выяснить это *
* Помимо Google, книг, Интернета, коллег и всех, кто умеет программировать.
Претенденты:
· Скромный массив в качестве контрольной группы.
· Hashset ‹int›. Поскольку в этом эксперименте мы используем только целые числа, мы будем использовать HashSet (словарь, в котором ключ == Hashed (значение))
· Дерево двоичного поиска - не является встроенным типом данных в .Net, который относительно легко создать и известен быстрым поиском.
Дерево поиска:
BST - это не структура данных, которую мы используем в повседневном программировании, поэтому вот краткий обзор того, как я создал свою.
BST - это набор узлов (см. Ниже). Каждый узел имеет значение и не более двух других узлов - левого и правого. Каждый дочерний узел, который меньше родительского, хранится слева, а каждый дочерний узел, который больше родительского узла, сохраняется справа.
Преимущества использования BST заключаются в том, что вам не нужно перебирать всю структуру данных, чтобы найти значение или выполнять какой-то алгоритм сортировки.
Создать дерево относительно просто с помощью рекурсивной функции:
Что называется так:
Здесь стоит упомянуть, что я знаю, насколько этот код неэффективен. В любом случае мы в конечном итоге перечисляем весь массив, и рекурсия также будет занимать память, но помните, мы здесь, чтобы проверить скорость поиска, поэтому мы пока не будем это рассматривать.
Все, что мы делаем, чтобы найти значение в BST:
Итак, чтобы провести эксперимент, я создал образец набора данных:
Значение в середине массива и значение в конце массива - это значения, которые мы будем искать вместе с одной несуществующей переменной (1000001).
Чтобы сделать это справедливым, я использовал шкалу Log10 (n), начиная с 200k int в массиве.
Результаты:
Поэтому мне пришлось записывать результаты в тиках, потому что, как бы вы ни старались, выполнение этой операции на 8-ядерном процессоре с тактовой частотой 4 ГГц никогда не будет медленным.
Результаты показали… ничью. Какое разочарование.
Как и следовало ожидать, время поиска в массиве масштабируется с размером набора данных в O (n) режиме. Однако и алгоритм двоичного дерева поиска, и метод Hashset.Contains (), похоже, занимали одинаковое количество времени.
Изначально меня удивила производительность алгоритма BST. Но когда вы думаете об этом, в конце концов, это не так уж и удивительно.
Метод FindValue на узле будет вызываться с максимальным значением Log2 (n), где n - начальный размер выборки (поскольку это максимальная глубина BST).
См. Таблицу ниже:
Для увеличения количества элементов в выборке в 10 раз требуется всего лишь 3–4 дополнительных вызова методов, что означает практически полное отсутствие времени. Отличный результат.
Это означает, что он так же эффективен, как и поиск хеш-набора, который печально известен быстро!
Прежде чем мы объявим победу двоичного дерева поиска, эта реализация (заведомо далекая от идеала) содержала почти в 10 раз больше памяти, чем хэш-набор, и требовала почти в 10 раз больше времени для создания. Я подозревал, что столько же кажущихся, хотя бесчисленные часы исследований были потрачены на уточнение и усовершенствование хеш-набора, и около 45 минут ушло на создание моего двоичного дерева поиска.
Все еще:
Хешсет 1–0 BST
