Python使用hash tables/dictionaries统计账本账户对交易总额

我手头有一份大型交易列表，需要汇总统计每一对转出账户到转入账户之间的转账总金额。

输入示例 #

sources = ['A','A','A','A','A','B','B','B','B']
targets = ['C','C','C','D','D','C','C','D','D']
values =  [ 2 , 1 , 2 , 2 , 3 , 2 , 3 , 2 , 3 ]

期望输出 #

sources = ['A','A','B','B']
targets = ['C','D','C','D']
totals =  [ 5 , 5 , 5 , 5 ]

原有实现 #

目前通过带索引的嵌套for循环实现需求，代码如下：

#Create a list of unique pairs
pairs = [[sources[0],targets[0]]]
for idx, x in enumerate(sources):
    temp_pair = [sources[idx],targets[idx]]
    new_pair = True
    for pair in pairs:
        if temp_pair == pair:
            new_pair = False
    if new_pair == True:
        pairs.append(temp_pair)
print(pairs)

#Define an empty totals list based on pairs list
totals = []
for pair in pairs:
    totals.append([pair[0],pair[1],0])
print(totals)

# Fill the totals list with values
for idx, x in enumerate(sources):
    for idy, pair in enumerate(pairs):
        if [pair[0],pair[1]] == [sources[idx],targets[idx]]:
            totals[idy][2] += values[idx]
print(totals)

原有代码运行结果：

咨询需求 #

如何通过哈希表（字典）实现相同的统计需求，替代低效的嵌套循环逻辑。

用(转出账户, 转入账户)的元组作为字典键，对应值存储该转账路径的累计金额即可，仅需单次遍历就能完成统计，时间复杂度从原有嵌套循环的O(n²) 降到O(n)，处理大型交易列表时效率提升非常明显。

最简实现（推荐） #

借助collections.defaultdict省去键存在性判断的逻辑：

from collections import defaultdict

pair_total = defaultdict(int)
# 直接并行遍历三个列表，无需手动取索引
for s, t, v in zip(sources, targets, values):
    pair_total[(s, t)] += v

# 拆分为要求的三个独立列表
sources_res = [k[0] for k in pair_total.keys()]
targets_res = [k[1] for k in pair_total.keys()]
totals_res = list(pair_total.values())

无依赖普通字典实现 #

如果不想导入标准库模块，用原生字典也可以实现：

pair_total = {}
for s, t, v in zip(sources, targets, values):
    key = (s, t)
    if key not in pair_total:
        pair_total[key] = 0
    pair_total[key] += v

# 结果拆分逻辑和上面完全一致
sources_res = [k[0] for k in pair_total.keys()]
targets_res = [k[1] for k in pair_total.keys()]
totals_res = list(pair_total.values())

运行上述代码得到的结果和期望输出完全匹配：

print(sources_res) # ['A', 'A', 'B', 'B']
print(targets_res) # ['C', 'D', 'C', 'D']
print(totals_res)  # [5, 5, 5, 5]

注意：Python 3.7及以上版本的字典默认保留插入顺序，最终输出的转账对顺序和交易中该配对首次出现的顺序一致，和原有循环实现的输出顺序完全匹配。如果使用更低版本Python，可以替换为collections.OrderedDict保证顺序一致。

内容的提问来源于stack exchange，提问作者sundialer