本文深入解析两种 ID 映射实现的性能差异，揭示列表 in 操作的隐式线性扫描如何将算法复杂度从 O(n) 恶化为 O(n²)，并通过实测数据与优化方案说明高效映射的关键原则。

本文深入解析两种 id 映射实现的性能差异，揭示列表 `in` 检查的隐式线性扫描如何将算法复杂度从 o(n) 恶化为 o(n²)，并通过实测数据与优化方案说明高效映射的关键原则。

在处理有序序列的唯一 ID 映射任务时（例如将 [2,2,3,4,5,5,5,6] 转换为 [0,0,1,2,3,3,3,4]），看似更“简洁”的单循环实现反而比双循环版本慢 100 倍以上（2.8 秒 vs 25.1 毫秒）。根本原因不在于循环次数，而在于底层数据结构的时间复杂度特性。

? 关键差异：dict vs list 的成员检查开销

• 原函数（快） 使用 dict 存储已见元素：
  if element not in idMapping 是平均 O(1) 的哈希查找；
  后续 idMapping[element] 同样为 O(1)；
  整体时间复杂度为 O(n)，两次遍历仍保持线性增长。

• 新函数（慢） 使用 list 存储已见元素：
  if element not in already_used_hashed_ids 需要逐个比对——即 O(k)（k 为当前列表长度）；
  在最坏情况下（全部不重复），总操作数 ≈ 1 + 2 + 3 + … + n = n(n+1)/2 → O(n²)；
  即使输入含大量重复（如示例），随着 already_used_hashed_ids 增长，每次 in 检查仍需扫描越来越长的列表。

? 简单验证：用小数据看本质

# 模拟新函数中关键操作的耗时增长
test_list = list(range(1000))
%timeit 999 in test_list   # ~15 µs（扫描千项）
%timeit 9999 in test_list * 10  # 若扩展到万项，耗时≈150 µs，呈线性上升

当输入规模达数万时，O(n²) 算法的实际耗时会呈平方级飙升——这正是 %timeit 测出 2.8 秒的根本原因。

✅ 推荐写法：兼顾清晰性与性能

无需牺牲可读性，只需回归哈希表本质，并利用 Python 内置工具进一步精简：

def map_to_consecutive_ids(hashed_ids):
    """将输入序列映射为从0开始的连续整数ID（保持首次出现顺序）"""
    seen = {}
    counter = 0
    result = []
    for x in hashed_ids:
        if x not in seen:
            seen[x] = counter
            counter += 1
        result.append(seen[x])
    return result

# 更 Pythonic 的写法（等效，但更紧凑）
def map_to_consecutive_ids_v2(hashed_ids):
    mapping = {}
    next_id = 0
    return [mapping.setdefault(x, next_id := next_id + 1) - 1 for x in hashed_ids]

? 提示：dict.setdefault(key, default) 在键不存在时插入并返回 default，存在时直接返回值——天然适配此场景，且原子性强、线程安全（单线程下无额外收益，但语义更精准）。

⚠️ 注意事项与延伸建议

• 永远避免在循环内对大列表做 x in list 检查：这是 Python 新手最常见的性能陷阱之一；
• 若输入严格有序且仅相邻重复（如题干所示），可进一步优化为单次遍历 + 比较前一项，时间/空间均为 O(n)：

  def map_sorted_unique_ids(hashed_ids):
      if not hashed_ids: return []
      result = [0]
      last_val, curr_id = hashed_ids[0], 0
      for x in hashed_ids[1:]:
          if x != last_val:
              curr_id += 1
              last_val = x
          result.append(curr_id)
      return result

• 对超大规模数据（百万级以上），考虑使用 numpy.unique(..., return_inverse=True) 获取逆映射索引，性能远超纯 Python 实现。

总之，算法效率不取决于“看起来有几层循环”，而取决于每步操作的渐进时间复杂度。善用哈希结构（dict/set）替代线性容器（list）进行存在性判断，是写出高性能 Python 代码的基石之一。