的Python：发现含有X列表

我有数据的类似形式的巨大的名单，1M以上的记录（虽然这是一个非常简单的形式）项的指标是：的Python：发现含有X列表

[ 
    {'name': 'Colby Karnopp', 'ids': [441, 231, 822]}, 
    {'name': 'Wilmer Lummus', 'ids': [438, 548, 469]}, 
    {'name': 'Hope Teschner', 'ids': [735, 747, 488]}, 
    {'name': 'Adolfo Fenrich', 'ids': [515, 213, 120]} 
    ... 
]

给定一个id为735，我想找到Hope Teschner的索引2，因为给定的id属于Hope的id列表。什么是最好的（性能明智）的方式来做到这一点？

感谢您的任何提示。

编辑

也许应该提到这一点，但一个ID 可能出现不止一次。如果一个特定的ID 确实不止一次出现，我希望给定ID的最低索引。

列表中的数据将会频繁更改，所以我对构建字典感到犹豫不决，因为字典需要修改/重建每次更新列表，因为索引是字典中的值 - 即。更改列表中某个项目的位置将需要更新字典中的每个值，其索引大于新更改的索引。

编辑编辑

我只是做了一些基准，似乎重建字典是相当快的甚至超过100万的记录。我想我现在会继续寻求这个解决方案。

来源

2009-12-29 sberry

一般来说，任何能够提高搜索性能的任何东西都需要你排序，或者创建一个单独的散列表等等。所以最重要的问题是......你需要访问多少次这个清单？这是建立一次，并多次访问？我不是一个蟒蛇开发者，所以我只是在那里谈论普遍性。 – 2009-12-29 17:48:02

拿到第一指标满足条件（在Python 2.6或更高

最简单的方法：

next((i for i, d in enumerate(hugelist) if 735 in d['ids']), None)

这给None如果项目不符合条件;更通常，你可以把作为第二个参数在这种情况下，无论您需要什么，都可以嵌入next，或者省略第二个参数（在这种情况下，您可以删除一组括号），如果没有项目满足条件的情况下可以获得StopIteration异常（例如，您知道这种情况是不可能的）

如果您需要在hugelist或其内容的更改之间进行此类操作的次数超过几次，那么，如您在对问题的第二次编辑中指出的那样，建立一个辅助字典（从整数到第一个字典的索引，包含它）是优选的。既然你想要的第一适用的指标，你想向后遍历（所以命中更接近的hugelist开始将覆盖那些进一步上） - 例如：

auxdict = {} 
L = len(hugelist) - 1 
for i, d in enumerate(reversed(hugelist)): 
    auxdict.update(dict.fromkeys(d['ids'], L-i))

[你不能使用reversed(enumerate(...，因为enumerate返回一个迭代器，而不是一个列表，并且reversed被优化为仅对一个序列参数起作用 - 因此需要L-i]]。

可以其他方式构建auxdict，包括但反转，例如：

auxdict = {} 
for i, d in enumerate(hugelist): 
    for item in d['ids']: 
    if item not in auxdict: auxdict[item] =i

但这很可能是慢得多，由于在内部循环执行的if数量庞大。直接dict构造函数（以键的顺序，值对）也可能会比较慢，因为需要内部循环：

L = len(hugelist) - 1 
auxdict = dict((item, L-i) for i, d in enumerate(reversed(hugelist)) for item in d['ids'])

但是，这些都只是定性的考虑 - 考虑在几个运行基准您可以在hugelist（在命令行提示符下使用timeit，正如我经常推荐的那样）的“典型/代表性”示例的值为度量这些方法的相对速度（以及它们的运行时间与我在这个答案开始时显示的一个独立查询 - 这个比率，加上你期望在连续hugelist变化之间执行的平均查找次数，wi将帮助您选择整体战略）。

来源

2009-12-29 18:41:30

从性能上看，如果您有1M条记录，则可能需要切换到数据库或不同的数据结构。对于给定的数据结构，这将是一个线性时间操作。你可以创建一个ID来记录一次，但如果你打算经常这样做。

来源

2009-12-29 17:42:29 Pace

最好的方法可能是设置一个反向字典（）从ID到名称。

来源

2009-12-29 17:43:28

两个或多个字符可以共享相同的ID吗？如果是这样，我认为你需要返回一个索引列表。

如果你想要做一个一次性的搜索，那么你可以用一个列表理解做到这一点：

>>> x = [ 
... {'name': 'Colby Karnopp', 'ids': [441, 231, 822]}, 
... {'name': 'Wilmer Lummus', 'ids': [438, 548, 469]}, 
... {'name': 'Hope Teschner', 'ids': [735, 747, 488]}, 
... {'name': 'Adolfo Fenrich', 'ids': [515, 213, 120]}, 
     ... 
... ] 

>>> print [idx for (idx, d) in enumerate(x) if 735 in d['ids']] 
[2]

但是，如果你想这样做了很多，列表不会有太大变化则是创建一个反向索引要好得多：

>>> indexes = dict((id, idx) for (idx,d) in enumerate(x) for id in d['ids']) 
>>> indexes 
{213: 3, 515: 3, 548: 1, 822: 0, 231: 0, 488: 2, 747: 2, 469: 1, 438: 1, 120: 3, 441: 0, 735: 2} 
>>> indexes[735] 
2

注意：上面的代码假定每个ID都是唯一的。如果有重复项，则使用collections.defaultdict（list）替换字典。

NNB：上面的代码将索引返回到原始列表中，因为这是您要求的。但是，除非您想使用索引从列表中删除它，否则最好返回实际的dict而不是索引。

来源

2009-12-29 18:08:54

如果建索引的频率低：

创建索引值的查找数组到主列表中，这样如

lookup = [-1,-1,-1...] 

... 
def addtolookup 
... 

mainlistindex =lookup[myvalue] 
if mainlistindex!=-1: 
name=mainlist[mainlistindex].name

如果frwquency高，考虑排序方法（我认为这就是Schwartzian变换的答案）。如果您在源列表更改时重建树的性能遇到更多问题，则可能比使用制造索引获取数据的性能更好;作为将数据插入现有列表（关键地知道关于其他可能的匹配的id，用于当先前的最佳匹配字符串停止与id关联时）将比在每个增量上从头开始构建列表更快。

编辑

这假定你的ID是人口稠密的整数。

为提高访问排序列表的性能，可以将它划分为400-600个条目的块，以避免将整个列表反复向前或向后移动一个或几个位置，并用二进制算法进行搜索。

来源

2009-12-29 18:23:21 martinr

似乎数据结构不适合其使用。更改列表代价昂贵 - 无论是更改本身（如果您执行任何插入/分隔）以及由此产生的需要重新生成字典，或者每次都进行线性扫描。

现在的问题是：如何更改？

也许不是使用索引（频繁更改），您可以使用对象，并使用指向对象本身的指针而不是担心索引？

来源

2009-12-30 17:34:47

的Python：发现含有X列表

回答

相关问题