Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня я продолжу знакомить с часто используемыми структурами данных в распределенных системах.Структура данных, которую мы представим сегодня, очень примечательна.Как и фильтр Блума, представленный ранее, это мощная структура данных с простыми принципами. И у него меньше недостатков и недостатков, и он более широко используется.Например, его использует широко распространенный Redis.
Введение в SkipList
SkipList — это структура данных, которая позволяет быстро искать, добавлять и удалять данные.
Добавление и удаление сложности. С точки зрения временной сложности оно похоже на сбалансированное дерево, но по сравнению со сбалансированным деревом имеет меньшую сложность кода и проще в реализации. Все студенты, изучавшие структуру данных, должны знать, что сбалансированное дерево часто нуждается в операции поворота для поддержания баланса поддеревьев с обеих сторон, что не только сложно кодировать и трудно понять, но и очень неудобно отлаживать. SkipList преодолевает эти недостатки, принцип прост и очень удобен в реализации.
принцип
Суть SkipList — это List, то есть связанный список. Все мы знаем, что связанный список представляет собой линейную структуру, и за раз можно перемещать только один узел, поэтому сложность получения и удаления элементов связанного списка одинакова.
.
Если мы хотим оптимизировать эту проблему, мы можем добавить указатель к общему узлу, чтобы указать на следующие два элемента. Таким образом, скорость нашего обхода может быть удвоена, а самый быстрый
пройти весь связанный список во времени.
Точно так же, если мы продолжим увеличивать количество указателей на узле, то эту скорость можно еще больше ускорить. Теоретически, если мы установим
указатель, который может быть полностью
Полный поиск элементов за определенное время, что является сутью SkipList.
Но есть проблема, что нам мало добиться быстрого поиска, нам нужно еще и обеспечить порядок элементов, иначе поиск будет невозможен. Однако порядок, в котором добавляются элементы, не обязательно соответствует порядку.Как мы можем гарантировать, что количество указателей, выделенных узлам, является разумным?
Чтобы решить эту проблему, SkipList вводит механизм случайной глубины, то есть количество указателей, которые может иметь узел, является случайным. Та же стратегия используется для обеспечения максимально равномерного распределения элементов во избежание перекоса данных.
Я думаю, что эта картинка должна быть понятна, когда она будет выпущена, и каждый узел можно представить как небольшое здание. Множественные указатели каждого узла можно рассматривать как различные этажи небольшого здания.Очевидно, что, поскольку все маленькие здания расположены в ряд, каждый этаж каждого здания может видеть только ближайший с той же высотой.
Например, 2 на приведенном выше рисунке имеет только один этаж, поэтому он может видеть только положение ближайшего первого этажа, который равен 3. 4 имеет три слоя. Его первый слой может видеть только 5, но второй и третий слои могут видеть 6. 6 также имеет три слоя. Поскольку ни один узел после 6 не имеет более двух слоев, его третий слой может быть иду прямо до конца .
Поскольку высота каждого узла является случайной, ситуация, которую может видеть каждый узел, разбросана, что может предотвратить такие проблемы, как неравномерное агрегирование данных, тем самым обеспечивая эффективность работы.
Реализовать узел
Я думаю, что каждый может понять принцип структуры данных, но если вы хотите начать, вы обнаружите, что это все еще немного сложно, и будет много деталей и граничных проблем. Это нормально, мой личный опыт заключается в том, чтобы начинать с простых частей и оставлять сложные части на конец. По мере прогресса понимание проблемы и способность решить проблему будут улучшаться, так что боль будет наименьшей, а возможность сдаться на полпути — наименьшей.
В дальнейшем содержании мы также придерживаемся этого принципа, начиная с простой части.
Определите структуру узла
Весь SkipList, по сути, представляет собой связанный список.Поскольку это связанный список, конечно, в нем есть узлы, поэтому мы можем начать с определения структуры узлов. Поскольку нам нужно поле для поиска и поле для хранения результата, очевидно, что ключ и значение являются обязательными полями. Кроме того, каждый узел будет иметь список указателей, записывающих местоположение, на которое можно указать. Таким образом, получается структура этого типа Node:
class Node:
def __init__(self, key, value=None, depth=1):
self._key = key
self._value = value
# 一开始全部赋值为None
self._next = [None for _ in range(depth)]
self._depth = depth
@property
def key(self):
return self._key
@key.setter
def key(self, key):
self._key = key
@property
def value(self):
return self._value
@value.setter
def value(self, value):
self._value = value
Некоторые студенты могут не понять аннотаций к методу Вот краткое введение. Это объектно-ориентированная спецификация в Python, потому что Python не делает различий между публичными и приватными полями, как в C++ или Java, а все поля в Python являются публичными. Очевидно, что это небезопасно, и иногда мы не хотим, чтобы вызывающая сторона получала всю нашу информацию. Поэтому в Python все оговаривают, что перед именем переменной добавляется знак подчеркивания, чтобы обозначить приватную переменную, чтобы и вызывающая сторона, и разработчик, читающий код, знали, что это приватная переменная.
В Java по умолчанию мы предоставляем общедоступные методы получения и установки для частных переменных, которые необходимо использовать, и то же самое верно и в Python. Однако Python предоставляет мощные аннотаторы. Мы можем упростить написание кода, добавив аннотации @property и @param.setter. С аннотациями Python автоматически сопоставляет имена методов и имена аннотаций. Например, имя переменной, определенное внутри нашего класса, — _key, но через аннотацию мы можем вызвать ее через node.key вне класса, и интерпретатор Python автоматически выполнит метод, который мы аннотировали. И когда мы присвоим ему значение, будет вызван и соответствующий метод.
Например, когда мы запускаем: node.key = 3, Python фактически выполняет node.key(3) внутри. Конечно, мы можем написать set и get и без аннотаций, это просто дело привычки, и в этом нет никакой проблемы.
добавить метод узла
После того, как мы определим структуру Node, она не заканчивается, потому что в этой задаче нам нужно получить доступ к n-му указателю узла.Конечно, мы также можем добавить аннотации к _next, как указано выше, а затем получить доступ через аннотации и индексы. Но это, в конце концов, более хлопотно, особенно если мы также задействуем суждение о том, является ли узел None, видим ли мы хвост и т. д. Чтобы облегчить написание кода, мы можем абстрагировать их в методы узла. класс.
Мы добавляем следующий метод в класс Node:
# 为第k个后向指针赋值
def set_forward_pos(self, k, node):
self._next[k] = node
# 获取指定深度的指针指向的节点的key
def query_key_by_depth(self, depth):
# 后向指针指向的内容有可能为空，并且深度可能超界
# 我们默认链表从小到大排列，所以当不存在的时候返回无穷大作为key
return math.inf if depth > self._depth or self._next[depth] is None else self._next[depth].key
# 获取指定深度的指针指向的节点
def forward_by_depth(self, depth):
return None if depth > self._depth else self._next[depth]
Эти три метода не должны быть сложными для понимания.Единственная проблема заключается в методе query_key_by_depth.В этом методе у нас есть бесконечный набор случаев, которых не существует. Сначала мы можем поместить сюда логику возврата в бесконечность, и мы поймем это позже, когда будем реализовывать Skiplist.
После добавления этих трех методов наш класс Node реализован, и можно написать следующее тело SkipList.
Реализовать список пропуска
Затем наступает главное событие.Мы также следуем принципу сначала легкое, а затем сложное, и реализуем сначала более простую часть.
Во-первых, давайте реализуем конструктор SkipList и функцию, которая случайным образом генерирует глубины узлов. Что касается глубины узла, вероятность p будет рассчитана в SkipList. Каждый раз случайным образом выбирается значение с плавающей запятой 0-1.Если оно больше p, то глубина увеличивается на единицу, в противном случае возвращается текущая глубина.Чтобы предотвратить взрыв глубины в крайних случаях, мы также устанавливаем максимальная глубина.
В SkipList помимо определения головного узла также требуется хвостовой узел, который представляет собой конец связанного списка. Поскольку мы хотим, чтобы SkipList выполнял быстрый запрос, элементы в SkipList упорядочены.Чтобы обеспечить порядок, мы устанавливаем ключ головы на бесконечность, а ключ хвоста на бесконечность. И задний указатель нашей головы по умолчанию заполнен, все указывает на хвост. После того, как логика понятна, код не сложный:
class SkipList:
def __init__(self, max_depth, rate=0.5):
# head的key设置成负无穷，tail的key设置成正无穷
self.root = Node(-math.inf, depth=max_depth)
self.tail = Node(math.inf)
self.rate = rate
self.max_depth = max_depth
self.depth = 1
# 把head节点的所有后向指针全部指向tail
for i in range(self.max_depth):
self.root.set_forward_pos(i, self.tail)
def random_depth(self):
depth = 1
while True:
rd = random.random()
# 如果随机值小于p或者已经到达最大深度，就返回
if rd < self.rate or depth == self.max_depth:
return depth
depth += 1
На данный момент мы сделали еще один шаг вперед, и осталось только три метода добавить, удалить и проверить из окончательной реализации. Логика модификации и поиска в основном одинакова, и в этом типе структуры данных модификация вообще не реализована, потому что модификация может быть заменена удалением и добавлением, а в случае больших данных модификация происходит редко.
метод запроса
Среди трех методов запрос является самым простым, потому что мы уже поняли логику поиска. Алгоритм похож на жадный, и сказать его очень просто.Мы пытаемся каждый раз оглядываться назад с самого верхнего этажа.Если значение, которое мы видим, меньше, чем искомый в данный момент ключ, то мы перескакиваем, иначе это означает что мы видели слишком много.Если это далеко, мы должны посмотреть поближе, поэтому мы спускаемся вниз и повторяем описанный выше процесс.
Например, на приведенном выше рисунке предположим, что мы хотим найти 20. Во-первых, мы оглядываемся на самую высокую точку положения головы и прямо видим положительную бесконечность.Она больше 20, что указывает на то, что мы смотрим слишком далеко и должен опуститься на один уровень. Итак, мы пошли на 4-й этаж, в этот раз мы увидели 17, что меньше 20, поэтому мы переехали туда.
После перехода к 17 мы все равно начнем с 4-го слоя, а затем обнаружим, что элементы, видимые на каждом слое, больше или равны 20, так что 17 — это ближайший к 20 элемент (возможно, что 20 не существует) . Затем мы перемещаемся на один пробел назад от 17, где может появиться 20. Если эта позиция не 20, то 20 не существует.
Эту логику следует хорошо понимать.В сочетании с несколькими инструментами и методами, которые мы добавили в Node ранее, код занимает всего несколько строк:
def query(self, key):
# 从头开始
pnt = self.root
# 遍历当下看的高度，高度只降不增
for i in range(self.depth-1, -1, -1):
# 如果看到比目标小的元素，则跳转
while pnt.query_key_by_depth(i) < key:
pnt = pnt.forward_by_depth(i)
# 走到唯一可能出现的位置
pnt = pnt.forward_by_depth(0)
# 判断是否相等，如果相等则说明找到
if pnt.key == key:
return True, pnt.value
else:
return False, None
метод удаления
Метод запроса реализован, и удаление не за горами. Поскольку мы хотим удалить узел, нам, очевидно, нужно сначала найти узел, поэтому мы можем повторно использовать код поиска, чтобы найти, где может существовать удаляемый узел.
Поиск местоположения не является одноразовым, мы удаляем его, это может повлиять на другие элементы.
Возьмем в качестве примера изображение выше, предположим, что мы хотим удалить элемент 25. Так что же происходит?
Это не повлияет на элементы после 25, потому что обратный указатель после узла повлияет на узлы, указывающие на 25, в этом примере на узел 17. Поскольку 25 удаляется, указатель 17 должен пройти через позицию 25 и продолжить указывать на следующие элементы, то есть 55 и 31. .
Легче понять, что если мы найдем эти указатели на 25, позицию после их модификации определить относительно легко, потому что на самом деле это позиция, на которую указывает элемент 25. Но как заставить эти элементы указывать на 25?
Если просто вдуматься, то кажется, что понятия нет, но когда совмещаешь с картинкой, то понять несложно.Помнишь жадный метод, которым мы каждый раз заглядывали как можно дальше, когда искали? Разве элемент, где мы выполняем операцию «внизу», не является ближайшей позицией, которая может видеть 25? То есть, мы можем записать место, где произошел спуск вниз во время процесса поиска.
После того, как я понял это, код готов к выходу.Он в основном такой же, как код запроса, но есть еще несколько строк, чтобы справиться с этим моментом.
def delete(self, key):
# 记录下楼位置的数组
heads = [None for _ in range(self.max_depth)]
pnt = self.root
for i in range(self.depth-1, -1, -1):
while pnt.query_key_by_depth(i) < key:
pnt = pnt.forward_by_depth(i)
# 记录下楼位置
heads[i] = pnt
pnt = pnt.forward_by_depth(0)
# 如果没找到，当然不存在删除
if pnt.key == key:
# 遍历所有下楼的位置
for i in range(self.depth):
# 由于是从低往高遍历，所以当看不到的时候，就说明已经超了，break
if heads[i].forward_by_depth(i).key != key:
break
# 将它看到的位置修改为删除节点同样楼层看到的位置
heads[i].set_forward_pos(i, pnt.forward_by_depth(i))
# 由于我们维护了skiplist当中的最高高度，所以要判断一下删除元素之后会不会出现高度降低的情况
while self.depth > 1 and self.root.forward_by_depth(self.depth - 1) == self.tail:
self.depth -= 1
else:
return False
метод вставки
Наконец, есть метод вставки элементов.Перед вставкой нам также нужно выполнить поиск, потому что мы хотим поместить элемент в правильное положение.
Если в этой позиции уже есть элемент, то мы напрямую модифицируем его значение.По сути, это операция модификации.Если она предназначена для запрета модификации, то может и вернуть отказ. Процесс вставки также влияет на содержимое, на которое указывают указатели других элементов.Мы обнаружим, что процесс вставки и удаления на самом деле противоположен. В процессе удаления нам нужно указать x на позицию, на которую указывает x, в то время как вставка противоположна.Нам нужно указать указатель за x на x, а также нужно обновить позицию, на которую указывает x.Если вы может понять удалить, значит понять вставить На самом деле это гвоздь в гроб.
Давайте посмотрим непосредственно на код:
def insert(self, key, value):
# 记录下楼的位置
heads = [None for _ in range(self.max_depth)]
pnt = self.root
for i in range(self.depth-1, -1, -1):
while pnt.query_key_by_depth(i) < key:
pnt = pnt.forward_by_depth(i)
heads[i] = pnt
pnt = pnt.forward_by_depth(0)
# 如果已经存在，直接修改
if pnt.key == key:
pnt.value = value
return
# 随机出楼层
new_l = self.random_depth()
# 如果楼层超过记录
if new_l > self.depth:
# 那么将头指针该高度指向它
for i in range(self.depth, new_l):
heads[i] = self.root
# 更新高度
self.depth = new_l
# 创建节点
new_node = Node(key, value, self.depth)
for i in range(0, new_l):
# x指向的位置定义成能看到x的位置指向的位置
new_node.set_forward_pos(i, self.tail if heads[i] is None else heads[i].forward_by_depth(i))
# 更新指向x的位置的指针
if heads[i] is not None:
heads[i].set_forward_pos(i, new_node)
На этом весь код заканчивается. Как сказать, хотя его принцип нетрудно понять, но написать код довольно хлопотно, потому что он включает в себя работу и работу указателя, его нелегко написать и отладить правильно. Но по сравнению с пресловутыми типами сбалансированных деревьев это уже очень просто.
SkipList широко используется в различных распределенных системах и приложениях, это очень важная базовая конструкция, поэтому ее стоит изучить. И я лично считаю, что эта структура данных очень гениальна, и принцип, и кодировка очень интересны, надеюсь, всем понравится.
На сегодняшней статье все, если вы найдете что-то полезное, пожалуйстаОтсканируйте код и обратите вниманиеЧто ж, твое маленькое усилие много значит для меня.