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

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