python - Python sorted() 内置函数 vs. list insert() 方法的效率

Question

我不是新手，但我用 Python 的不多，我的知识面比较广，对这门语言的了解不是很深，也许这里有知识渊博的人可以回答我的问题。我发现自己处于需要将项目添加到列表并将其按添加的项目排序的情况。一种快速的方法是。

list.append(item)                  // O(1)
list.sort()                        // ??

我想如果这是将项目添加到列表中的唯一方式，我希望排序会相当有效，因为列表会在每次添加时进行排序。但是，还有一个可行的方法:

inserted = False
for i in range(len(list)):         // O(N)
    if (item < list[i]): 
        list.insert(i, item)       // ??
        inserted = True
        break
if not inserted: list.append(item)

谁能告诉我其中一个是否明显更有效率？我倾向于第二种说法，但我真的不知道。

Answer 1

您正在寻找的是 bisect 模块，最有可能是 insort_left

所以你的表达式可以等效地写成

来自

some_list.append(item)                  // O(1)
some_list.sort()                        // ??

到

bisect.insort_left(some_list, item)