0

所以我一直在努力保持一个列表的顺序。所以每当有新数据进来时，我都会把它插入到“排序列表”中。

问题，为什么 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

我还尝试使用其他实现，例如排序的字典，但没有什么比 bisect 实现更好的了。有没有更有效的实现方式？基本上想要一个始终排序的数据列表，我会不断向列表中添加/插入新数据..

4

1 回答 1

2

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

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

于 2020-07-27T16:45:35.647 回答