我正在寻找Python的链表和相关算法实现。我问的每个人都建议使用内置的Python列表,但性能测量表明,列表的插入和删除是应用程序的瓶颈。实现一个简单的链表是很简单的,但我想知道是否有一个成熟的库,它包括一些操作,如排序、合并、拼接、搜索、下限/上限等
我知道这是一个骗局,但在任何搜索引擎上搜索python列表都会得到预期的糟糕结果,大多数人只是说python(pfft!)中不需要链表
PS:我需要在列表中的任何位置插入和删除,而不仅仅是结尾
好的,你自找的: 我需要维护一个有几十万条记录的有序列表。我将(一个接一个地)向前遍历列表,在每个条目上使用访问者,从开始或通过二进制搜索找到的位置开始。当找到与谓词匹配的条目时,会将其从列表中删除,然后从删除条目的前一个位置开始,对列表的子集执行另一个二进制搜索,直到事先统计确定位置为止。忽略错误条件,修改后的条目可用于创建另一个链表,该链表拼接到通过第二次二进制搜索找到的新位置。从删除条目的位置继续迭代。有时,可以在列表中的任何位置添加或删除数千个连续的有序条目。有时,必须以增量方式搜索和删除数千个不连续的条目
python的列表是不可接受的,因为插入/删除的成本太高,二进制搜索速度的微小提高与总成本完全无关。我们的内部测试证实了这一点
如果我忽略了任何细节,也许我可以通过电子邮件向您发送一份我公司的保密协议副本,并就此事与您私下通信讽刺。结束()
Python列表是O(1) for operations at the end of the list。如果您将以半连续的方式进行所有插入操作(与C类似,只将一个指针作为某种“游标”保留在列表的中间),那么只需使用两个Python列表就可以节省大量的工作量。一个列表显示光标前的内容,一个列表显示光标后的内容;移动光标涉及从一个列表中拖出下一个项目并将其附加到另一个列表中。这使您可以在光标位置进行任意O(1)插入,与创建一个完整的新数据结构相比,所需的工作量和重复性要少得多,从而可以重用许多现有的列表函数
但是,对于允许列表中有多个引用的完全通用的情况,您可能无法创建某种类型的链接列表
编辑:您没有认真考虑对链接列表进行“二进制搜索”,是吗?二进制搜索在本质上是连续的数据结构上甚至没有意义
无论如何,如果你对线性时间搜索没问题,并且你的插入总是保持列表顺序而不重新排序,那么一个简单的链表可能就是你所需要的。如果你像迭代一样做大量的搜索,你应该考虑快速索引,如果需要诉诸的话,像树之类的东西会更好。p>
令人费解的是,每个人都要求有理由需要一个链接列表。链表是最基本的数据结构之一,其原因是:它们具有其他主要数据结构所缺乏的属性,如果需要这些属性,则需要链表或其近亲之一。如果您不理解为什么链表是一种重要的数据结构,不能总是用deque或二叉树来替换,那么您永远不应该传递“数据结构简介”类
这里有一个快速的实现,支持通常的功能:在给定节点引用的任意点进行常量时间插入,将列表拆分为两个列表,并将一个列表插入另一个列表的中间(拼接)。支持通用Python接口:push、pop、pushleft、popleft、extend、普通迭代、片上迭代(getiter)
我刚刚写了这篇文章,所以它是博士论文,但没有经过生产测试;可能仍然有bug
这里有一个blog post分享你的痛苦。它包括链表的实现和性能比较
也许
blist
会更好,但是(从here)请注意,它实际上是作为B+树实现的,允许所有这些操作都有很好的性能
相关问题 更多 >
编程相关推荐