Python，为什么 bisect.insort 比我的链表快很多

Question

所以我一直在努力保持列表的有序。因此，每当有新数据进来时，我都会将其插入 'sorted list'.

问题，为什么bisect.insort比我的链表实现快很多。我知道对分搜索需要 O(logn)，但由于插入到列表中，它确实需要 O(n)。其中链表实现也应该是 O(n)。在已排序的链表中插入新值也应该是 O(n)。但为什么时间比较慢得多？我的链表实现没有优化吗？

这是我的示例代码：

import timeit
import bisect
import random


# Testing parameters
NUM_ITERATION_TEST = 10
TOTAL_NUM_DATA = 10000
DATA = [random.randint(0, 1000) for x in range(TOTAL_NUM_DATA)]


class Node():
    def __init__(self, val):
        self.val = val
        self.next = None


class LinkedListIterator():
    def __init__(self, head):
        self.current = head

    def __iter__(self):
        return self

    def __next__(self):
        if not self.current:
            raise StopIteration
        else:
            val = self.current.val
            self.current = self.current.next
            return val


class LinkedList():
    def __init__(self):
        self.head = None

    def __iter__(self):
        return LinkedListIterator(self.head)

    def insert(self, val):
        new_node = Node(val)

        if self.head is None:
            self.head = new_node
            return

        curr = self.head
        if curr.val > val:
            new_node.next = curr
            self.head = new_node
            return

        while curr.next:
            if curr.next.val > val:
                break
            curr = curr.next

        new_node.next = curr.next
        curr.next = new_node


def method1(DATA):
    sorted_list = []
    for num in DATA:
        bisect.insort_right(sorted_list, num)


def method2(DATA):
    sorted_list = LinkedList()
    for num in DATA:
        sorted_list.insert(num)


if __name__ == "__main__":
    # METHOD 1
    print("Method 1 Execution Time:")
    print(timeit.timeit("test_timeit.method1(test_timeit.DATA)",
                        number=NUM_ITERATION_TEST,
                        setup="import test_timeit"))

    # METHOD 2
    print("Method 2 Execution Time:")
    print(timeit.timeit("test_timeit.method2(test_timeit.DATA)",
                        number=NUM_ITERATION_TEST,
                        setup="import test_timeit"))

执行时间为：

Method 1 Execution Time:
0.11593010000000001
Method 2 Execution Time:
33.0651346

我也尝试过使用其他实现，如排序的字典，但没有什么比对分实现更好的了。有没有更高效的实现方式？基本上想要一个始终排序的数据列表，我会不断地向列表 add/insert 新数据..

Answer 1

您自己的实现由 Python 解释器执行，创建和链接动态运行-time 对象，其中包含大量多余的有效性检查，一次创建或删除一个对象。内置函数在 C 中进行了优化，已编译。它可以在更大的块中分配内存，在单个 struct 映射中制造新对象，避免许多有效性检查，...

基于 C 语言的内置程序（几乎）总能击败您可以在 Python 中编写的任何程序。

Python，为什么 bisect.insort 比我的链表快很多

Python, why is bisect.insort much faster than my linkedlist

python

sorting

linked-list

bisect