我正在寻找Python的链表和相关算法实现.我要求的每个人都建议使用内置的Python列表,但性能测量表明列表插入和删除是我们应用程序的瓶颈.实现一个简单的链表是微不足道的,但我想知道是否有一个成熟的库,其中包括一些操作,如排序,合并,拼接,搜索,下限/上限等...
我知道这是一个骗局,但在任何搜索引擎上搜索python列表都会给出可预测的糟糕结果,大多数人只是说python中不需要链接列表(pfft!).
PS:我需要从列表中的任何位置插入和删除,而不仅仅是结尾.
好的,你要求它:我需要维护一个有数十万个条目的有序列表.我将逐步遍历列表(逐个),使用每个条目上的访问者,从头开始或二进制搜索找到的位置.当找到与谓词匹配的条目时,将其从列表中移除,然后,对从列表的子集开始的另一个二进制搜索从所移除的条目的先前位置开始,直到预先在统计上确定的位置.忽略错误条件,修改的条目可以用于创建另一个链接列表,该链接列表被拼接到通过第二二进制搜索找到的新位置.从删除条目的位置继续迭代.有时,可以在列表中的任何位置添加/移除数千个连续的有序条目.有时必须逐步搜索和删除数千个不连续的条目.
python的列表是不可接受的,因为插入/删除的成本过高,而二进制搜索的速度微小增益与总成本完全无关.我们的内部测试证实了这一点.
如果我忽略了任何细节,或许我可以通过电子邮件向您发送我公司的保密协议副本,我可以就此事私下与您通信.sarcasm.end().
我必须将C++ STL应用程序移植到Python.我是一个Python新手,但已编程超过十年.我对STL有很多经验,发现它让我迷上了使用C++.过去几天我一直在Google上搜索以下内容:
并且已经找到了关于上述主题的帖子,关于Python列表的教程,这些教程明显没有进展,或者是死胡同.我对自己缺乏成功感到非常惊讶,我想我只是因为过度工作而进入了糟糕的搜索条件!
(我的问题)我可以获得Python STL包装器,或者像STL一样工作的Python列表的接口吗？如果没有,有人可以指向我一个真正的高级教程或论文来管理非常大的非平凡对象的集合？
PS我可以很容易地为一两个用途实现变通方法,但如果管理层希望移植更多代码,我想准备好立即用等效的Python代码替换我找到的任何STL代码.是的,我已经测量过并且需要完全具有最佳代码!我不能做冗余的搜索和搜索!
(附录)感谢您的回复,我已经查看了一些参考文献并很高兴.回应一些评论:
1 - 它正被移植到python,因为管理层这么说,我会尽快不管它 - 如果它不能解决,为什么要解决它？
2 - 使用非平凡对象的高级列表使用,我的意思是:许多不同的方式来订购和比较对象,而不是通过一个cmp方法.我想广泛地拼接,排序,合并,搜索,插入,擦除和组合列表.我想要列表迭代器列表,我想避免复制.
3 - 我现在知道内置列表实际上是数组,我应该寻找一个不同的python类.我认为这是我困惑的根源.
4 - 当然我正在学习以Python方式做事,但我也有最后期限.我正在移植的STL代码工作正常,我想尽可能少地改变它,因为这会引入错误.
感谢大家的投入,我真的很感激.