从Python dict获得独特的第一次出现的更有效方法

value_holder = set()

(好吧,你还必须改变追加添加.但还是很简单.)

使用集合而不是列表意味着每个查找都是O(1)而不是O(N),因此整个操作是O(N)而不是O(N ^ 2).换句话说,如果您有10,000行,那么您将进行10,000次哈希查找而不是50,000,000次比较.

这个解决方案的一个警告 – 以及所有其他发布的 – 是它要求值可以清除.如果它们不可清洗,但它们具有可比性,您仍然可以通过使用排序集(例如,来自blist库)获得O(NlogN)而不是O(N ^ 2).如果它们既不可清洗也不可排序……好吧,你可能想找到一些方法来生成可用的(或可排序的)用作“第一次检查”的东西,然后只用于实际匹配的“第一次检查”匹配,它将到达O(NM),其中M是散列冲突的平均数量.

您可能希望了解标准库文档中itertools recipes中unique_everseen的实现方式.

请注意,字典实际上没有订单,所以没有办法选择“第一”副本;你会随意得到一个.在这种情况下,还有另一种方法：

inverted = {v:k for k,v in d.iteritems()}
reverted = {v:k for k,v in inverted.iteritems()}

(这实际上是decorate-process-undecorate成语的一种形式,没有任何处理.)

但是,不是建立dict然后过滤它,你可以通过在阅读时过滤来使事情变得更好(更简单,更快,更节省内存,并保持秩序).基本上,随着时间的推移,将套装放在字典旁边.例如,而不是这样：

mydict = {}
for line in f:
    k,v = line.split(None,1)
    mydict[k] = v

mapp = {}
value_holder = set()

for i in mydict:
    if mydict[i] not in value_holder:
        mapp[i] = mydict[i]
        value_holder.add(mydict[i])

这样做：

mapp = {}
value_holder = set()
for line in f:
    k,1)
    if v not in value_holder:
        mapp[k] = v
        value_holder.add(v)

实际上,您可能需要考虑编写一个包含它的one_to_one_dict(或者搜索PyPI模块和ActiveState配方以查看是否有人已经为您编写了它),那么您可以编写：

mapp = one_to_one_dict()
for line in f:
    k,1)
    mapp[k] = v