第四节：数据结构选型：列表 vs 队列 vs 堆

做回测引擎，说白了就是在跟时间赛跑。你想想看，一次回测可能要处理几百万甚至上千万个事件，每个事件从产生到被消费，中间经过的数据结构如果选错了，性能差距能到几十倍。

我个人习惯，在开始写任何核心代码之前，先想清楚一件事：这个数据结构，到底要解决什么访问模式？是先进先出？还是按优先级调度？还是随机访问？想清楚这个，选型就成功了一半。

4.1 列表（List）—— 最熟悉，但最危险

Python 的 list 用起来确实顺手。我见过不少新手，上来就用 list 当队列使：

# 错误示范：用 list 模拟队列
events = []
events.append(event)  # 入队 O(1)
event = events.pop(0) # 出队 O(n) —— 灾难！

为什么会这样？因为 pop(0) 会让所有元素往前挪一位。你想想看，100 万个事件，每次出队都要移动 100 万个指针，这谁受得了？

那 list 是不是一无是处？也不是。如果你只需要随机访问（比如按索引取某个历史事件），list 的 O(1) 访问速度是无可替代的。

4.2 队列（Queue / deque）—— 事件驱动的基石

事件驱动架构里，最核心的就是事件队列。说白了，就是生产者往里面塞事件，消费者从里面取事件。这里有两个关键选择：

4.2.1 标准库 queue.Queue vs collections.deque

特性	queue.Queue	collections.deque
线程安全	✅ 内置锁	❌ 非线程安全
性能（单线程）	较慢（锁开销）	极快（C 语言实现）
适用场景	多线程生产者-消费者	单线程回测引擎

我个人建议：回测引擎用 deque，别犹豫。为什么？因为回测是单线程的，不需要线程安全。queue.Queue 每次操作都要加锁释放锁，这个开销在百万级事件下会被放大到不可接受。

from collections import deque

class EventEngine:
    def __init__(self):
        self.event_queue = deque()
    
    def push_event(self, event):
        self.event_queue.append(event)  # O(1)
    
    def pop_event(self):
        return self.event_queue.popleft() if self.event_queue else None  # O(1)

4.3 堆（Heap）—— 时间优先级的王者

回测引擎里有个经典问题：事件有优先级怎么办？比如，同一时刻的成交事件应该优先于报价事件被处理。这时候，普通队列就不够用了。

Python 的 heapq 模块实现了最小堆，非常适合做优先级队列：

import heapq

class PriorityEventQueue:
    def __init__(self):
        self._heap = []
        self._counter = 0  # 用于处理相同优先级时的 FIFO
    
    def push(self, event, priority):
        heapq.heappush(self._heap, (priority, self._counter, event))
        self._counter += 1
    
    def pop(self):
        if self._heap:
            _, _, event = heapq.heappop(self._heap)
            return event
        return None

这里有个细节：为什么加了个 counter？因为堆比较的是元组，如果两个事件优先级相同，堆会比较第二个元素。如果不加 counter，而事件对象本身不可比较，就会报错。嗯，这个坑我踩过。

4.4 PriorityQueue 的性能真相

Python 标准库的 queue.PriorityQueue 本质上就是 heapq + 线程安全锁。我做过一个对比测试：

操作	deque（普通队列）	heapq（优先级队列）	PriorityQueue
入队 100 万次	0.08 秒	0.35 秒	1.2 秒
出队 100 万次	0.07 秒	0.38 秒	1.3 秒
内存占用	低	中	高（锁对象）

4.5 实战中的选择策略

我一般这样设计回测引擎的事件系统：

1. 主事件队列：用 deque。因为大部分事件是按时间顺序到达的，不需要优先级。
2. 定时器队列：用 heapq。比如定时触发的止盈止损检查，需要按触发时间排序。
3. 撮合引擎内部：用 heapq。订单簿的买卖盘需要按价格优先级排序。

你看，同一个回测引擎里，不同场景用不同的数据结构。没有银弹，只有合适的选择。

4.6 本章知识体系

下面这张图，是我对事件驱动回测中数据结构选型的理解：

最后说一句：别迷信任何数据结构。我见过有人为了炫技，在不需要优先级的地方硬上堆，结果性能反而更差。选型之前，先问自己三个问题：

• 这个队列的访问模式是什么？（FIFO？优先级？随机？）
• 是单线程还是多线程？
• 数据量级有多大？（100 万和 1 亿，选型完全不同）

想清楚这些，你的数据结构选型就不会跑偏。

---