python中的有效列表操作
我有一个大的列表，并且经常需要找到一个满足相当复杂的条件(不相等)的项目，也就是说，我被迫检查列表中的每一项，直到找到一个。情况不同，但有些项目比其他项目更经常匹配。因此，每次我找到匹配项时，我都会将匹配项放在列表的前面，因此匹配项的查找速度会更快。
有没有一种高效的，仿生的方法来做这件事？
序列([])是由数组支持的，因此删除中间的某个项并将其放在数组的前面意味着移动以前的每个项。那是在O(n)时间，不好。
在C中，您可以构建一个链接列表，并在找到时自己移动该项。在deque中有一个.next，但是afaik不能引用节点对象，也不能访问.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]:
...回答 2
Stack Overflow用户
发布于 2015-01-17 20:40:25
相反，考虑一下毕达通的方法。正如埃德·波斯特曾经说过的，“坚定的真正的程序员可以用任何语言编写FORTRAN程序”--这概括了.您正在尝试用Python编写C，但它对您不太好：-)
相反，可以考虑在dict旁边放置一个辅助list缓存--缓存找到项的索引(只需要在列表结构的“深度”更改时才失效)。更简单的和更快。
最好的方法是在一个小类中使用list和dict：
class Seeker(object):
def __init__(self, *a, **k):
self.l = list(*a, **k)
self.d = {}
def find(self, value):
where = self.d.get(value)
if where is None:
self.d[value] = where = self.l.find(value)
return where
def __setitem__(self, index, value):
if value in self.d: del self.d[value]
self.l[index] = value
# and so on for other mutators that invalidate self.d; then,
def __getattr__(self, name):
# delegate everything else to the list
return getattr(self.l, name)您只需定义实际需要使用的变异器--例如，如果不执行insert、sort、__delitem__和&c，则不需要定义这些变量，只需将它们委托给列表即可。
补充:在Python3.2或更高版本中，functools.lru_cache实际上可以为您完成大部分工作--使用它来装饰find，您将获得更好的缓存实现，如果您愿意，可以限制缓存大小。要清除缓存，您需要在适当的位置调用self.find.cache_clear() (我在上面使用self.d = {}) --不幸的是，这个关键的功能还没有(！)被记录下来(更新文档的志愿者并不是更新代码的相同的).但是，相信我，它不会消失在你身上：-)
补充: OP编辑了Q，以澄清他不是在“值相等”，而是一些更复杂的条件集，例如：
def good_for_g(g, n):
# for some container `g` and item value `n`:
u, v, w = n.value
return v in g[u] and w in g[v] and u not in g[w]那么，那么，把“好”物品带到正面的愿望反过来又取决于它们的“善”是“粘性”的，也就是说，g在一段时间内基本上保持不变。在这种情况下，可以使用谓词1作为特征提取和检查函数，它构成字典中的键--例如：
class FancySeeker(object):
def __init__(self, *a, **k):
self.l = list(*a, **k)
self.d = {}
def _find_in_list(self, predicate):
for i, n in enumerate(self.l):
if predicate(n):
return i
return -1
def find(self, predicate):
where = self.d.get(predicate)
if where is None:
where = self._find_in_list(predicate)
self.d[predicate] = where
return where以此类推。
因此，剩下的困难是将predicate以一种适合于有效索引到dict的形式。如果predicate只是一个函数，那么没有问题。但是，如果predicate是一个带有参数的函数，如由functools.partial形成的函数，或者作为某些实例的绑定方法，则需要进一步的处理/包装才能使索引工作。
对functools.partial的两个调用具有相同的绑定参数和函数，例如，不返回相同的对象--一个调用必须检查返回对象的.args和.func，以确保为任何给定的(func, args)对返回“单例”。
此外，如果某些绑定参数是可变的，则需要使用它们的id来代替它们的hash (否则原始的functools.partial对象是不可接受的)。对于绑定方法，它会变得更加复杂，尽管它们同样可以被包装到一个可接受的、“平等调整的”Predicate类中。
最后，如果这些循环太麻烦，而且您真的希望快速实现链接列表，那么请看https://pypi.python.org/pypi/llist/0.4 --它是一个C代码的实现，用于Python的单链接和双链接列表(对于每种类型，它实现了三种类型:列表本身、列表节点和列表的迭代器)。
Stack Overflow用户
发布于 2015-01-17 20:53:45
使用deque.rotate，您完全可以做您想做的事情。
from collections import deque
class Collection:
"Linked List collection that moves searched for items to the front of the collection"
def __init__(self, seq):
self._deque = deque(seq)
def __contains__(self, target):
for i, item in enumerate(self._deque):
if item == target:
self._deque.rotate(i)
self._deque.popleft()
self._deque.rotate(-i+1)
self._deque.appendleft(item)
return True
return False
def __str__(self):
return "Collection({})".format(str(self._deque))
c = Collection(range(10))
print(c)
print("5 in d:", 5 in c)
print(c)给出以下输出：
Collection(deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))
5 in c: True
Collection(deque([5, 0, 1, 2, 3, 4, 6, 7, 8, 9]))https://stackoverflow.com/questions/28004021
复制相似问题
腾讯云开发者
