Skip List в Golang

Kate · Воскресенье в 16:03

Сегодня я решил поделиться с вами одной из тех структур данных, которая, возможно, не так популярна, как хеш‑таблицы или деревья, но обладает своими уникальными фичами. Знакомьтесь — Skip List!

Итак, Skip List — это структура данных, которая позволяет быстро искать, вставлять и удалять элементы. Можно сказать, что это своего рода гибрид между списком и деревом, только без всяких заморочек.

Рассмотрим реализацию этой структуры в Golang, и для этого есть пакет huandu/skiplist.

Начнем с самого простого — установки библиотеки. Откройте терминал и введите:

go get github.com/huandu/skiplist

Создание и использование Skip List

Ничего сложного здесь нет.

package main

import (
"fmt"
"github.com/huandu/skiplist"
)

func main() {
// Создаем Skip List с ключами типа int
list := skiplist.New(skiplist.Int)

// Добавляем элементы
list.Set(10, "десять")
list.Set(20, "двадцать")
list.Set(30, "тридцать")

// Получаем элемент по ключу
elem := list.Get(20)
if elem != nil {
fmt.Println("Ключ:", elem.Key(), "Значение:", elem.Value)
}

// Итерация по элементам
for elem := list.Front(); elem != nil; elem = elem.Next() {
fmt.Printf("Ключ: %v, Значение: %v\n", elem.Key(), elem.Value)
}

// Удаление элемента
list.Remove(20)
fmt.Println("После удаления ключа 20:")
for elem := list.Front(); elem != nil; elem = elem.Next() {
fmt.Printf("Ключ: %v, Значение: %v\n", elem.Key(), elem.Value)
}
}
Мы начинаем с инициализации нового Skip List с ключами типа int, затем вставляем три элемента с ключами 10, 20 и 30. Далее ищем элемент с ключом 20 и выводим его значение. После этого проходимся по всем элементам списка, выводя их на экран. Наконец, удаляем элемент с ключом 20 и снова отображаем обновленный список.

Вывод программы:

Ключ: 20 Значение: двадцать
Ключ: 10, Значение: десять
Ключ: 20, Значение: двадцать
Ключ: 30, Значение: тридцать
После удаления ключа 20:
Ключ: 10, Значение: десять
Ключ: 30, Значение: тридцать
Просто, как дважды два, правда. Но копнем чуть глубже и узнаем, как можно использовать эту структуру эффективней.

Кастомизация

Иногда стандартных возможностей недостаточно. Например, нужно использовать структуру в качестве ключа и сортировать элементы по какому‑то специфическому критерию.

Создадим Skip List, где ключами будут структуры с углами в радианах, и отсортируем их по значению синуса.

package main

import (
"fmt"
"math"
"github.com/huandu/skiplist"
)

type Angle struct {
Rad float64
}

func main() {
// Создаем Skip List с кастомной функцией сравнения
list := skiplist.New(skiplist.GreaterThanFunc(func(a, b interface{}) int {
angleA := a.(Angle).Rad
angleB := b.(Angle).Rad
sinA := math.Sin(angleA)
sinB := math.Sin(angleB)
switch {
case sinA > sinB:
return 1
case sinA < sinB:
return -1
default:
return 0
}
}))

// Добавляем элементы
list.Set(Angle{Rad: math.Pi / 8}, "sin(π/8)")
list.Set(Angle{Rad: math.Pi / 2}, "sin(π/2)")
list.Set(Angle{Rad: math.Pi}, "sin(π)")

// Выводим элементы в порядке сортировки
for elem := list.Front(); elem != nil; elem = elem.Next() {
fmt.Printf("Ключ: %.2f, Значение: %v\n", elem.Key().(Angle).Rad, elem.Value)
}
}
Определили структуру Angle с полем для угла в радианах, настроили Skip List с пользовательской функцией сравнения на основе значений синуса углов, добавили три таких угла с соответствующими значениями синуса и вывели их. В результате элементы отсортировались по возрастанию значения синуса.

Вывод программы:

Ключ: 3.14, Значение: sin(π)
Ключ: 1.57, Значение: sin(π/2)
Ключ: 0.39, Значение: sin(π/8)
Элементы отсортированы не по значению угла, а по значению его синуса

Потокобезопасность

К сожалению, huandu/skiplist не предоставляет встроенной поддержки потокобезопасности, но ничего страшного. Добавим сами с помощью sync.RWMutex:

package main

import (
"fmt"
"sync"
"github.com/huandu/skiplist"
)

type SafeSkipList struct {
list *skiplist.SkipList
mutex sync.RWMutex
}

func NewSafeSkipList(comparable skiplist.Comparable) *SafeSkipList {
return &SafeSkipList{
list: skiplist.New(comparable),
}
}

func (s *SafeSkipList) Set(key, value interface{}) {
s.mutex.Lock()
defer s.mutex.Unlock()
s.list.Set(key, value)
}

func (s *SafeSkipList) Get(key interface{}) (interface{}, bool) {
s.mutex.RLock()
defer s.mutex.RUnlock()
return s.list.GetValue(key)
}

func (s *SafeSkipList) Remove(key interface{}) {
s.mutex.Lock()
defer s.mutex.Unlock()
s.list.Remove(key)
}

func main() {
safeList := NewSafeSkipList(skiplist.Int)
safeList.Set(1, "один")
safeList.Set(2, "два")

value, ok := safeList.Get(1)
if ok {
fmt.Println("Ключ 1 имеет значение:", value)
}

safeList.Remove(1)
_, ok = safeList.Get(1)
if !ok {
fmt.Println("Ключ 1 успешно удален")
}
}
Создали обертку SafeSkipList, которая объединяет сам Skip List с мьютексом. Методы Set, Get и Remove теперь аккуратно обернуты блокировками мьютекса, чтобы никакие горутины не нарушили целостность списка.