Python: Tổng giá trị của từ điển ba lớp

Question

Cho từ điển có ba lớp khóa, cách nhanh nhất để tổng hợp các giá trị là gì? Dưới đây là cách tiếp cận hiện tại của tôi:

from collections import defaultdict 

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ] 

def sum_three_deep_dict_values(dicts): 
    '''Read in two dicts and return a dictionary that contains their outer-joined keys and value sums''' 
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) 
    for d in dicts: 
     for w1, val_dict in d.iteritems():   
      for w2 in val_dict.iterkeys():    
       for w3 in val_dict[w2].iterkeys(): 
        combined[w1][w2][w3] += d[w1][w2][w3] 
    return combined 

print sum_three_deep_dict_values(dicts) 

đây sản lượng dự kiến ​​là {'a': {'b': {'c': 5, 'e': 3}}} Mục đích là để tổng hợp các giá trị mà hai cuốn từ điển có các phím tương tự (ví dụ như d[a][b][c] đây) và bao gồm các cặp giá trị key còn lại từ một trong hai từ điển trong từ điển đầu ra.

Có một số câu hỏi về SO xuất hiện để trả lời câu hỏi: "Làm cách nào để tổng hợp giá trị của từ điển lồng nhau"? Tuy nhiên, đọc qua chúng tối qua, mọi thứ tôi tìm thấy liên quan đến một số trường hợp đặc biệt lạ hoặc tham số, như "kết hợp/bỏ qua lớp khóa thứ n" hoặc "áp dụng điều kiện nếu ở vị trí đặc biệt". Do đó, tôi muốn nêu ra câu hỏi đơn giản: Cách tốt nhất để tổng hợp các giá trị của từ điển lồng nhau đôi trong Python là gì?

Answer 1

Tôi nghĩ cách tiếp cận hiện tại của bạn nói chung là một cách tốt nhất. Đề xuất của tôi là loại bỏ càng nhiều tra cứu từ điển càng tốt. Lặp lại các khóa và giá trị với nhau phải nhanh bằng cách lặp qua các phím, vì vậy bạn cũng có thể kết hợp chúng với nhau. Và cuộc gọi cuối cùng đến d[w1][w2][w3] là không cần thiết nếu bạn làm điều đó, cũng không phải là tra cứu khóa tạm thời. Vì vậy, một cái gì đó như thế này:

def sum_three_deep_dict_values(dicts): 
    '''Read in two dicts and return a dictionary that contains 
     their outer-joined keys and value sums''' 
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) 
    for layer0 in dicts: 
     for k1, layer1 in layer0.iteritems(): 
      for k2, layer2 in layer1.iteritems(): 
       for k3, count in layer2.iteritems(): 
        combined[k1][k2][k3] += count 
    return combined 

Tôi đã tự do thay đổi sơ đồ tên của bạn một chút.

Nếu bạn vẫn lo lắng về tốc độ sau khi thử nghiệm ở trên, bạn có thể cần xem xét các cấu trúc dữ liệu khác hoặc thư viện của bên thứ ba. Nhưng trước khi bạn làm điều đó, hãy thử PyPy - Tôi thấy nó thường mang lại ít nhất một tốc độ 4x trên các vòng vanilla for.

Ngoài ra, hãy kiểm tra điều này với mã ban đầu của bạn. Tôi nghĩ rằng lý do của tôi ở trên nắm giữ, nhưng nó vẫn còn một chút phỏng đoán. Tôi cũng tò mò về đề xuất của người khác. Ở quy mô bạn đang làm việc, đây có thể là một thách thức! (Out of curiosity, bao lâu là này đưa bạn với mã hiện tại của bạn?)

UPDATE: Tôi đã thử nghiệm này và nó thực sự nhanh hơn, mặc dù chỉ bằng một sợi tóc:

>>> %timeit sum_three_deep_original(dicts) 
1000 loops, best of 3: 1.38 ms per loop 
>>> %timeit sum_three_deep_edited(dicts) 
1000 loops, best of 3: 1.26 ms per loop 

Tôi đoán bạn cần thêm tốc độ cho ứng dụng của bạn. Tôi đã thử nó với PyPy, và tôi cũng biên dịch nó bằng cách sử dụng cython (nhưng không có bất kỳ sửa đổi hoặc loại chú thích). PyPy thắng với tốc độ tăng 66%. python Plain một lần nữa (với các thông số hơi khác nhau thời gian này):

:~ $ python -c 'from tdsum import test; test()' 
1.63905096054 

Biên soạn với cython:

:~ $ python -c 'from tdsum import test; test()' 
1.224848032 

Và sử dụng PyPy:

:~ $ pypy -c 'from tdsum import test; test()' 
0.427165031433 

Tôi mong chờ một phiên bản cython thực sử dụng một cấu trúc dữ liệu được xây dựng tùy chỉnh để làm tốt hơn đáng kể PyPy. Vấn đề là bạn không thể sử dụng dict s và vẫn nhận được tốc độ lặp lại mà bạn muốn, bởi vì cython phải muck về với chi phí đối tượng Python. Vì vậy, bạn sẽ phải thực hiện bảng băm của riêng bạn!

Tôi thường tự hỏi tại sao cython không cung cấp giải pháp cho vấn đề này; có lẽ có một loại numpy có thể sử dụng được. Tôi sẽ tiếp tục tìm kiếm!

Answer 2

Đây là giải pháp sử dụng chức năng làm phẳng và chức năng phun lên, đối với các vấn đề lồng nhau sâu tùy ý. Hoạt động cho bạn nhập nhưng không thử nghiệm nhiều hơn nữa:

from collections import Counter 

def flatten(d, parent=None): 
    for k, v in d.items(): 
     keys = (k,) if parent is None else parent + (k,) 
     if isinstance(v, dict): 
      yield from flatten(v, keys) 
     else: 
      yield keys, v 

def puffup(c): 
    top = {} 
    for k, v in c.items(): 
     current = top # reset walk 
     for ki in k[:-1]: 
      if ki not in current: 
       current[ki] = {} 
     current[k[-1]] = v 
    return top 

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ] 
c = Counter() 
for d in dicts: 
    c += dict(flatten(d)) 
print(puffup(c)) 
# {'a': {'b': {'c': 5, 'e': 3}}} 

Tôi vừa thấy bạn đang tìm kiếm nhanh nhất. Mặc dù linh hoạt hơn nhiều, điều này là ~ 2.5x chậm hơn so với câu trả lời ở trên, mà không cần cắt giảm với đầu vào nhiều ở tất cả.