Bisect/Insort 的列表和双端队列的时间复杂度是否不同？
Do time complexities differ between list and deque for Bisect/Insort?
据我所知，Python中的list是用数组实现的，而deque是用双链表实现的。在任何一种情况下，对某个值的二进制搜索都需要 O(logn) 时间，但是如果我们插入到那个位置，数组需要 O(n) 而双链表需要 O(1)。
那么，我们是否可以使用bisect、insort和deque的组合来实现时间复杂度与Java中的TreeMap相当的所有动态集合操作呢？
更新：我在这个 Leetcode 问题中测试了它：https://leetcode.com/problems/time-based-key-value-store/submissions/
完全出乎我的意料，当我从list切换到deque时，速度慢了很多。
关于你的标题问题：是的，他们有。
关于你假设的排序集实现问题：不，你不能。
一，你对deque的执行有误；它不是一个普通的 "item per node" 链表，它是每个节点的 块 项目（CPython 参考解释器上有 64 个项目，尽管这是一个实现细节）。除了头部和尾部块之外，内部块永远不会留空，因此在 deque 中间插入并不是特别便宜，它仍然需要移动一堆东西。它不像 O(n) 像 mid-list 插入，因为它利用旋转的一些效率来旋转，附加到一侧或另一侧，然后旋转回来，但它与插入相去甚远链表中的已知点，剩余 O(n)（尽管有很大的常数除数，因为洗牌整个块比移动每个单独的项目更便宜）。
二，deque 中的每个查找都是 O(n)，而不是 list 中的 O(1)；如前所述，它有一个 64 的常数除数，它在 deque 两端附近下降到 O(1)，但它通常仍然是 O(n)，对于大 [=10] =]秒。 bisect 搜索是 O(log n) ，假设索引序列是 O(1)；对于 deque，它们会是 O(n log n)，因为它们会执行 log n O(n) 索引操作。这与您的测试结果相符； bisect+deque 明显更差。
Java的TreeMap无论如何都不是按照二分查找和链表实现的；链表对此没有好处，因为最终一个完整的二分查找必须来回遍历足够多以完成 O(n) 总工作量，即使它只需要与 O(log n) 个元素进行比较。树图需要某种树结构，你不能用链表和好的算法来伪造它。
Built-in 备选方案包括：
insort of a normal list: 总体来说当然是O(n)，但是昂贵的部分（找到插入的地方）是O(log n)，而且它只是"make room" 步 O(n)，真的 便宜 O(n)（基本上是 memcpy）。对于真正巨大的 lists 是不可接受的，但你会惊讶地发现在开销明显相对于 Python 的缓慢之前你需要多大的 list。- 延迟缓冲排序：如果查找不频繁，但插入很常见，则将排序推迟到需要时，以尽量减少排序操作的次数；只需将新元素附加到末尾而不进行排序并设置 "needs sorting" 标志，并在设置标志后在查找之前重新
sort 。当输入已经大部分排序时，TimSort 算法 非常 很好（比没有优化的通用排序更接近 O(n) 部分排序通常可以做到），所以它可能没事。
- 如果您在任何给定时间只需要最小的元素，
heapq 模块可以使用真正的 O(log n) 插入和删除来做到这一点，并使用 O(1) 获得最小值（它是始终索引 0).
- 使用
sqlite3 数据库（可能通过 shelve），适当索引； sqlite3 索引默认使用 B-tree，这意味着使用索引键排序的查询会按 "for free". 的排序顺序返回结果
否则，您将必须安装一个 third-party 模块，它提供一个正确排序的 set 类型。
据我所知，Python中的list是用数组实现的，而deque是用双链表实现的。在任何一种情况下，对某个值的二进制搜索都需要 O(logn) 时间，但是如果我们插入到那个位置，数组需要 O(n) 而双链表需要 O(1)。
那么，我们是否可以使用bisect、insort和deque的组合来实现时间复杂度与Java中的TreeMap相当的所有动态集合操作呢？
更新：我在这个 Leetcode 问题中测试了它：https://leetcode.com/problems/time-based-key-value-store/submissions/
完全出乎我的意料，当我从list切换到deque时，速度慢了很多。
关于你的标题问题：是的，他们有。
关于你假设的排序集实现问题：不，你不能。
一，你对deque的执行有误；它不是一个普通的 "item per node" 链表，它是每个节点的 块 项目（CPython 参考解释器上有 64 个项目，尽管这是一个实现细节）。除了头部和尾部块之外，内部块永远不会留空，因此在 deque 中间插入并不是特别便宜，它仍然需要移动一堆东西。它不像 O(n) 像 mid-list 插入，因为它利用旋转的一些效率来旋转，附加到一侧或另一侧，然后旋转回来，但它与插入相去甚远链表中的已知点，剩余 O(n)（尽管有很大的常数除数，因为洗牌整个块比移动每个单独的项目更便宜）。
二，deque 中的每个查找都是 O(n)，而不是 list 中的 O(1)；如前所述，它有一个 64 的常数除数，它在 deque 两端附近下降到 O(1)，但它通常仍然是 O(n)，对于大 [=10] =]秒。 bisect 搜索是 O(log n) ，假设索引序列是 O(1)；对于 deque，它们会是 O(n log n)，因为它们会执行 log n O(n) 索引操作。这与您的测试结果相符； bisect+deque 明显更差。
Java的TreeMap无论如何都不是按照二分查找和链表实现的；链表对此没有好处，因为最终一个完整的二分查找必须来回遍历足够多以完成 O(n) 总工作量，即使它只需要与 O(log n) 个元素进行比较。树图需要某种树结构，你不能用链表和好的算法来伪造它。
Built-in 备选方案包括：
insortof a normallist: 总体来说当然是O(n)，但是昂贵的部分（找到插入的地方）是O(log n)，而且它只是"make room" 步O(n)，真的 便宜O(n)（基本上是memcpy）。对于真正巨大的lists 是不可接受的，但你会惊讶地发现在开销明显相对于 Python 的缓慢之前你需要多大的list。- 延迟缓冲排序：如果查找不频繁，但插入很常见，则将排序推迟到需要时，以尽量减少排序操作的次数；只需将新元素附加到末尾而不进行排序并设置 "needs sorting" 标志，并在设置标志后在查找之前重新
sort。当输入已经大部分排序时，TimSort 算法 非常 很好（比没有优化的通用排序更接近O(n)部分排序通常可以做到），所以它可能没事。 - 如果您在任何给定时间只需要最小的元素，
heapq模块可以使用真正的O(log n)插入和删除来做到这一点，并使用O(1)获得最小值（它是始终索引 0). - 使用
sqlite3数据库（可能通过shelve），适当索引；sqlite3索引默认使用 B-tree，这意味着使用索引键排序的查询会按 "for free". 的排序顺序返回结果
否则，您将必须安装一个 third-party 模块，它提供一个正确排序的 set 类型。