Skip List в Golang

Привет, Хабр! Сегодня я решил поделиться с вами одной из тех структур данных, которая, возможно, не так популярна, как хеш‑таблицы или деревья, но обладает своими уникальными фичами. Знакомьтесь — 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 теперь аккуратно обернуты блокировками мьютекса, чтобы никакие горутины не нарушили целостность списка.

Если у вас есть какие‑то интересные примеры применения Skip List, обязательно делитесь в комментариях. С наступающим Новым Годом!

Всех разработчиков на Go приглашаем на открытый урок 25 декабря: «Каналы Go: от устройства до практического применения». Мы подробно разберем устройство и механизмы работы каналов, рассмотрим возможные ситуации, а затем на примерах кода посмотрим, как использовать каналы в программах. Записывайтесь по ссылке.

Все остальные открытые уроки по разным ИТ-направлениям можно посмотреть в календаре мероприятий.