Python中高效的列表操作

Question

Python中高效的列表操作

3

我有一个很大的列表，需要经常查找满足相当复杂条件（不是相等），也就是说，我被迫检查列表中的每个项目，直到找到一个符合条件的。条件会改变，但有些项目比其他项目更匹配。因此，我希望每次找到一个匹配项时将其置于列表前面，以便更快地找到频繁匹配的项。

有没有一种高效的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]:
    ...

- R2-D2

2个回答

0

您可以使用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]))

- Dunes

1

“deque.rotate” 仍然会导致整个内存移动，从而导致 O(n) 的时间复杂度，对吗？ - zehnpaard

我不这么认为。我的理解是deque由链表支持。旋转只是改变deque指向的头项。它的时间复杂度是O(n)，但内存更改是O(1)。 - Dunes

@Dunes，这比你想象的要复杂一些，请参见Python源代码中的Modules/_collectionsmodule.c。deque是一个链接块的链表（每个块目前最多包含62个PyObject*），使得rotate有些复杂，并且需要大量的memcpy操作。我认为O(n)适用于时间和“内存更改”指标。 - Alex Martelli

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex Martelli · Accepted Answer

考虑采用Pythonic方法。正如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)

你只需要定义你实际需要使用的变异器，例如，如果你不会执行插入、排序、__delitem__等操作，则无需定义这些操作，你可以将它们委托给列表。

补充：在Python 3.2或更高版本中，functools.lru_cache实际上可以为您完成大部分工作——用它来装饰查找函数，您将获得一个更好的缓存实现，如果需要，还可以限制缓存大小。要清除缓存，您需要在适当的位置调用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在一段时间内基本保持不变。在这种情况下，可以使用谓词作为特征提取和检查函数，形成字典的关键字--例如：

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