python:在列表中查找包含x的项的索引

最简单的方法 第一 满足条件的索引(在python 2.6或更高版本中:

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

这给了 None 如果没有满足条件的项;更一般地说,可以将作为 next 在这种情况下,无论您需要什么,或者省略第二个参数(在这种情况下,您可以删除一组括号),如果您可以在没有满足条件的项目(例如,您知道情况是不可能的)时获得一个停止迭代异常。

如果您需要在更改到 hugelist 或者它的内容,然后,正如您在问题的第二次编辑中所指出的,构建一个辅助dict(从整数到包含它的第一个dict的索引)更可取。既然你想要 第一 适用的索引,您希望向后迭代(这样点击就更接近 哈格尔主义者 将覆盖更进一步的内容——例如:

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'])

然而,这些只是定性的考虑——考虑在几个“典型/代表性”的值示例上运行基准测试。 哈格尔主义者 (使用) timeit 在命令行提示下,正如我经常建议的那样)to 测量 这些方法的相对速度(以及它们的运行时与我在这个答案开头所展示的无辅助查找的运行时的比较方式——这个比率,加上您期望在连续的两次查找之间执行的平均查找数 哈格尔主义者 变化,将帮助你选择整体战略)。

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

最好的方法可能是设置一个从id到name的reverse dict()。

两个或多个听写可以共享同一个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都是唯一的。如果有重复项,请将dict替换为collections.defaultdict(list)。

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

如果建立索引的频率较低:

在主列表中创建索引值的查找数组,例如

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

...
def addtolookup
...

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

如果frwquency很高,请考虑排序方法(我认为这就是Schwartzian转换答案的含义)。当源列表发生更改时,如果在重建树的性能方面遇到的问题比从生成的索引中获取数据的性能更大,那么这可能是好事;因为将数据插入现有列表(至关重要的是,该列表知道以前最佳匹配字符串时ID的其他可能匹配项)。停止与ID关联)将比在每个增量上从头开始构建列表更快。

编辑

这假设您的ID是密集填充的整数。

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

数据结构似乎不适合它的使用。更改列表是昂贵的-更改本身(如果您进行了任何插入/删除操作)以及由此产生的重新生成dict的需要,或者每次都进行线性扫描。

问题是: 怎样 你的名单有变化吗?

也许您可以使用对象,使用对象本身的指针,而不是担心索引,而不是使用索引(经常更改)?