Python：在列表中找到包含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和名字对应起来。

Answer 2

从性能的角度来看，如果你有100万条记录，可能需要考虑换成数据库或者其他的数据结构。用现在这种数据结构来处理这些记录，速度会比较慢，因为它是线性时间操作。不过，如果你打算经常进行这种查询，可以先创建一个记录和ID的字典，这样会更方便。

Answer 3

获取满足条件的第一个索引的最简单方法（适用于 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 变化之间执行的查找次数，将帮助你选择整体策略）。