代码之家 › 专栏 › 技术社区 › Andrew Ingram

在python中以最快的方式按键添加dict列表

dictionary python

Andrew Ingram · 技术社区 · 15 年前

比如说我有一堆字典

a = {'x': 1.0, 'y': 0.5, 'z': 0.25 }
b = {'w': 0.5, 'x': 0.2 }

只有两个,但问题是关于一个任意的数额。

找到每个键的平均值的最快方法是什么?听写是相当稀疏的,所以会有很多情况下,许多键不存在于各种听写中。

我要找的是一本新字典,里面有所有的键和每个键的平均值。值总是浮动的,我很高兴使用cTypes。我使用的方法比我想要的慢,可能是因为在我的例子中,我使用的是defaultdict,这意味着我实际上正在初始化值,即使它们不存在。如果这是我乐于重构的缓慢的原因,只想确保我没有遗漏任何明显的东西。

编辑:我认为我误导了结果应该是什么,如果值不存在,那么它应该是0.0,所以上面例子的结果是:

{'w':0.25,'x':0.6,'y':0.25,'z':0.125}

所以除法是按唯一键的总数。

我想知道的主要问题是,是否有一种秘密的方法可以在一步中用长度来划分整个dict,或者在一步中做加法。基本上是一个非常快速的向量加和除。我简单地看了一下numpy数组,但它们似乎不适用于dict,如果我将dict转换为list,就必须删除spargeness属性(显式地将缺少的值设置为0)。

6 回复 | 直到 15 年前

Kenan Banks 15 年前

通过分析可以证明这不是最快的,但是…

import collections

a = {'x': 1.0, 'y': 0.5, 'z': 0.25 }
b = {'w': 0.5, 'x': 0.2 }
dicts = [a,b]

totals = collections.defaultdict(list)
avg = {}

for D in dicts:
    for key,value in D.iteritems():
        totals[key].append(value)

for key,values in totals.iteritems():
   avg[key] = sum(values) / len(values)

我是猜测允许python使用内置的 sum() 和 len() 当你看到新的值时,在计算平均值时会得到一些性能,但是我肯定会错的。

Ned Batchelder 15 年前

这工作:

import collections

data= [
    {'x': 1.0, 'y': 0.5, 'z': 0.25 },
    {'w': 0.5, 'x': 0.2 }
    ]

tally = collections.defaultdict(lambda: (0.0, 0))

for d in data:
    for k,v in d.items():
        sum, count = tally[k]
        tally[k] = (sum+v, count+1)

results = {}
for k, v in tally.items():
    t = tally[k]
    results[k] = t[0]/t[1]

print results

我不知道它是否比你的快,因为你还没有发布你的代码。

{'y': 0.5, 'x': 0.59999999999999998, 'z': 0.25, 'w': 0.5}

我试着在Tally中避免再次存储所有的值,只需累加和,然后在最后计算平均值。通常,python程序的时间瓶颈在内存分配器中,使用较少的内存可以大大提高速度。

John Kugelman Michael Hodel 15 年前

>>> def avg(items):
...     return sum(items) / len(items)
... 
>>> hashes = [a, b]
>>> dict([(k, avg([h.get(k) or 0 for h in hashes])) for k in set(sum((h.keys() for h in hashes), []))])
{'y': 0.25, 'x': 0.59999999999999998, 'z': 0.125, 'w': 0.25}

说明:

所有散列中的一组键,不重复。

set(sum((h.keys() for h in hashes), []))

上述集合中每个键的平均值,如果该值在特定哈希中不存在,则使用0。
```
(k, avg([h.get(k) or 0 for h in hashes]))
```

David Berger 15 年前

您的瓶颈可能是由于过度使用内存造成的。考虑使用iteritems来利用发电机的功率。

因为你说你的数据是稀疏的,这可能不是最有效的。考虑迭代器的这种替代用法:

dicts = ... #Assume this is your dataset
totals = {}
lengths = {}
means = {}
for d in dicts:
    for key,value in d.iteritems():
        totals.setdefault(key,0)
        lengths.setdefault(key,0)
        totals[key] += value
        length[key] += 1
for key,value in totals.iteritems():
    means[key] = value / lengths[key]

这里,总计、长度和平均值是您创建的唯一数据结构。这应该是相当快的,因为它避免了创建辅助列表,并且每个字典包含的每个键只循环一次。

下面是第二种方法,我怀疑它会比第一种方法在性能上有所改进,但理论上它可以,这取决于您的数据和机器,因为它将需要更少的内存分配:

dicts = ... #Assume this is your dataset
key_set = Set([])
for d in dicts: key_set.update(d.keys())
means = {}
def get_total(dicts, key):
    vals = (dict[key] for dict in dicts if dict.has_key(key))
    return sum(vals)
def get_length(dicts, key):
    vals = (1 for dict in dicts if dict.has_key(key))
    return sum(vals)
def get_mean(dicts,key):
    return get_total(dicts,key)/get_length(dicts,key)
for key in key_set:
    means[key] = get_mean(dicts,key)

对于每个键,您确实会循环遍历所有字典两次,但除了键集之外,不需要任何中间数据结构。

Alex Martelli 15 年前

scipy.sparse 支持稀疏矩阵 dok_matrix 窗体似乎非常适合您的需要(不过,您必须使用整数坐标,因此需要单独的过程来收集并以任意但确定的顺序排列当前的字符串键)。如果有大量非常大且稀疏的“数组”,那么性能的提高可能值得复杂化。

Steve Losh 15 年前

这很简单,但可以做到:

a = { 'x': 1.0, 'y': 0.5, 'z': 0.25 }
b = { 'w': 0.5, 'x': 0.2 }

ds = [a, b]
result = {}

for d in ds:
    for k, v in d.iteritems():
        result[k] = v + result.get(k, 0)

n = len(ds)
result = dict((k, amt/n) for k, amt in result.iteritems())

print result

我不知道它与你的方法相比,因为你没有发布任何代码。