从pythondi获得第一次出现唯一的更有效方法

Question

我有一个非常大的文件，我正在分析并从行中获取键值。我只需要第一个键和值，只需要一个值。也就是说，我要删除重复的值

看起来是这样的：

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

它会输出：

^{pr2}$

这有点令人困惑，因为我不在乎钥匙是什么。所以上面的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])

每次都必须查看值持有人：（有没有更快的方法？在

Answer 1

是的，一个小小的改变会让它更快：

value_holder = set()

（好吧，您还必须将append更改为add。但还是很简单。）

查找是一个（O）集合，而不是一个（O）操作，而不是一个（O）集合。换句话说，如果您有10000行，那么您将执行10000个哈希查找，而不是50000000个比较。在

这个解决方案和其他所有已发布的解决方案的一个警告是，它要求值是散列的。如果它们不可散列，但它们是可比较的，那么仍然可以通过使用排序集（例如，从^{}库）获得O（NlogN）而不是O（N^2）。如果它们既不是散列的也不是可排序的……那么，您可能需要找到一些方法来生成一些可散列（或可排序）的内容，用作“第一次检查”，然后只对“first check”匹配进行实际匹配，这将使您得到O（NM），其中M是哈希碰撞的平均数。在

您可能想看看unique_everseen是如何在标准库文档的^{} recipes中实现的。在

请注意，字典实际上没有顺序，因此无法选择“第一个”副本；您只能随意获取一个。在这种情况下，还有另一种方法：

^{pr2}$

（这实际上是decorate-process-undecorate习语的一种形式，无需任何处理。）

但是，与其建立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 recipes，看看是否有人已经为您编写过），这样您就可以编写：

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

Answer 2

我不太清楚您到底在做什么，但是set是删除重复项的好方法。例如：

>>> k = [1,3,4,4,5,4,3,2,2,3,3,4,5]
>>> set(k)
set([1, 2, 3, 4, 5])
>>> list(set(k))
[1, 2, 3, 4, 5]

尽管它有点依赖于您正在加载的输入的结构，但是可能有一种方法可以简单地使用set，这样您就不必每次迭代整个对象来查看是否有匹配的键——而是运行一次set。在

Answer 3

正如其他人所提到的，加快速度的第一种方法是使用set来记录所看到的值，因为检查集合的成员资格要快得多。在

我们也可以用dict comprehension将其缩短：

seen = set()
new_mapp = {k: v for k, v in mapp.items() if v not in seen or seen.add(i)}

if的情况需要一点解释：我们只在以前没有看到过值的地方添加键/值对，但是我们有点粗俗地使用or来确保将任何未看到的值添加到集合中。由于set.add()返回{}，因此它不会影响结果。在

一如既往，在2.x中，用户dict.iteritems()超过dict.items()。在