Python 中的高效列表操作

Question

我有一个很大的列表，经常需要找到一个满足相当复杂条件（不是相等）的项目，即我被迫检查列表中的每个项目，直到找到一个。条件会发生变化，但某些项目比其他项目更频繁地匹配。因此，每次找到匹配项时，我都想将匹配项放在列表的前面，因此通常可以更快地找到匹配项。

有没有一种有效的、pythonicic的方法可以做到这一点？

序列（[]）由数组支持，因此删除中间某处的项目并将其添加到数组中意味着移动每个先前的项目。那是在O（n）时间，不好。

在 C 中，您可以构建一个链表，并在找到时自行移动项目。在 Python 中有一个deque，但 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]:
    ...

Answer 1

考虑使用 Python 方法。 正如 Ed Post 曾经说过的那样，"坚定的真正程序员可以用任何语言编写 FORTRAN 程序"——这概括了......你正在尝试用Python编写C，但它对你来说效果不佳：-）

相反，考虑在list旁边放置一个辅助dict缓存 - 缓存找到项目的索引（仅在列表结构的"深度"更改时才需要失效）。 更简单，更快捷...

最好通过在小班中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__等，不需要定义这些，你可以把它们委托给列表。

补充：在Python 3.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一段时间内几乎保持不变。 在这种情况下，可以使用谓词 one 作为特征提取和检查函数，它形成字典中的键 - 例如：

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 - 它是Python单链表和双链表的C编码实现（对于每种类型，它实现了三种类型：列表本身，列表节点和列表的迭代器）。

Answer 2

您可以使用

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]))