如何在Python中使用分块数组优化大批量数据随机插入？-Python教程-PHP中文网

直接用 list.append() 不会变慢，变慢的是 list.insert()；因动态数组需搬移元素，最坏 O(n²)；deque 不支持 O(1) 随机插入；分块列表（ChunkedList）可实现 O(√n) 插入。

如何在python中使用分块数组优化大批量数据随机插入？

为什么直接用 list.append() 处理大批量随机插入会变慢？

因为 list 在 Python 中底层是动态数组，每次在中间或开头插入（比如用 list.insert(i, x)）都会触发后续所有元素的内存搬移。插入位置越靠前，搬移量越大；插入 10 万次，最坏情况总搬移量可达 O(n²)，实测可能卡住几秒甚至更久。

这不是“写法问题”，而是数据结构限制——list 为索引访问优化，不是为高频中间插入设计的。

用 deque 替代 list 做随机位置插入靠谱吗？

不靠谱。deque 虽然在两端插入/删除是 O(1)，但它**不支持 O(1) 的随机位置插入**。调用 deque.insert(i, x) 仍需遍历到第 i 个节点，内部是双向链表，索引访问是 O(n)，插入仍是 O(n)。实测 5 万次中间插入比 list 还慢。

真正能缓解的方案是「分块」：把大数组拆成固定大小的子块（如每块 1000 个元素），用列表存块，块内用 list，块间用 list 管理。插入时只影响一个块 + 块列表，避免全局搬移。

关键点：

块大小建议设为 sqrt(N)（N 是总预估元素数），平衡查找与插入开销；实测 500–2000 之间较稳
插入位置 pos 需先算出落在第几个块、块内偏移：block_idx = pos // block_size，inner_idx = pos % block_size
若块内插入导致超长（如 > 1.5×block_size），可分裂该块；若连续多块过短，可合并 —— 但初期可先忽略合并逻辑

如何实现一个支持 O(√n) 插入的分块列表？

不需要第三方库，手写一个轻量 ChunkedList 类即可。核心是维护 self.blocks: List[List] 和 self.block_size: int：

testing-python

使用pytest编写和评估有效的Python测试。适用于编写测试、审查测试代码、调试测试失败或提高测试覆盖率。

下载

class ChunkedList:
    def __init__(self, block_size=1000):
        self.block_size = block_size
        self.blocks = []
<pre class="brush:php;toolbar:false;">def insert(self, pos, value):
    if pos  len(self):
        raise IndexError("index out of range")

    block_idx = pos // self.block_size
    inner_idx = pos % self.block_size

    # 确保有足够块
    while len(self.blocks)  self.block_size * 2:
        mid = len(target_block) // 2
        new_block = target_block[mid:]
        target_block[:] = target_block[:mid]
        self.blocks.insert(block_idx + 1, new_block)

def __len__(self):
    return sum(len(b) for b in self.blocks)

def __getitem__(self, idx):
    if idx <p></p>

注意：__getitem__ 和 insert 都依赖块索引计算，不能直接用 self.blocks[idx] —— 因为块数 ≠ 总长度 / 块大小（末块通常不满）。