游戏开发笔记 - 链表优化（快慢指针）

2023-11-21

全文 ≈ 821字 | 预计阅读时长 3分钟

优化链表查询效率

前言

链表在操作的时候需要从头节点遍历到目标节点，如果数据量大比较耗时。当链表应用在 AOI 算法（十字链表，双有序链表）时这个效率问题更会凸显，最坏的情况是遍历 x*y*{v}个节点。

优化方案

常见的 2 种优化方式：

快慢针

创建 2 个指针同时指向头节点，快指针移动步长大、慢指针移动步长小，查询时通过快慢指针确定目标节点的范围。

跳表

链表每固定步长的节点为索引节点，这些索引节点再组成一个索引链表，查询时通过索引链表确定目标节点的范围。

原理类似 ClickHouse 的跳数索引，可以存在多个索引链表。

快慢针

假设一个从小到大的有序链表，检索流程

创建 2 个指针同时指向头节点
快指针移动一次
检查目标节点值是否小于快指针的节点值
- 小于，把慢指针的位置移动到快指针的位置，从步骤 2 继续执行。
- 大于，说明目标节点值在慢指针的节点位置和快指针的节点位置中间，从慢指针开始遍历。

快慢针实现简单，且不需要修改链表结构。但查询效率不够稳定，与链表数据大小、快慢针步长的设计有一定关系。

链表结构

type Aoi struct {
    nodes        map[uint32]*node
    xList        *list
    yList        *list
    visibleRange uint
    step         int
}

type list struct {
    head *node
    tail *node
    size int
}

type node struct {
    Id     uint32
    xPrev  *node
    xNext  *node
    yPrev  *node
    yNext  *node
    x, y   uint
    player *entity.Player
}

x 轴插入节点（y 轴逻辑一致）

func (r *Aoi) addX(targetNode *node) {
    // 直接插入尾部
    if r.xList.tail.x <= targetNode.x {
        r.xList.tail.xNext = targetNode
        targetNode.xPrev = r.xList.tail
        r.xList.tail = targetNode
        return
    }
    var (
        prev *node
        slow = r.xList.head
        skip = int(math.Ceil(float64(r.xList.size) / float64(r.step)))
    )
    for i := 0; i < r.step; i++ {
        // 移动快指针
        fast := r.xFastMove(slow, skip)
        // 快指针的坐标小于插入坐标，移动慢指针至快指针位置
        if fast.x < targetNode.x {
            slow = fast
            continue
        }
        for ; slow != nil; slow = slow.xNext {
            // 插入cur之前
            if slow.x >= targetNode.x {
                // 根节点
                if slow.xPrev == nil {
                    r.xList.head = targetNode
                } else {
                    targetNode.xPrev = slow.xPrev // 当前节点的前置节点作为新节点的前置节点
                    slow.xPrev.xNext = targetNode // 新节点成为当前节点的前置节点的后置节点
                }
                slow.xPrev = targetNode // 新节点作为当前节点的前置节点
                targetNode.xNext = slow // 当前节点作为新节点的后置节点
                break
            }
            prev = slow
        }
        // 插入尾部
        if prev != nil && slow == nil {
            prev.xNext = targetNode
            targetNode.xPrev = prev
        }
        break
    }
}

func (r *AoiMgr) removeX(delNode *aoiNode) {
    // 根节点
    if delNode.xPrev == nil {
        if delNode.xNext == nil {
            r.xList.head = nil
        } else {
            r.xList.head = delNode.xNext
            r.xList.head.xPrev = nil
        }
    } else if delNode.xNext == nil { // 尾节点
        delNode.xPrev.xNext = nil
        r.xList.tail = delNode.xPrev
    } else if delNode.xNext != nil {
        delNode.xPrev.xNext = delNode.xNext
        delNode.xNext.xPrev = delNode.xPrev
    } else {
        delNode.xPrev.xNext = nil
    }
    delNode.xPrev, delNode.xNext = nil, nil
}

func (r *Aoi) xFastMove(cur *node, skip int) *node {
    for i := 1; i <= skip; i++ {
        if cur.xNext == nil {
            break
        }
        cur = cur.xNext
    }
    return cur
}