Python，为什么是平分的.排序比我的链表快得多

Question

所以我一直在努力保持列表的有序。因此，每当有新数据出现时，我都会将其插入到"排序列表"中。

问题，为什么是平分。排序比我的链表实现快得多。我知道平分搜索需要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

我也尝试过使用其他实现，比如排序dicts，但没有什么能比得上平分实现。是否有更有效的实施？基本上想要一个始终排序的数据列表，我会不断地向列表中添加/插入新数据。。

Answer 1

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

基于C的内置程序(几乎(总是胜过任何可以用Python编程的程序。