面试题：Python字典与集合用法的专家级问题

from collections import OrderedDict


class OrderedDictEnhanced:
    def __init__(self):
        self.data = OrderedDict()
        self.change_history = []

    def __setitem__(self, key, value):
        if key in self.data:
            old_value = self.data[key]
            self.data[key] = value
            self.change_history.append((key, old_value, value))
        else:
            self.data[key] = value

    def __getitem__(self, key):
        return self.data[key]

    def __delitem__(self, key):
        del self.data[key]

    def get_by_index(self, index):
        keys = list(self.data.keys())
        if 0 <= index < len(keys):
            key = keys[index]
            return key, self.data[key]
        else:
            raise IndexError("Index out of range")


# 对于大型集合成员检测优化
# 使用集合(set)来优化，原理是集合的成员检测操作平均时间复杂度为O(1)，而列表为O(n)
large_list = list(range(1000000))
large_set = set(large_list)


def check_member_in_list(target):
    return target in large_list


def check_member_in_set(target):
    return target in large_set

OrderedDictEnhanced 类的实现:
- 数据结构: 使用 collections.OrderedDict 来保持插入顺序。它是Python标准库中专门用于有序字典的类。
- __setitem__ 方法: 当设置键值对时，如果键已存在，记录值的变化到 change_history 列表中，该列表用于记录值变化的历史。如果键不存在，直接添加键值对。
- __getitem__ 方法: 实现根据键获取值的操作，直接从 self.data 中获取。
- __delitem__ 方法: 实现删除键值对的操作，从 self.data 中删除指定键的键值对。
- get_by_index 方法: 先获取所有的键，然后根据索引获取对应的键值对，如果索引越界则抛出 IndexError 异常。
大型集合成员检测优化:
- 原理: 列表的成员检测操作平均时间复杂度为 $O(n)$，因为需要遍历列表中的每个元素来查找目标元素。而集合的成员检测操作平均时间复杂度为 $O(1)$，这是因为集合使用哈希表实现，通过计算元素的哈希值可以快速定位元素是否存在。
- 代码示例: 分别创建了包含一百万个元素的列表 large_list 和集合 large_set，并定义了 check_member_in_list 和 check_member_in_set 两个函数来演示在列表和集合中进行成员检测的操作。在实际应用中，对于大型集合，应优先使用集合来进行成员检测操作以提高效率。

星途面试题库

面试题：Python字典与集合用法的专家级问题

知识考点

面试题答案