Python：在lis中查找包含X的项的索引

Question

我有一个庞大的数据列表，超过100万条记录的格式与此类似（尽管这是一个更简单的形式）：

[
  {'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万以上的记录。我想我现在会寻求这个解决方案。在

Answer 1

最好的方法可能是设置一个从id到names的反向dict（）。在

Answer 2

性能方面，如果有1M条记录，则可能需要切换到数据库或其他数据结构。对于给定的数据结构，这将是一个线性时间操作。如果您计划经常执行此查询，那么可以创建一个ID来记录dict。在

Answer 3

获取满足条件的第一个索引的最简单方法（在Python2.6或更高版本中：

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

如果没有项满足条件，则这将给出None；更一般的情况下，您可以将第二个参数作为next内置参数的第二个参数，或者忽略第二个参数（在这种情况下，您可以删除一组括号），前提是没有项满足条件时会出现StopIteration异常（例如。，你知道这种情况是不可能的）。在

如果在对hugelist或其内容的更改之间需要执行这种操作的次数非常少，那么，正如您在问题的第二次编辑中所指出的那样，最好构建一个辅助dict（从整数到包含它的第一个dict的索引）。因为您需要第一个适用的索引，所以需要向后迭代（因此，接近hugelist开头的命中将覆盖更进一步的命中）--例如：

^{pr2}$

[[不能使用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更改之间执行的平均查找次数，将有助于您选择总体策略）。在