Python中如何高效删除字典内元组列表中指定首元素的元组？

问题背景 #

给定如下嵌套字典结构，每个键对应一个元组列表，元组包含坐标名称和距离：

data = {
    '0_0': [('0_0', 0), ('0_1', 1), ('0_2', 2)],
    '0_1': [('0_0', 1), ('0_1', 0), ('0_2', 1)],
    '0_2': [('0_0', 2), ('0_1', 1), ('0_2', 0)],
}

需要根据指定的坐标名称，删除所有子列表中对应的元组。原实现函数虽能得到预期结果，但处理大型数据集时效率偏低：

def remove_all_acs(
    dictionary,
    delete_ac
):
    for key in dictionary:
        acs = dictionary[key]
        for ac in acs:
            if ac[0] == delete_ac:
                acs.remove(ac)
                break

    return dictionary

原函数的效率瓶颈 #

原函数的核心问题在于：

1. 遍历子列表查找目标元组后调用list.remove()——该操作时间复杂度为O(n)（n为子列表长度），因为remove需要移动被删除元素后的所有列表元素。
2. Python层面的循环遍历开销较高，处理包含大量元素的数据集时，累积耗时会非常明显。

优化实现方案 #

方案1：列表推导式（单次删除首选） #

利用Python内置列表推导式过滤元素，底层由C实现，比手动循环+remove高效得多。时间复杂度仍为O(m*n)（m为字典键数，n为子列表长度），但常数项大幅降低：

def remove_all_acs(dictionary, delete_ac):
    for key in dictionary:
        dictionary[key] = [ac for ac in dictionary[key] if ac[0] != delete_ac]
    return dictionary

该方案会删除所有符合条件的元组（若子列表存在多个相同坐标名称的元组），而原函数仅删除第一个后就break——如果你的场景中每个子列表的坐标名称唯一，两种结果一致。

方案2：预处理为嵌套字典（多次删除首选） #

若需多次执行删除操作，建议先将数据集转换为字典嵌套字典的结构，这样每次删除操作的时间复杂度为O(1)：

# 预处理：将原列表结构转为字典，键为坐标名称，值为距离
def preprocess_dataset(dataset):
    return {key: {ac[0]: ac[1] for ac in value} for key, value in dataset.items()}

# 删除指定坐标的函数
def remove_all_acs_preprocessed(dictionary, delete_ac):
    for key in dictionary:
        # pop方法删除指定键，第二个参数None表示键不存在时不报错
        dictionary[key].pop(delete_ac, None)
    # 如需转回原列表格式，执行以下代码
    # return {key: list(items.items()) for key, items in dictionary.items()}
    return dictionary

预处理仅需执行一次，后续每次删除操作都能快速完成，适合频繁进行删除操作的场景。

大型数据集测试 #

可用以下代码生成大型测试数据集：

import math

def generate(width, height):
    coordinates = [(x, y) for x in range(width) for y in range(height)]
    dataset = {}
    
    for x1, y1 in coordinates:
        key = f"{x1}_{y1}"
        distances = []
        for x2, y2 in coordinates:
            if (x1, y1) != (x2, y2):
                distance = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
                distances.append((f"{x2}_{y2}", distance))
        dataset[key] = distances
    
    return dataset

例如生成100x100的数据集：large_data = generate(100,100)，对比原函数和优化后的函数运行时间，能明显看到性能差距。

内容的提问来源于stack exchange，提问作者E. Zeytinci