我有一个字典列表，我正在寻找其中一个键的唯一值列表。
这是我想出的，但不禁想知道它的效率、时间和/或记忆是否明智：
list(set([d['key'] for d in my_list]))
有没有更好的办法？
问问题
348 次
1 回答
6
这：
list(set([d['key'] for d in my_list]))
…构造一个所有值的列表，然后构造一个仅包含唯一值的集合，然后从集合中构造一个列表。
假设您有 10000 个项目，其中 1000 个是唯一的。您已将最终存储量从 10000 项减少到 1000 项，这很棒 — 但您已将峰值存储量从 10000 项增加到 11000 项（因为显然必须有一段时间，整个列表和几乎整个集合都同时在内存中）。
有两种非常简单的方法可以避免这种情况。
首先（只要你有 Python 2.4 或更高版本）使用生成器表达式而不是列表推导式。在大多数情况下，包括这个，这只是删除方括号或将它们变成括号的问题：
list(set(d['key'] for d in my_list))
或者，更简单（使用 Python 2.7 或更高版本），只需使用集合推导而不是列表推导直接构造集合：
list({d['key'] for d in my_list})
如果您坚持使用 Python 2.3 或更早版本，则必须编写显式循环。在 2.2 或更早版本中，没有集合，因此您必须使用将每个键映射到None或类似的 dict 来伪造它。
超越空间，时间呢？好吧，显然您必须遍历 10000 个字典的整个列表，并dict.get为每个字典执行 O(1)。
原始版本list.append对每个步骤执行一个（实际上是稍微快一点的内部等效），然后set转换是遍历相同大小的列表，set.add每个列表都有一个，然后list转换是遍历较小的集合每个人都有一个list.append。所以，它是 O(N)，这在算法上显然是最优的，而且比仅仅迭代列表并且什么都不做更糟糕的是乘数较小。
set 版本跳过list.appends，并且只迭代一次而不是两次。所以，它也是 O(N)，但乘数更小。内存管理的节省（如果 N 足够大的话）也可能有所帮助。
于 2013-09-24T01:02:53.767 回答