python - 列表切片中的快速成员资格

Question

我有一个名为“数据”的非常大的列表，我需要回答相当于

if (x in data[a:b]):

对于 a、b 和 x 的不同值。

是否可以预处理数据以使这些查询快速

Answer 1

主意

您可以创建一个dict. 对于每个元素，存储它出现的位置的排序列表。

回答查询：二进制搜索大于或等于的第一个元素a，检查它是否存在并且小于b

伪代码

预处理：

from collections import defaultdict

byvalue = defaultdict(list)

for i, x in enumerate(data):
    byvalue[x].append(i)

询问：

def has_index_in_slice(indices, a, b):
   r = bisect.bisect_left(indices, a)

   return r < len(indices) and indices[r] < b

def check(byvalue, x, a, b):
    indices = byvalue.get(x, None)
    if not indices: return False

    return has_index_in_slice(indices, a, b)

O(log N)如果我们假设list并且dict具有 O(1)“按索引获取”复杂性，那么这里的复杂性是每个查询。

Answer 2

是的，您可以将这些切片预处理为集合，从而进行成员资格查找，O(1)而不是O(n)：

check = set(data[a:b])
if x in check:
    # do something
if y in check:
    # do something else

Answer 3

将列表放入数据库并利用内置的索引、优化和缓存。例如，来自 PostgreSQL 手册：

一旦创建了索引，就不需要进一步的干预：当表被修改时，系统会更新索引，当它认为这样做比顺序表扫描更有效时，它会在查询中使用索引。

但是您也可以使用 sqlite 来简化（以及在 Python 标准库中的可用性）。从Python 的文档中，关于索引：

Row 实例用作 Connection 对象的高度优化的 row_factory。它试图在其大部分特征中模仿一个元组。

它支持按列名和索引、迭代、表示、相等测试和 len() 进行映射访问。

以及该页面上的其他地方：

Row 提供对列的基于索引和不区分大小写的基于名称的访问，几乎没有内存开销。它可能比您自己的基于字典的自定义方法甚至基于 db_row 的解决方案更好。