的片我有一个名为“数据”非常大名单，我需要回答的等效查询到快速成员名单

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

对的，B和X不同的值。

是否有可能预处理的数据，使这些查询快速

来源

2013-08-03 phoenix

您可能需要添加更多关于'x'，'a'和'b'如何变化的信息。许多不同的'x's针对'[a：b]'或者'x'的一个实例，针对许多不同的'[a：b]'切片进行检查...？另外，数据是否可以分类？ –

我可以为每个a，b对有许多不同的x。列表数据并未被排序。 – phoenix

想法

您可以创建一个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）“通过索引获取”的复杂性，那么每个查询在这里。

来源

2013-08-03 21:47:59 RiaD

['bisect']（http://docs.python.org/2/library/bisect.html）模块提供了简化二进制搜索代码并使其更快的工具。 – user2357112

@ user2357112谢谢，补充。 – RiaD

我编辑了你的答案，删除了注释掉的代码，并且只做了一次而不是两次搜索键“x”。我进一步作出了美学改变，使答案更加pythonic（没有分号，没有'！'，'defaultdict'而不是手动检查，'枚举（数据）'而不是'range（len（data））'。） – orlp

是的，你可以预处理这些切片成组，从而使会员查找O(1)代替O(n)：

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

来源

2013-08-03 21:48:11

-1这不回答这个问题。如果我没有弄错，那么这个问题想要预处理数据，以便将来在任意片上的成员资格请求很快，而不是为一个特定的片预先计算一组。 – orlp

@nightcracker：我不确定，因为他以不同的方式格式化“数据”这个词。不过，你可能是对的 - 在这种情况下，答案可能是“不”。不幸的是，菲尼克斯没有对我的澄清要求作出反应...... –

啊，我没有看到你的澄清。我确实认为，因为'a，b'是查询的一部分，它们可能会有所不同。但答案肯定是，请看RiaD的答案。 – orlp

列入名单的数据库，并采取内置的索引，优化和缓存的优势。例如，来自PostgreSQL手册：

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

但是你也可以使用sqlite来简化（和Python的标准库中的可用性）。从Python's documentation, regarding indexing：

行实例充当连接对象的高度优化的row_factory。它试图模仿大部分功能中的元组。

它支持按列名称和索引，迭代，表示，相等性测试和len（）进行映射访问。

该网页上的其他地方：

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

来源

2013-08-03 23:17:36

快速成员名单

回答

想法

伪

相关问题