Python 字典和集合

字典是由键 key 和值 value 配对组成的元素的集合;

相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。

而集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。

列表

用列表来存储数据结构，并进行查找。

def find_product_price(products, product_id):
    for id, price in products:
        if id == product_id:
            return price
    return None 
     
products = [
    (1, 100),
    (2, 30),
    (3, 150),
    (4, 30)
]

print('产品2的价格是 {}'.format(find_product_price(products, 2)))
# 输出 产品2的价格是 30

假设列表有 n 个元素，而查找的过程要遍历列表，那么时间复杂度就为 O(n)。 即使我们先对列表进行排序，然后使用二分查找，也会需要 O(logn) 的时间复杂度， 更何况，列表的排序还需要 O(nlogn) 的时间。

字典

用字典来存储这些数据，那么查找就会非常便捷高效，只需 O(1) 的时间复杂度就可以完成。 字典的内部组成是一张哈希表，你可以直接通过键的哈希值，找到其对应的值。

products = {
  1: 100,
  2: 30,
  3: 150,
  4: 30
}

print('产品2的价格是 {}'.format(products[2])) 
# 输出 产品2的价格是 30

字典和集合性能

当数据量较小时，时间复杂度的影响可能不明显；但随着数据规模增大（例如达到 100,000 条或更多），优化的效果会愈发显著。

import time
id = [x for x in range(0, 100000)]
price = [x for x in range(200000, 300000)]
products = list(zip(id, price))

# 计算使用列表版本的时间
start_using_list = time.perf_counter()
find_unique_price_using_list(products)
end_using_list = time.perf_counter()
print("使用列表耗时: {}".format(end_using_list - start_using_list))
## 输出 使用列表耗时: 57.26800930000036

# 计算使用集合版本的时间
start_using_set = time.perf_counter()
find_unique_price_using_set(products)
end_using_set = time.perf_counter()
print("使用集合耗时: {}".format(end_using_set - start_using_set))
# 输出 使用集合耗时: 0.015330400000038935


# 使用列表
def find_unique_price_using_list(products):
    unique_price_list = []
    for _, price in products:
        if price not in unique_price_list:
            unique_price_list.append(price)
    return len(unique_price_list)


# 使用集合
def find_unique_price_using_set(products):
    unique_price_set = set()
    for _, price in products:
        unique_price_set.add(price)
    return len(unique_price_set)

---

返回 后端开发文章