3

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

所以它看起来像：

{
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 :( 有没有更快的方法来做到这一点？

4

6 回答 6

6

是的，一个微不足道的改变使它更快：

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()}

（这实际上是一种没有任何处理的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 配方以查看是否有人已经为您编写了它），那么您可以编写：

mapp = one_to_one_dict()
for line in f:
    k, v = line.split(None, 1)
    mapp[k] = v
于 2012-12-27T22:59:12.490 回答
2

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

我们还可以使用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()回报None，它不会影响结果。

与往常一样，在 2.x 中，用户dict.iteritems()超过dict.items().

于 2012-12-27T23:24:01.933 回答
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一次。

于 2012-12-27T22:59:30.483 回答
0

使用 aset而不是 alist会大大加快你的速度......

于 2012-12-27T22:59:38.580 回答
-1

您的部分问题是 dicts 在迭代时不保留任何类型的逻辑顺序。他们使用哈希表来索引项目（参见这篇很棒的文章）。所以在这种数据结构中没有真正的“价值首次出现”的概念。这样做的正确方法可能是键值对列表。例如：

kv_pairs = [(k1,v1),(k2,v2),...]

或者，因为文件太大，最好使用 python 提供的优秀文件迭代来检索 k/v 对：

def kv_iter(f):
    # f being the file descriptor
    for line in f:
        yield ... # (whatever logic you use to get k, v values from a line)

Value_holder 是集合变量的绝佳候选者。您实际上只是在测试 value_holder. 因为值是唯一的，所以可以使用类似的散列方法更有效地对它们进行索引。所以它最终会有点像这样：

mapp = {}
value_holder = set()

for k,v in kv_iter(f):
    if v in value_holder:
       mapp[k] = v
       value_holder.add(v)
于 2012-12-27T23:44:39.943 回答
-1

您说您正在读取一个非常大的文件，并且只想保留第一次出现的键。我最初认为这意味着您关心键/值对在非常大的文件中出现的顺序。这段代码会做到这一点并且会很快。

values_seen = set()
mapp = {}
with open("large_file.txt") as f:
    for line in f:
        key, value = line.split()
        if value not in values_seen:
            values_seen.add(value)
            mapp[key] = value

您正在使用 alist来跟踪您的代码看到的键。搜索 alist非常慢：列表越大，它就越慢。Aset快得多，因为查找接近于恒定时间（不会变得更慢，或者可能根本更慢，列表越大）。（Adict也以 a 的方式set工作。）

于 2012-12-27T22:59:54.007 回答