Таблица перехода структуры данных

предисловие

Реализация кода прилагается.Лифт прямой

Вы также можете получить его, ответив на [Пропустить таблицу] в официальном аккаунте.

Что такое пропускной стол

Таблица пропуска — это структура данных. Это позволяет быстро запрашивать связанный список упорядоченных смежных элементов. Средняя сложность времени поиска и вставки для списков пропуска составляет O(log n), что лучше, чем O(n) для обычных очередей.

из Википедии

цитата

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

Массив представляет собой непрерывную в памяти структуру данных, которая имеет то преимущество, что ее можно首地址+N*(sizeOf(Node))Чтобы быстро получить элемент в указанной позиции Что делать, если мы не знаем позицию указанного элемента?

Связный список — это тип непрерывных данных, не связанных с памятью, и его преимущество в том, что элементы можно быстро добавлять или вычитать, изменяя адрес указателя. Очевидная проблема, вам сначала нужно знать, какой целевой элемент вы хотите добавить/удалить!O(n)время запроса.

С точки зрения эффективности необходимо сказать, что сбалансированное дерево (AVL) вверх. Эффективность добавления и удаленияO(logN). Но такая структура данных, принцип сложнее, ее не сложнее реализовать, она достаточно сложна. Добавления и удаления требуют, чтобы они полагались на операции балансировки для запуска корректировок поддерева.

Итак, аплодисменты нашему сегодняшнему герою:пропустить стол.

пропустить стол

концепция

пропустить стол (skip list) полное имя Список переходов. Это связанная структура данных, похожая на список.

Производительность таблицы пропуска такая же, как производительность сбалансированного дерева.Временная сложность вставки, удаления и поискаO(n), представляет собой структуру данных, которая использует пространство вместо времени.

Таблица пропуска — это рандомизированная структура данных, которая в настоящее время используется программным обеспечением с открытым исходным кодом Redis и LevelDB.

Вот, позвольте мне показать вамвозможныйСтруктура таблицы пропуска.

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

Давайте проанализируем приведенную выше структуру таблицы пропусков.

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

Допустим, мы ищем5Этот элемент в отдельном упорядоченном списке мы должны пройти от головного узла к5этот узел. путь1->2->3->4->5, путь желтой линии на изображении ниже. , теперь нам нужно только начать с1->2->4->5.Путь фиолетовой линии на изображении ниже. Поскольку мы можем абстрагировать новый связанный список от исходного связанного списка, мы также можем абстрагировать новый связанный список от нового связанного списка. В этом случае вы можете напрямую1->4->5, вы можете найти один из наших целевых узлов.

Если вы видите это, я расскажу вам важную концепцию.

Слой: это новый связанный список, который мы считаем абстрагированным.

Может быть, вам интересно, как мы должны хранить слой?Это очень просто!

Как будут определены элементы каждого связанного списка в будущем?

typedef struct NODE {
    T data;
    Node *next;
} node;

Нам просто нужно изменить указатель на следующий элемент на массив указателей!

typedef struct NODE {
    T data;
    /// 指向后继元素的指针数组
    struct Node *next[i];
} node;

Разобравшись, как хранить, как определить, сколько слоев у ноды?Вот я вам говорю, рандомно! Как это случайно?Оно определяется случайными числами, что является формой подбрасывания монеты, которую мы часто говорим. Например следующий код.

/**
 * 生成一个随机数
 * @return 一个随机数
 */
int random_level() {
    int level = 1;
    while (rand() % 2) {
        level++;
    }
    level = (level < MAX_LEVEL) ? level : MAX_LEVEL;
    return level;
}

Затем мы пытаемся реализовать таблицу пропуска.

Реализация таблицы пропуска

Определить структуру таблицы пропуска

После приведенного выше анализа указатель каждого узла на следующий узел представляет собой массив, поэтому мы получаем следующую структуру. (Конечно, есть и другие способы достижения, добро пожаловать на общение~)

/// 节点
NODE {
    T data,
    /// 指向下一个节点的数组，从1开始。
    /// 数组中的每个元素对应该层的下一个节点
    /// next[1],是第一层的下一个节点的地址。
    /// next[2] 是第二层的下一个节点的地址。
    NODE []next;
}

/// 跳表
SKIP_LIST{
    NODE head;
    /// 该跳表的层数
    int level;
}

Найти указанный элемент

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

Основная логика такова: поиск с верхнего уровня до тех пор, пока не будет найдена вершина E, равная указанному элементу, или первая вершина G, которая больше заданного элемента. Если это узел E, то просто вернитесь напрямую. Если это узел G, то используйте предыдущий узел L узла G для поиска на следующем уровне и повторяйте описанную выше логику до тех пор, пока не будет найден узел E или не будет достигнут конец списка пропуска.

Например, найдите рисунок ниже5Процесс:

head->8, 8>5,отheadНачните, перейдите на следующий уровень, чтобы найти.
head->4->8, 8>5,от4элемент для начала поиска. Перейдите на следующий уровень, чтобы найти
head->4->8, 8>5,от4элемент для начала поиска. Перейти на следующий уровень, чтобы найти.
head->4->6, 6>5,от4элемент для начала поиска. Перейти на следующий уровень, чтобы найти.
head->4->5, 5==5, возвратный узел5.

Например, следующий псевдокод.

search() {
    /// i 表示层数，从最高层开始查找 。
    for (; i >= 0; i--) {
        while ((q = p->next[i]) && q->k < k) {
            p = q;
        }
        if (q && k == q->data) {
            return &(q->data);
        }
    }
}

Составьте таблицу пропусков.

Из вышеприведенного анализа можно сделать вывод, что список переходов представляет собой многоуровневый упорядоченный связанный список. Таким образом, мы можем сделать это как обычный связанный список для каждого слоя. Как следующее:

insert () {
    // 找到要插入的节点位置。
    // level是本跳表的层数
    for (i = level-1; i >= 0; i--) {
        ///遍历该层小于指定值的前一个元素
        while ((q = p->next[i]) && q->k < k) {
            p = q;
        }
        /// 新节点的前一个节点的层指针。
        update[i] = p;
    }

    // 随机生成该节点的层数,如果生成的层数大于当前层，需要更新跳表中记录的level值。
    new_level = rand_level();
    if(new_level > level) {
        level = new_level;
    }
    
    // 生成新的节点，并针对每一层执行普通链表的插入操作。
    new_node = create_new_node();
    for (i = level - 1; i >= 0; i--) {
        /// 下面两行代码就是普通连接的增加方法。
        /// 新节点的前一个节点的第i层的节点。
        new_node->next[i] = update[i]->next[i];
        update[i]->next[i] = q;
    }
}

удалить элемент списка пропуска

Основная логика заключается в том, что каждый слой узла должен быть удален.

То есть для каждого слоя предыдущий узел удаляемого узла указывает на следующий узел удаляемого узла.

del() {
    /// 找到要删除的节点
    for (; i >= 0; --i) {
        while ((q = p->next[i]) && q->k < k) {
            p = q;
        }
        update[i] = p;
    }
}

Код

Реализовано:

пропустить столCязыковая версия

пропустить столJAVAВерсия

другие языки, такие какpython, golang, c++, js, php, kotlinкод версии, вы заинтересованы в создании волны?адрес

Вы можете выбрать язык, с которым вы знакомы. Код реализации предназначен только для справки. Если у вас есть какие-либо идеи, добро пожаловать на обмен wow~, пожалуйста, не стесняйтесь дать мне несколько советов!

Герои также могут отправить код своего языка на склад~, провести мозговой штурм и пообщаться вместе! С нетерпением жду~~

(Структуры данных и алгоритмы на складе постоянно обновляются, добро пожаловатьstar)

Анализ временной сложности

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

Если не очень понятно, можно подумать и так:

Если каждые два узла извлекают один узел в качестве узла индекса верхнего уровня, количество узлов в индексе первого уровня приблизительно равноn/2, индекс второго уровняn/4, третий уровеньn/8. То есть,kКоличество инодов уровняn/(2^k);

Предположим, у нас естьhуровень, индекс верхнего уровня имеет2узлы, то естьn/(2^k)=2, Так k=log_2N-1 , высота этого связанного списка равна log_2N , Если каждый слой должен быть пройденmузлов, то временная сложность запроса данных в таблице пропуска равнаO(m*logN).

Из-за существования случайного распределения мы можем рассматривать m как константу, поэтому временную сложность можно грубо рассматривать какO(logN)

Анализ космической сложности

В соответствии с общей реализацией кода мы используем форму связанного списка для реализации.nextОн изменен на массив для хранения указателя следующего узла, и нет никакого реального объекта хранения, то есть мы фактически не используем много памяти, конечно, это все же больше, чем общий связанный список . Для объектов, которые мы храним, память, используемая для хранения указателей, может быть напрямую проигнорирована. Временная сложностьO(N+m),вN>>m(Nнамного больше, чемm).

сравнивать

Сравнение таблицы пропуска со сбалансированным деревом и хеш-таблицей

	пропустить стол	Сбалансированное дерево	хеш-таблица
упорядоченность	аккуратный	аккуратный	беспорядок
Найти производительность	O(logN)	O(logN)	O(N)
реализовать логику	Простой	сложный	Простой
Поддерживать ли поиск диапазона	служба поддержки	служба поддержки	Не поддерживается (неупорядоченный)
временная сложность	меньше, в зависимости от параметра p	Больше (по сравнению с таблицей переходов, занимающей по два указателя левого и правого поддеревьев)	в общем

Объяснение следующее:

При поиске по диапазону сбалансированные деревья сложнее, чем операции с пропуском списка. В сбалансированном дереве после того, как мы найдем малое значение в указанном диапазоне, нам нужно продолжить поиск других узлов, которые не превышают большое значение в порядке обхода по порядку. Без какой-либо модификации сбалансированного дерева обход по порядку здесь осуществить непросто. Поиск диапазона в таблице пропуска очень прост, сразу после нахождения небольшого значения,1Это может быть достигнуто путем обхода иерархического связанного списка в несколько шагов.
Добавление и удаление сбалансированного дерева может вызвать корректировку баланса поддерева, в то время как вставка и удаление таблицы пропуска требуют только изменения указателя соседнего узла, и операция выполняется просто и быстро.
С точки зрения использования памяти таблица пропуска более гибкая, чем сбалансированное дерево. В общем случае каждый узел сбалансированного дерева содержит2указателей (указывающих на левое и правое поддеревья соответственно), а среднее количество указателей, содержащихся в каждом узле таблицы переходов, равно1/(1-p), в зависимости от параметраpразмер. если что-то вродеRedisаналогична реализации вp=1/4, то в среднем каждый узел содержит1.33указатели, которые более выгодны, чем сбалансированные деревья.
найти одинkey, временная сложность списка пропуска и сбалансированного дереваO(log n), примерно эквивалентно; в то время как хеш-таблица поддерживает низкую вероятность столкновения хеш-значений, сложность времени поиска близка кO(1), производительность выше.

я тоже видела в инетеRedisавторов выбирают список пропуска какzsetПричина базовой структуры данных размещена ниже.

`Redis`Причины, по которым автор выбрал SkipList:

There are a few reasons:

Они не очень требовательны к памяти. В основном это зависит от вас. Изменение параметров вероятности узла иметь заданное количество уровней сделает их менее требовательными к памяти, чем b-деревья.

A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

Суммировать

Простой анализ барьеров производительности массивов и связанных списков с точки зрения производительности приводит к нашему сегодняшнему главному герою: списку пропуска.
Нарисуйте возможную структуру таблицы пропуска Это первая встреча с таблицей пропуска. И внедрил замаскированное приложение бинарного поиска. В настоящее время все это основано на предпосылке упорядоченных связанных списков.
Введено понятие слоя связанного списка, которое является наиболее важным и единственным понятием пропускаемого списка по отношению к связанному списку, при этом временная сложностьO(logN)эффективность запросов, так что временная сложность операций добавления и удаления такжеO(logN).
Далее мы вместе завершили логику реализации таблицы пропуска. И он предоставляет версию реализации таблицы пропуска на нескольких языках.Я надеюсь, что вы также отправите код на склад, и мы будем общаться вместе и с нетерпением ждем его.
Так же в процессе разработки есть несколько вариантов таблицы пропуска, а у нас как раз самая простая реализация. Оптимальное решение по количеству элементов и количеству слоев мы даже не рассматривали, позже будет статья, в которой поделимсяRedisсерединаskiplistРеализация. Пожалуйста, ждите этого~

В конце концов

Ждем вашего внимания, давайте общаться и учиться вместе~