有效地将不可散列的对象映射到它们在列表中的索引

Efficiently mapping unhashable objects to their index in a list

一个Python列表

f = [x0, x1, x2]

可以被视为从 [0, 1, ..., len(f) - 1] 到其元素集的映射的有效表示。 "efficient" 我的意思是 f[i] returns 在 O(1) 时间内与 i 关联的元素。

逆映射可以定义如下:

class Inverse:
    def __init__(self, f):
        self.f = f

    def __getitem__(self, x):
        return self.f.index(x)

这有效,但是 Inverse(f)[x] takes O(n) time on average.

或者,可以使用 dict:

f_inv = {x: i for i, x in enumerate(f)}

这有O(1)的平均时间复杂度,但它要求列表中的对象是hashable

有没有一种方法可以在 O(1) 平均时间内为 unhashable 对象定义提供基于相等性查找的逆向映射?

编辑:示例输入和预期输出:

>>> f = [x0, x1, x2]
>>> f_inv = Inverse(f)  # this is to be defined
>>> f_inv[x0]  # in O(1) time
0
>>> f_inv[x2]  # in O(1) time
2

不幸的是,您在这里遇到了算法限制。快速查找结构(如哈希表或二叉树)非常高效,因为它们将对象放在特定的桶中或根据它们的值对它们进行排序。这要求它们在您将它们存储在此结构中的整个过程中是可散列的或可比较的一致,否则查找很可能会失败。

如果您需要的对象是可变的(通常是它们不可散列的原因),那么只要您跟踪的对象发生变化,您就需要更新数据结构。最安全的方法是创建不可变对象。如果你需要改变一个对象,那么创建一个新的,从字典中删除旧的,并将新的对象作为具有相同值的键插入。

相对于字典的大小,这里的操作仍然是O(1),您只需要考虑每次更改时复制对象的成本是否值得。

您可以创建关联字典,将对象 ID 映射回列表索引。

明显的缺点是您必须在索引中搜索标识对象,而不是仅相等的 eobject。

从好的方面来说,通过使用 collections.abc 创建自定义 MutableSequence class,您可以使用最少的代码编写一个 class,将您的数据既作为序列又作为反向字典。

from collections.abc import MutableSequence
from threading import RLock


class MD(dict):
    # No need for a full MutableMapping subclass, as the use is limited
    def __getitem__(self, key):
        return super().__getitem__(id(key))


class Reversible(MutableSequence):
    def __init__(self, args):
        self.seq = list()
        self.reverse = MD()
        self.lock = RLock()
        for element in args:
            self.append(element)

    def __getitem__(self, index):
        return self.seq[index]

    def __setitem__(self, index, value):
        with self.lock:
            del self.reverse[id(self.seq[index])]
            self.seq[index] = value
            self.reverse[id(value)] = index

    def __delitem__(self, index):
        if index < 0:
            index += len(self)
        with self.lock:
            # Increase all mapped indexes
            for obj in self.seq[index:]:
                self.reverse[obj] -= 1
            del self.reverse[id(self.seq[index])]
            del self.seq[index]

    def __len__(self):
        return len(self.seq)

    def insert(self, index, value):
        if index < 0:
            index += len(self)
        with self.lock:
            # Increase all mapped indexes
            for obj in self.seq[index:]:
                self.reverse[obj] += 1
            self.seq.insert(index, value)
            self.reverse[id(value)] = index

瞧瞧:只需使用此对象代替您的列表,并使用 public 属性 "reverse" 获取标识对象的索引。 认为你可以通过尝试使用不同的策略来增加 "MD" class 的 "intelligence",比如使用对象本身,如果它们是可散列的,并且只求助于 id 或其他自定义需要时基于其他对象属性的键。这样您就可以减少搜索同一对象的需要。

因此,对于列表上的普通操作,此 class 保持恢复的字典同步。但是,不支持切片索引。 有关详细信息,请查看 https://docs.python.org/3/library/collections.abc.html

上的文档