Golang은 스킵 테이블을 구현합니다.

스킵 리스트(Skip list)는 연결 리스트(linked list)를 기반으로 한 데이터 구조로, 연결 리스트에 포인터를 추가함으로써 일반 연결 리스트에 비해 데이터 검색 및 연산의 효율성이 크게 향상됩니다. 점프 테이블은 원래 1990년 William Pugh가 제안했으며 데이터베이스, 검색 엔진 및 기타 분야에서 널리 사용됩니다. 이 기사에서는 Go 언어를 사용하여 스킵 테이블 데이터 구조를 구현하는 방법을 소개합니다.

1. 점프 목록 개요

스킵 목록은 연결 목록의 각 수준에 있는 데이터 노드가 다음 수준의 연결 목록에 있는 여러 노드에 분산되는 구조입니다. 점프 목록의 각 노드에는 루트 노드와 다음 수준 연결 목록의 동일한 위치에 있는 노드를 가리키는 여러 포인터가 포함된 배열이 있습니다. 이러한 포인터는 무작위로 또는 특정 규칙에 따라 설정됩니다. 부적절한 설정으로 인해 점프 목록이 단일 연결 목록으로 변질되므로 포인터 분포를 적절하게 설정해야 합니다.

스킵 테이블은 추가, 삭제, 검색과 같은 기본 작업을 지원하며, 시간 복잡도는 이진 트리의 시간 복잡도와 동일합니다. 스킵 리스트 구조는 연결 리스트(Linked List)를 기반으로 하기 때문에 포인터 정보를 저장하기 위해서는 일정량의 추가 저장 공간이 필요하다.

2. 점프 테이블 구현

먼저 점프 테이블의 노드 구조를 정의해야 합니다.

type skipListNode struct {
    Val       int                            // 节点值
    next      []*skipListNode               // 指向下一层节点的指针数组
}

노드 구조는 노드의 값과 다음 노드를 가리키는 포인터 배열을 정의합니다. 다음 레이어의 노드 수는 rand.Intn() 함수를 통해 무작위로 설정되고 생성됩니다.

func newNode(val int, level int) *skipListNode {
    node := &skipListNode{Val: val, next: make([]*skipListNode, level+1)}
    return node
}

func randLevel() int {
    level := 1
    for rand.Float32() < 0.5 {
        level++
    }
    return level
}

노드 구조와 난수 레이어를 생성하는 함수를 정의한 후 점프 목록의 구조를 정의할 수 있습니다.

type skipList struct {
    head   []*skipListNode              // 指向跳表头节点的指针数组
    level  int                           // 当前跳表深度
    length int                          // 跳表节点数量
}

점프 목록 구조에는 점프 목록의 헤드 노드를 가리키는 포인터 배열 헤드가 포함되어 있습니다. 현재 점프 목록 깊이 수준 및 점프 테이블 노드 수 길이. 점프 테이블의 초기 깊이는 1이며, 노드 추가 시 난수에 의해 생성된 레벨 수에 따라 깊이가 변경됩니다.

점프 목록 구조를 정의한 후 점프 목록의 기본 작업 구현을 시작할 수 있습니다. 첫 번째는 삽입 작업입니다.

func (sl *skipList) insert(val int) {
    level := randLevel()                   // 生成随机层数
    node := newNode(val, level)            // 创建新节点
    update := make([]*skipListNode, level+1) // 用于更新每层跳表的节点指针
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {       // 从最高层开始向下查找
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找插入位置
            cur = cur.next[i]
        }
        update[i] = cur                      // 更新每层跳表要插入的位置
    }
    for i := 0; i <= level; i++ {            // 更新每层跳表插入节点
        node.next[i] = update[i].next[i]
        update[i].next[i] = node
    }
    // 更新跳表深度和节点数
    if level > sl.level {
        sl.level = level
    }
    sl.length++
}

삽입 작업은 먼저 임의의 수의 레이어를 생성하고 새 노드를 생성한 다음 업데이트 배열을 사용하여 각 레이어를 점프 테이블에 삽입할 때 위치를 기록합니다. 그런 다음 최상위 레벨부터 시작하여 아래쪽으로 삽입할 위치를 검색하고 삽입할 위치의 이전 노드를 기록한 다음 삽입된 노드와 이전 노드의 방향을 각 레이어의 점프 테이블에 업데이트합니다. 마지막으로 점프 테이블의 깊이와 노드 수가 업데이트됩니다.

다음 단계는 삭제 작업입니다.

func (sl *skipList) delete(val int) {
    update := make([]*skipListNode, sl.level+1) // 用于更新每层跳表的节点指针
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找要删除的节点位置
            cur = cur.next[i]
        }
        if cur.next[i] != nil && cur.next[i].Val == val { // 找到要删除的节点
            update[i] = cur
        } else {
            update[i] = nil
        }
    }
    if update[0] != nil && update[0].next[0].Val == val { // 更新节点指针
        node := update[0].next[0]
        for i := 0; i <= sl.level && update[i].next[i] == node; i++ {
            update[i].next[i] = node.next[i]
        }
        // 更新跳表深度和节点数
        for sl.level > 0 && len(sl.head[sl.level].next) == 0 {
            sl.level--
        }
        sl.length--
    }
}

삭제 작업은 먼저 삭제할 노드를 찾아 그 위치와 이전 노드의 위치를 ​​기록합니다. 삭제할 노드가 발견되면 노드 포인터가 업데이트되고 점프 테이블의 깊이와 노드 수가 업데이트됩니다.

마지막은 검색 작업입니다.

func (sl *skipList) search(val int) *skipListNode {
    cur := sl.head[sl.level]
    for i := sl.level; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].Val < val { // 查找要查找的节点位置
            cur = cur.next[i]
        }
    }
    if cur.next[0] != nil && cur.next[0].Val == val { // 找到要查找的节点
        return cur.next[0]
    }
    return nil // 没有找到节点，返回nil
}

검색 작업은 기본적으로 삽입 및 삭제 작업과 유사합니다. 최상위 수준에서 시작하여 찾을 노드를 아래쪽으로 검색하고 해당 위치를 기록한 후 노드를 반환합니다. 설립하다.

3. 스킵 리스트 분석

스킵 리스트는 연결 리스트 기반의 효율적인 데이터 구조로, 균형 이진 트리와 비교할 때 삽입 및 삭제 작업의 시간 복잡도는 동일하지만(O(log n)) 검색 연산의 시간 복잡도는 O(log n)이며, 이는 이진 트리의 검색 시간 복잡도 O(h)(여기서 h는 트리의 높이)보다 더 효율적입니다. 랜덤 레이어 설정으로 인해 점프 테이블의 높이도 랜덤하게 되어 삽입, 삭제, 검색이 더 효율적입니다.

스킵 리스트는 노드와 포인터 수를 합리적으로 설정하여 공간 복잡도를 제어할 수도 있습니다. 점프 목록에 여러 포인터를 설정하고 더 많은 저장 공간을 소비하는 것은 더 나은 성능을 얻기 위해 일부 특정 시나리오에서 이러한 추가 공간 오버헤드가 더 합리적입니다.

4. 요약

스킵 리스트는 대규모 캐시 데이터 저장 및 검색 문제를 처리하기 위해 균형 트리를 대체하는 데 사용할 수 있는 효율적인 연결 리스트 데이터 구조입니다. Go 언어의 동시성 기능과 플랫 패키지 구조는 Go 애플리케이션에서 건너뛰기 목록을 매우 실용적으로 만듭니다. 스킵 테이블 구현의 핵심은 노드 레벨을 무작위로 생성하고, 삽입 및 삭제할 위치를 찾고, 노드 포인터를 업데이트하는 데 있습니다. 이러한 기본 작업을 통해 스킵 리스트는 일반 연결 리스트보다 효율성이 높고 특정 애플리케이션 시나리오에 따라 노드 및 포인터 수를 합리적으로 설정할 수 있습니다.

위 내용은 Golang은 스킵 테이블을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!