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

Question

我有一个非常大的文件,我正在解析并从该行获取键值.我只想要第一个键和值,只有一个值.也就是说,我正在删除重复的值

所以它看起来像:

{
A:1
B:2
C:3
D:2
E:2
F:3
G:1
}

它会输出:

{E:2,F:3,G:1}

这有点让人困惑,因为我并不在乎关键是什么.所以上面的E可以用B或D代替,F可以用C代替,G可以用A.代替.

这是我发现的最佳方法,但随着文件变大,速度非常慢.

mapp = {}
value_holder = []

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

每次都必须通过value_holder查看:(有更快的方法吗？

Answer 1

是的,一个微不足道的变化使它更快:

value_holder = set()

(嗯,你也必须改变append到add,但还是蛮简单的.)

使用集合而不是列表意味着每个查找都是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是散列冲突的平均数量.

您可能希望了解标准库文档unique_everseen中的itertools配方是如何实现的.

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

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

(这实际上是装饰过程 - 未装饰成语的一种形式,没有任何处理.)

但是,不是构建dict然后过滤它,而是通过在阅读时进行过滤,使事情变得更好(更简单,更快,更节省内存,并保持顺序).基本上,保持set旁边的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, v = line.split(None, 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, v = line.split(None, 1)
    mapp[k] = v