本文揭示了看似更简洁的单循环实现为何比双循环字典方案慢100倍：关键在于 if x not in list 的线性查找本质，导致算法从 O(n) 退化为 O(n²)。
本文揭示了看似更简洁的单循环实现为何比双循环字典方案慢100倍：关键在于 `if x not in list` 的线性查找本质，导致算法从 o(n) 退化为 o(n²)。
在将排序数组映射为连续唯一ID的场景中（如 [2,2,3,4,5,5,5,6] → [0,0,1,2,3,3,3,4]），直觉上“只遍历一次”的实现似乎更高效。但实际性能却天差地别——原版字典方案仅耗时 25.1ms，而新版列表方案高达 2.8s（相差约 110 倍）。根本原因在于数据结构选择引发的时间复杂度质变。
? 核心差异：哈希表 vs 线性搜索
旧函数（高效，O(n)）
使用 dict 存储已见元素及其分配ID：idMapping[element] = currentId。
字典的 in 查找、插入均为平均 O(1) ——底层基于哈希表，无需遍历。新函数（低效，O(n²)）
使用 list 记录已见元素：if element not in already_used_hashed_ids。
列表的 in 操作需逐个比较，最坏/平均时间复杂度均为 O(k)（k 为当前列表长度）。对 n 个元素，总操作数 ≈ 1 + 2 + 3 + … + n = n(n+1)/2 → O(n²)。
? 性能对比验证（小规模示例）
# 模拟新函数的内层开销（简化版）
def slow_lookup_demo(elements):
seen = []
for i, x in enumerate(elements):
# 每次执行 len(seen) 次比较！
if x not in seen: # ← 这里是性能黑洞
seen.append(x)
print(f"Step {i}: 'x not in seen' checks ~{len(seen)} times")
slow_lookup_demo([2,2,3,4,5])
# 输出：
# Step 0: 'x not in seen' checks ~0 times
# Step 1: 'x not in seen' checks ~1 times
# Step 2: 'x not in seen' checks ~2 times
# Step 3: 'x not in seen' checks ~3 times
# Step 4: 'x not in seen' checks ~4 times
# 总比较次数：0+1+2+3+4 = 10 → 当 n=10000 时，比较次数超 5000 万！
✅ 正确优化方向：保持 O(n)，拒绝 O(n²)
若坚持单循环，应用集合（set）替代列表来维护“已见元素”，兼顾去重与 O(1) 查找：
def map_to_unique_ids_optimized(hashed_ids):
seen = set() # O(1) 查找 & 插入
id_mapping = {} # O(1) 映射存储
result = []
next_id = 0
for x in hashed_ids:
if x not in seen:
seen.add(x)
id_mapping[x] = next_id
next_id += 1
result.append(id_mapping[x])
return result
? 关键提醒：即使输入已排序，也不能跳过哈希结构——排序仅影响输出顺序，不改变“判重”操作的本质成本。list 的 in 永远无法通过排序优化为亚线性。
? 总结
- ✅ 优先使用 dict 或 set 实现 O(1) 成员检查；
- ❌ 避免在循环中对 list 执行 x in list，尤其当列表动态增长时；
- ⚖️ “代码行数少” ≠ “执行效率高”，算法复杂度才是性能的决定性因素；
- ? 使用 %timeit 测试时，建议从小规模（如 range(100)）逐步扩大，观察增长趋势，快速定位 O(n²) 瓶颈。
选择合适的数据结构，不是语法细节，而是算法思维的基本功。
