Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Словарь - это абстрактный тип данных, который связывает ключи со значениями. Его ещё называют ассоциативный массив, карта, таблица символов, коллекция. Будет две статьи на эту тему, где мы покажем шесть картинок / способов реализации словаря, которые отличаются друг от друга по времени работы и по требованию к памяти.
Первая статья:
Линейный массив
Односвязный список
Отсортированный массив
Вторая статья:
Двоичное дерево поиска
Хэш-таблица
Префиксное дерево
Дом для кота, Интерфейс для словаря
Начнём созидание словаря с формулировки методов для работы с ним. Минимальный набор таких методов: put - добавить, get - получить.
По хорошему, мы должны создать обобщённый интерфейс с возможностью указать любой тип данных как для ключа, так и для значения. Однако, в рамках этой работы мы будем для удобства использовать string для ключей, int для значений. Ещё в словаре могут быть методы для удаления ключей, для итерации по всем записям, получение количества элементов и много других важных и приятных мелочей, которые мы опустим.
Картинка первая. Линейный массив.
Самый простой способ для хранения пар «ключ, значение» - это создание класса или структуры Node (узел) и декларация линейного массива сих пар.
Для поиска узла по ключу необходимо просканировать весь массив от начала до конца и в каждом узле проверять, не совпало ли значение. Если совпало - вернуть найденное значение, если сканирование завершилось, а значение так и не было найдено - рапортуем, что не найдено. На это нужно N операций.
class ArrayStorage : IStorage
{
int size;
Node[] array;
private Node empty = new Node(null, 0);
public ArrayStorage(int N)
{
array = new Node[N];
size = 0;
}
private Node find(string key)
{
for (int j = 0; j < size; j ++)
if (array[j].key == key)
return array[j];
return empty;
}
public int get(string key)
{
return find(key).value;
}
Для добавления новой пары достаточно в конец массива вписать новый узел, это быстро, всего 1 операция. Однако, прежде чем добавить новый узел, мы должны убедиться, что в словаре нет узла с точно таким же значением ключа, для этого необходимо вызвать метод поиска. Если такой ключ есть - мы записываем новое значение на место старого.
public void put(string key, int value)
{
Node node = find(key);
if (node.key == null)
array[size++] = new Node(key, value);
else
node.value = value;
}
}Сколько памяти выделять для словаря? Какого размера массив необходимо декларировать для эффективной работы? Если размер массива будет совпадать с количеством элементов, то при каждом добавлении пары необходимо пересоздавать массив увеличенного размера и заниматься копированием значений из старого массива в новый, а это, на минуточку, N действий для каждой операции добавления элемента.
Чтобы избежать тьмы лишних действий, можно выделять массив удвоенного размера, тогда процесс пересоздания массива добавит к сложности алгоритма лишь Log N операций, однако размер требуемой памяти удвоится.
Сложность поиска: N операций = O(N).
Сложность вставки: N (поиск) + Log N (пересоздание) + 1 (вставка) = O(N).
Требование к памяти: N (словарь) + N (резерв) = O(N).
Вывод: простой, но медленный способ, двойной расход памяти
Картинка вторая. Односвязный список.
Есть идеи по экономии памяти, но чтобы при этом не нужно было тратиться на дополнительные операции по пересозданию массива и копированию элементов? Ответ лежит на поверхности: односвязный список! Это динамическая структура, которая занимает ровно столько место, сколько в ней элементов и позволяет легко добавлять новые сущности.
Как видим, в класс узла добавилось ещё одно поле next - указатель на следующий элемент списка (между нами говоря, накладные расходы на необходимость хранить этот указатель могут свести на нет то, ради чего мы, собственно, и).
Сложность поиска узла по ключу не изменилась - нам вновь необходимо сканировать весь список от начала до конца, прыгая по кочкам списка.
class LinkedListStorage : IStorage
{
private Node root = null;
private Node empty = new Node(null, null);
private Node find(string key)
{
for (Node curr = root; curr != null; curr = curr.next)
if (curr.key == key)
return curr;
return empty;
}
public int get(string key)
{
return find(key).value;
}Сложность добавления элемента значительно ускорился - нет дополнительных расходов на пересоздание массива, а новые пары удобнее всего добавлять в начало списка. Обратите внимание, что на рисунке порядок расположения пар реверсивен: кот был первым, а стал последним.
public void put(string key, int value)
{
Node node = find(key);
if (node.key == null)
root = new Node(key, value, root);
else
node.value = value;
}
}Сложность поиска: N операций = O(N).
Сложность вставки: N (поиск) + 1 (вставка) = O(N).
Требование к памяти: N (словарь) = O(N).
Вывод: простой, но медленный способ, эффективен по памяти.
А можно ли как-то ускорить процесс поиска ключей? Линейное время, это слишком медленно и применимо лишь на малых размерах словаря. Можно.
Картина третья. Отсортированный список.
В книжных словарях слова расположены по алфавиту, что позволяет искать их значительно быстрее, за логарифмическое время. Например, для поиска ключа в отсортированном списке из 1000 записей достаточно сделать всего десять сравнений, потому как 2^10 = 1024.
Давайте и мы попробуем располагать ключи в алфавитном порядке.
Теперь для поиска ключа можно применить бинарный поиск: смотрим, какой элемент посередине списка находится и рекурсивно продолжаем поиск либо в первой половине, либо во второй. Время поиска O(Log N).
class SortedStorage : IStorage
{
int size;
Node[] array;
public SortedStorage(int N)
{
array = new Node[N];
size = 0;
}
public string get(string key)
{
return get(key, 0, size - 1);
}
int get(string key, int low, int high)
{
if (low > high)
return null;
int mid = (low + high) / 2;
if (array[mid].key == key)
return array[mid].value;
if (key > array[mid].key)
return get(key, mid + 1, high);
else
return get(key, low, mid - 1);
}Для добавления новой пары в словарь нужно сначала найти индекс в массиве, куда следует вставить пару, чтобы ключи располагались в алфавитном порядке, на это нужно Log N операций. Затем нужно сдвинуть все элементы на одну позицию вперёд и в освободившееся место разместить новую пару. Хотел бы обратить внимание, что сдвигать элементы нужно с хвоста поезда.
public void put(string key, int value)
{
int j;
for (j = 0; j < size; j++)
if (array[j].key == key)
{
array[j].value = value;
return;
}
else if (key < array[j].key)
break;
for (int t = size; t > j; t--)
array[t] = array[t - 1];
array[j] = new Node(key, value);
size++;
}
}
На сдвиг элементов может потребоваться до N действий. Возможны дополнительные операции на пересоздание и копирование массива в размере Log N.
Сложность поиска: Log N операций = O(Log N).
Сложность вставки: Log N (поиск) + Log N (пересоздание) + N (сдвиг) + 1 (вставка) = O(N).
Требование к памяти: N (словарь) + N (резерв) = O(N).
Вывод: логарифмический поиск, линейное добавление, двойной расход памяти.
Кстати, а можно ли уменьшить расходы по памяти, используя для хранения пар односвязный отсортированный список? Увы, нельзя. Потому как мы можем только скользить по односвязному списку, без возможности перехода к любому элементу по индексу. А отличительная черта обычного массива - это моментальный доступ к любому элементу по его индексу, что и используется при двоичном поиске ключа в отсортированном массиве.
Впрочем, мы можем отказаться от излишних копирований и сдвигов элементов, если для хранения словаря воспользуемся двоичным деревом поиска.
Но об этом в следующей статье. А сейчас приглашаю всех на бесплатный урок по теме: "Создание ассоциативного массива на базе хэш-таблицы и префиксного дерева".
Зарегистрироваться на бесплатный урок
