有人可以解释一下为什么函数1比函数2慢很多吗？

Question

我有一个函数，它接受排序的值列表并计算每个输入值的唯一 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 毫秒。是什么导致了计算时间的显着差异？我在忽略什么？我本以为我的新方法会快得多，因为它只涉及一个循环，没有字典，也没有计数器变量。

我很欣赏你的想法！

Answer 1

在第一个函数中：您使用的是字典，字典中的查找和插入操作通常平均为 O(1)。因此，对于 n 个元素，该函数的总体时间复杂度将为 O(n)。

在第二个函数中：您使用的是列表，“不在”操作具有线性时间复杂度 O(n)，因此对于 n 个元素，总体时间复杂度将为 O(n^2)