二分模块的相关性

在寻找保持列表排序而不考虑插入和删除的方法时，我遇到了 bisect 和 sortedcontainers 模块。

bisect 的 insort 功能是 O(n) 因为它结合了 bisect_left O(log n) 和 || |然而，一个等效的操作 insert O(n)

def insort_left(a, x, lo=0, hi=None, *, key=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.

    A custom key function can be supplied to customize the sort order.
    """

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

for add from SortedList 模块是 sortedcontainers 由于 O(log n) 这个 原因。 现在据我了解，不包括排序是一个设计决定Python 标准库中的容器 -

来源 . 因此，在这个旨在简化性的设计决策和

旨在提高性能的设计决策之间， SortedList 有何相关性？是否存在 bisect 可能是首选的用例？ bisect could be preferred?

你对于 bisect 和 sortedcontainers 的性能分析是正确的。 bisect.insort 的时间复杂度为 O(n)，因为它在内部使用 list.insert ，该操作需要 O(n) 的时间来移动元素以维持顺序。另一方面， sortedcontainers.SortedList 使用像 B 树这样的数据结构来实现 O(log n) 的插入时间复杂度。

关于 bisect 和 sortedcontainers 的相关性，这取决于你的具体使用场景：

什么时候应该使用 bisect ？

1. 你只需要维护一个已排序的列表，并且插入/删除操作不频繁。 在这种情况下， bisect.insort 的 O(n) 复杂度不会成为性能瓶颈。
2. 你正在处理相对较小的列表。 对于小列表， bisect 的开销较低，并且可能比 sortedcontainers 更快。
3. 你想要一个更轻量级的解决方案。 bisect 模块是 Python 标准库的一部分，因此你不需要安装任何额外的依赖项。

什么时候应该使用 sortedcontainers ？

1. 你需要对大型列表执行频繁的插入/删除操作。 在这种情况下， sortedcontainers.SortedList 的 O(log n) 复杂度将提供显着的性能优势。
2. 你需要其他排序容器，例如 SortedDict 或 SortedSet 。 sortedcontainers 模块提供了一系列排序容器，而 bisect 只关注列表。

总结:

bisect 是一个简单、轻量级的解决方案，适用于维护小型排序列表或插入/删除操作不频繁的情况。如果你需要对大型列表执行频繁的插入/删除操作或需要其他排序容器，则 sortedcontainers 是更好的选择。

总的来说， bisect 强调简单性和标准库的包含性，而 sortedcontainers 则优先考虑性能和功能的丰富性。选择哪一个取决于你的特定需求和优先级。