Python deque与C++ list随机位置增删性能对比及C++优化咨询

需求背景 #

需要实现一个队列，支持按指定位置插入对象、删除队列头部或中间对象；每次增删操作后需更新后续对象的位置，采用队列索引跟踪位置。这类场景需要频繁在数据结构的第n个元素位置执行增删操作，双链表的增删操作本身是O(1)复杂度，但定位到目标位置的效率是关键。

测试代码 #

Python实现（script.py） #

from collections import deque
import random

class Event():
    def __init__(self):
        self.a = random.randint(0, 9)
        self.b = random.randint(0, 9)

structure = deque()

for i in range(0, 5000000, 1):
    event = Event()
    structure.insert(random.randint(0, 1000), event)

for i in range(0, 1000000, 1):
    del structure[random.randint(0, 1000)]

C++实现（script.cpp） #

#include <iostream>
#include <list>
#include <random>

class Event {
        public:
                Event() {
                        std::random_device rd;
                        std::mt19937 gen(rd());
                        std::uniform_int_distribution<> dis(0, 9);
                        a = dis(gen);
                        b = dis(gen);
                }
                int a;
                int b;
};

int main() {
        std::list<Event> structure;

        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, 1000);

        for (int i = 0; i < 5000000; ++i) {
                Event event;

                auto it = structure.begin();
                std::advance(it, dis(gen));
                structure.insert(it, event);
        }

        for (int i = 0; i < 1000000; ++i) {
                auto it = structure.begin();
                std::advance(it, dis(gen));

                structure.erase(it);
        }
        return 0;
}

测试结果 #

• g++ -O3编译C++代码后运行耗时：28.28秒
• Python 3.11版本运行耗时：9.43秒

C++版本性能不如预期，经微基准测试，主要开销来自std::advance方法。

当前C++实现的不足 #

• 数据结构选择不当：std::list是双向链表，std::advance需要从begin()开始逐个移动迭代器到目标索引，时间复杂度为O(k)（k为目标索引值）。而Python的deque底层是分段连续存储结构，支持O(min(k, n-k))的索引访问，在本次测试的0-1000索引范围内几乎是O(1)级别的效率，这是核心性能差距。
• 随机数生成冗余：Event构造函数中每次都重新初始化std::random_device和std::mt19937，带来不必要的初始化开销。
• 缺乏边界检查：当生成的随机索引超过当前std::list的元素数量时，std::advance会将迭代器移动到end()，此时执行erase(end())属于未定义行为，存在崩溃风险。

优化方案 #

1. 替换为std::deque数据结构 #

C++的std::deque与Python的deque底层实现逻辑类似，采用分段连续存储，索引访问效率远高于std::list。对于本次测试中0-1000的随机索引，std::deque可以直接通过begin() + idx定位到目标位置，时间复杂度接近O(1)。

修改后的核心代码示例：

#include <iostream>
#include <deque>
#include <random>

class Event {
public:
    static std::mt19937 gen;
    static std::uniform_int_distribution<> dis;
    
    Event() {
        a = dis(gen);
        b = dis(gen);
    }
    int a;
    int b;
};

// 初始化静态随机数生成器
std::mt19937 Event::gen(std::random_device{}());
std::uniform_int_distribution<> Event::dis(0, 9);

int main() {
    std::deque<Event> structure;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> idx_dis(0, 1000);

    const int insert_count = 5000000;
    for (int i = 0; i < insert_count; ++i) {
        size_t idx = idx_dis(gen);
        // 确保索引不超过当前容器大小，超出则插入到末尾
        if (idx > structure.size()) {
            idx = structure.size();
        }
        structure.insert(structure.begin() + idx, Event());
    }

    const int erase_count = 1000000;
    for (int i = 0; i < erase_count; ++i) {
        if (structure.empty()) break;
        size_t idx = idx_dis(gen);
        // 确保索引合法，超出则取最后一个元素
        if (idx >= structure.size()) {
            idx = structure.size() - 1;
        }
        structure.erase(structure.begin() + idx);
    }
    return 0;
}

2. 复用随机数生成器 #

将Event类中的随机数生成器改为静态成员，避免每次构造对象时重复初始化，减少额外开销。

3. 增加边界合法性检查 #

在插入和删除操作前，校验随机索引是否在当前容器的有效范围内，避免未定义行为。

4. 可选：自定义带索引优化的双链表（极致场景） #

如果业务场景必须使用双链表，可以实现带跳表（Skip List）或节点大小统计的自定义结构，将索引定位的时间复杂度降低到O(log n)，但实现复杂度较高，仅适合对性能有极致要求的场景。

优化效果预期 #

改用std::deque后，索引定位的开销会大幅降低，结合C++本身的底层执行效率，性能会超过Python版本，填补之前的性能差距。

内容的提问来源于stack exchange，提问作者sandstorm111