가장 빠른 방법으로 키가 많다는 함께 파이썬

Question

에 dicts의 목록을 추가 내가 거기에 두 가지의 사전

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

의 무리를 말하지만, 문제는 인해 임의 양에 관한됩니다.

각 키의 평균값을 찾는 가장 빠른 방법은 무엇입니까? dicts는 매우 희소하기 때문에 많은 dicts에 많은 키가 존재하지 않는 경우가 많이있을 것입니다.

내가 찾고있는 결과는 모든 키와 각각에 대한 평균값을 가진 새 사전입니다. 값은 항상 부동입니다, 나는 ctypes에 담글 수있어서 기쁩니다. 내가 가지고있는 접근 방식은 내가 원했던 것보다 느리다. 왜냐하면 아마도 나의 경우 defaultdicts를 사용하고 있는데, 이는 그들이 실제로 존재하지 않더라도 실제로 값을 초기화한다는 것을 의미하기 때문이다. 이것이 저속의 원인이라면 나는 리팩토링하는 것을 기쁘게 생각합니다. 나는 명백한 것을 놓치지 않고 있는지 확인하고 싶습니다.

편집 : 나는 값이 0.0로 작동한다없는 경우 나, 결과가 있어야한다 무엇에 오해의 소지가되었다고 생각하기 때문에 위의 예에 대한 결과는 다음과 같습니다

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

그래서를 division은 총 고유 키 수입니다.

내가 궁금해하는 주요한 점은 한 문장으로 전체 문장을 길이로 나눌 수있는 방법이나 한 걸음 더하기를하는 것입니다. 기본적으로 매우 빠른 벡터 추가 및 나누기. 난 numpy 배열을 간단히 살펴 봤지만 그들은 dicts에 적용하지 않는 것 같아요. 그리고 목록에 딕테이션을 변환한다면 (희박한 값을 0으로 명시함으로써) 희소성 속성을 제거해야 할 것입니다.

Answer 1

...이 꽤 빠른 아니라고 프로파일 링을 통해 입증 될 수 있지만 내가 이을 추측하고있어

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) 

그 파이썬은 sum()와 len()가가는 내장 기능을 사용할 수 있도록 새로운 가치를 보면서 평균을 계산하는 것보다 약간의 성과를 얻지 만, 나는 그것에 대해 틀리게 생각할 수 있습니다.

Answer 2

이 작동 :

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} 

나는 다시 모든 값을 저장 단순히 합계를 축적하고 내가 마지막에 평균을 계산해야 할 것 계산 피하기 위해 집계에 노력했다. 종종 Python 프로그램의 병목 현상은 메모리 할당 자에 있고, 메모리를 적게 사용하면 속도가 빨라집니다.

Answer 3

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

설명 : 해시, 반복없이 모두에서 키

1. 세트입니다.

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

2. 값이 특정 해시에없는 경우 0을 이용하여 상기 세트 내의 각각의 키의 평균값.과도한 메모리 사용에

   (k, avg([h.get(k) or 0 for h in hashes])) 
   

Answer 4

당신의 병목 현상이있을 가능성이 . 발전기의 힘을 활용하기 위해 iteritem을 사용하는 것을 고려하십시오.

데이터가 희박하다고 말하면 아마도 가장 효율적이지 않을 것입니다.

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) 

: 덜 메모리 할당을 필요로하기 때문에, 데이터 및 시스템에 따라 다음

는 내가 처음을 통해 성능이 향상 될 것입니다 의심 두 번째 접근 방식, 그러나 그것은 이론적으로 수 모든 사전에 대해 각 키에 대해 두 번 반복되지만 key_set 이외의 중간 데이터 구조는 필요하지 않습니다.

Answer 5

scipy.sparse은 희소 행렬을 지원합니다. - dok_matrix 형식은 사용자의 요구에 적합하다고 생각됩니다 (정수 좌표를 사용해야하기 때문에 임의의 특정 순서로 수집하고 넣기 위해 별도의 단계가 필요합니다. 현재 가지고있는 키). 매우 크고 드문 드문 "어레이"가 많은 경우 성능이 향상 될 수 있습니다.

Answer 6

그것은 간단하지만이 일할 수 :

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 

난 당신이 코드를 게시하지 않았기 때문에 그것은 당신의 방법과 비교하는 방법을 모른다.