python中的高效列表操作(Efficient list manipulation in python)

 我有一个很大的列表，并且经常需要找到一个满足相当复杂条件（不相等）的项目，即我被迫检查列表中的每个项目，直到找到一个。 条件发生变化，但有些项目比其他项目更频繁。 所以我想在每次找到匹配项目时将匹配项目带到列表的前面，这样可以更快地找到经常匹配的项目。 
 
 有没有一种有效的 pythonic方法来做到这一点？ 
 
 序列（ [] ）由数组支持，因此删除中间某处的项目并将其添加到数组中意味着移动每个前一项目。 这是在O（n）时间，不好。 
 
 在C中，您可以构建链接列表，并在找到时自行移动项目。 在Python中有一个deque ，但是你不能引用节点对象，也不能访问.next指针。 
 
 Python中的自制链表非常慢。 （事实上​​，如果不移动任何项目，它比普通线性搜索慢。） 
 
 遗憾的是， dict或set基于价值平等来查找项目，因此不适合我的问题。 
 
 举个例子，这是条件： 
 
u, v, w = n.value   # list item
if v in g[u] and w in g[v] and u not in g[w]:
    ...

I have a large list and regularily need to find an item satisfying a rather complex condition (not equality), i.e. I am forced to check every item in the list until I find one. The conditions change, but some items match more often then others. So I would like to bring the matching item to the front of the list each time I find one, so frequently matching items are found more quickly.
 
Is there an efficient, pythonic way to do this?
 
Sequences ([]) are backed by an array, so removing an item somewhere in the middle and prepending it to the array means moving every previous item. That's in O(n) time, not good.
 
In C you could build a linked list and move the item on your own when found. In Python there is a deque, but afaik you cannot reference the node objects nor have access to .next pointers.
 
And a self-made linked list is very slow in Python. (In fact it's slower than ordinary linear search without moving any item.)
 
Sadly, a dict or set finds items based on value equality and thus doesn't fit my problem.
 
As an illustration, here's the condition:
 
u, v, w = n.value   # list item
if v in g[u] and w in g[v] and u not in g[w]:
    ...

原文：https://stackoverflow.com/questions/28004021