Python字典能否从中间开始迭代？O(1)复杂度定位可行吗？

问题说明 #

我们可以通过以下生成器表达式获取符合条件的字典值迭代器：

(value for value in dict if <condition>)

已知Python 3.6及以上版本的字典会保留插入顺序，现在需要查找字典中第一个True值，且已知该值位于字典中间位置，有两个疑问：

• 能否以**O(1)**时间复杂度定位到字典中间位置并从该处开始迭代查找第一个True值？
• 是否唯一的高效方案是始终追踪字典中的第一个True值？

解答 #

1. 无法实现O(1)定位中间位置并开始迭代
   Python的有序字典（3.6+）并没有提供直接访问中间位置元素的内置接口，也不支持从指定位置启动迭代器。字典的迭代器默认从头开始遍历，要定位到中间位置，必须先遍历前半部分元素，这一步的时间复杂度已经是O(n)，不存在O(1)的实现方式。

2. 始终追踪是最高效的方案
   如果需要频繁获取第一个True值，在字典的修改操作（添加、更新、删除键值对）中同步维护一个记录第一个True值的变量，是最优解。这样每次获取目标值时都能直接返回，时间复杂度为O(1)。

示例实现：

class TrackedDict(dict):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.first_true = self._find_first_true()
    
    def _find_first_true(self):
        for val in self.values():
            if val is True:
                return val
        return None
    
    def __setitem__(self, key, value):
        old_val = self.get(key)
        super().__setitem__(key, value)
        
        # 新设置的值是True且当前无记录，直接更新
        if value is True and self.first_true is None:
            self.first_true = value
        # 原来的第一个True被修改为非True，重新查找
        elif old_val is True and value is not True:
            self.first_true = self._find_first_true()
    
    def __delitem__(self, key):
        old_val = self.get(key)
        super().__delitem__(key)
        
        # 如果删除的是第一个True，重新查找
        if old_val is True and self.first_true == old_val:
            self.first_true = self._find_first_true()

如果只是偶尔需要查找一次，直接从头遍历到第一个True值的效率，和先定位中间位置再查找的效率并无差异（本质都是O(n)），甚至前者更简洁。

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