Python 链表 O(1) 插入/删除 [英] Python linked list O(1) insert/remove

问题描述

我正在寻找 Python 的链表和相关算法实现.我问的每个人都只推荐使用内置的 Python 列表，但性能测量表明列表插入和删除是我们应用程序的瓶颈.实现一个简单的链表很简单，但是我想知道是否有一个成熟的库，其中包括一些操作，例如排序，合并，拼接，搜索，下/上界等......

I am looking for a linked list and related algorithms implementation for Python. Everyone I ask just recommends using built in Python lists, but performance measurements indicate that list insertion and removal is a bottleneck for our application. It's trivial to implement a simple linked list, but I wonder if there is a mature library which includes some operations like sort, merge, splice, search, lower/upper bound, etc...

我知道这是个骗局，但在任何搜索引擎上搜索 python 列表都会得到可预见的糟糕结果，大多数人只是说 python 中不需要链表(pfft！).

I know this is a dupe, but searching for python list on any search engine gives predictably poor results, with most people just saying that linked lists are unneeded in python (pfft!).

PS:我需要从列表中的任何位置插入和删除，而不仅仅是末端.

PS: I need to insert and remove from anywhere in the list, not just the ends.

好的，你要求它:我需要维护一个包含数十万个条目的有序列表.我将遍历列表(一个接一个)，在每个条目上使用一个访问者，从头开始或从二进制搜索找到的位置开始.当找到匹配谓词的条目时，将其从列表中删除，然后，从删除条目的先前位置开始，对列表的子集执行另一次二分搜索，直到预先统计确定的位置.忽略错误条件，修改后的条目可用于创建另一个链表，该链表拼接到通过第二次二分查找找到的新位置.从条目被移除的位置继续迭代.有时，可能会向列表中的任何位置添加/删除数千个连续的有序条目.有时必须逐步搜索和删除数千个不连续的条目.

OK, you asked for it: I need to maintain an ordered list of several hundred thousand entries. I will iterate over the list forwards (one by one), using a visitor on each entry, starting from the beginning or a position found by a binary search. When an entry matching a predicate is found it is removed from the list, and then, another binary search is performed on a subset of the list beginning from the removed entry's previous position, until a position determined statistically beforehand. Ignoring the error condition, the modified entry may be used to create another linked list which is spliced into the new position found through the second binary search. Iteration is continued from the position where the entry was removed. On occasion, several thousand contiguous ordered entries may be added to/removed from any place in the list. Sometimes several thousand non-contiguous entries must be searched for and removed incrementally.

python 的列表是不可接受的，因为插入/删除的成本高得令人望而却步，而且二分查找速度的微小提升与总成本完全无关.我们的内部测试证实了这一点.

python's list is unnacceptable as the cost of insertion/removal is prohibitive, and the minor gains in speed for the binary search are totally irrelevant to the total cost. Our in house tests confirm this.

如果我忽略了任何细节，也许我可以通过电子邮件将我公司的保密协议的副本发送给您，然后我可以就此事私下与您通信.讽刺.end().

if I have neglected any detail perhaps I can e-mail you a copy of my company's non-disclosure agreement and I can privately correspond with you on the matter. sarcasm.end().

推荐答案

这里有一个 博文 分享您的痛苦.它包括一个链表的实现和一个性能比较.

Here's a blog post sharing your pain. It includes an implementation of a linked list and a performance comparison.

也许 blist 会更好，不过(来自 这里)?

Perhaps blist would be better, though (from here)?

BList 的用例比 Python 的列表稍慢如下(O(log n) vs. O(1)):

The use cases where the BList is slightly slower than Python's list are as follows (O(log n) vs. O(1)):

1. 一个永远不会改变长度的大列表.
2. 插入和删除仅在末尾的大型列表列表 (LIFO).

排除免责声明，以下是一些用例，其中BLists 比内置列表:

With that disclaimer out of the way, here are some of the use cases where the BLists is dramatically faster than the built-in list:

1. 在大列表中插入或删除(O(log n) vs. O(n))
2. 获取大列表的大切片(O(log n) vs O(n))
3. 制作大型列表的浅拷贝(O(1) vs. O(n))
4. 更改大列表的大片段(O(log n + log k) vs. O(n + k))
5. 将一个列表相乘以形成一个大的、稀疏的列表(O(log k) vs.O(kn))

请注意，它实际上是作为 B+ 树实现的，可为所有这些操作提供出色的性能.

Note that it's actually implemented as a B+ tree, allowing great performance for all those operations.

这篇关于Python 链表 O(1) 插入/删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！