为何新实现的Generate_unique_sectionid函数远慢于旧函数？

问题背景 #

需要实现一个接收有序值列表、为每个输入值计算唯一ID的函数，示例如下：

input : [2,2,3,4,5,5,5,6]
output: [0,0,1,2,3,3,3,4]

旧函数实现 #

def mapHashedIdsToIds(hashed_ids):
    unique_section_ids = []
    uniqueHashedIds = []
    idMapping = {}
    currentId = 0

    for element in hashed_ids:
        if element not in idMapping:
            idMapping[element] = currentId
            currentId += 1
            uniqueHashedIds.append(element)

    for element in hashed_ids:
        unique_section_id = idMapping[element]
        unique_section_ids.append(unique_section_id)

    return(unique_section_ids)

unique_ids = mapHashedIdsToIds(uniqueAbschnittsId)

新函数实现 #

def Generate_unique_sectionid(hashed_ids):
    already_used_hashed_ids = []
    unique_section_ids = []
    for element in hashed_ids:
        if element not in already_used_hashed_ids:
            already_used_hashed_ids.append(element)
            unique_section_ids.append(len(already_used_hashed_ids)-1)
        else:
            unique_section_ids.append(len(already_used_hashed_ids)-1)
    return unique_section_ids

unique_ids = Generate_unique_sectionid(uniqueAbschnittsId)

性能测试结果 #

在Jupyter Notebook中用%timeit测试发现：

• 新函数耗时2.8秒
• 旧函数仅耗时25.1毫秒

原以为新函数单循环、无字典和计数器会更快，想明确性能差异的核心原因。

核心原因：查找操作的时间复杂度差异 #

• 旧函数的字典查找：Python字典（dict）基于哈希表实现，判断element not in idMapping的时间复杂度为O(1)（平均情况）——无论字典内元素数量多少，单次查找耗时基本恒定。即便执行两次循环，总时间复杂度仍为O(n)（n为输入列表长度）。
• 新函数的列表查找：列表的element not in already_used_hashed_ids是顺序遍历查找，时间复杂度为O(k)（k为当前列表已存元素数量）。随着输入列表增长，每次查找的遍历长度越来越长，总时间复杂度会升级为O(n²)——当n较大时，耗时会呈指数级上升，这就是新函数慢几十倍的根本原因。

举个直观例子：若输入列表有10000个元素，旧函数两次循环仅做20000次O(1)操作；而新函数每轮循环可能需要遍历几百甚至上千个元素，总操作量会达到几十万次，耗时自然剧增。

额外补充：旧函数中的uniqueHashedIds列表属于冗余代码，删除后不影响功能，还能节省少量内存。

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