使用字典元组键的最后两个元素求和

Question

我有列表

A = [(i,j,k,l,m)]
B = [(l,m,k)]

和字典

C = {(i,j,k,l,m): val}
D = {(l,m,k): other_val}

我想创建一个 E 的字典，这样

E = {(i,j,k): C[(i,j,k,l,m)]*D[(l,m,k)]}

假定列表和词典中的所有索引约定都匹配。我有以下非 Pythonic 的、非常慢的解决方案。对于非常大的 A 大小，例如 500 万行，是否有任何 Pythonic 方法可以快速执行此操作？

E = {}
for i,j,k,l,m in A:
    E[i,j,k] = sum(
        C[i,j,k,l,m] * D[l2,m2,k2] 
        for l2,m2,k2 in B if l2==l and m2==m and k2==k)

下面是生成样本数据集的代码，该数据集接近要处理的实际大小。

import numpy as np
np.random.seed(1)

Irange = range(50)
Jrange = range(10)
Krange = range(80)
Lrange = range(8)
Mrange = range(18)

A = [
    (i,j,k,l,m)
    for i in Irange
    for j in Jrange
    for k in Krange
    for l in Lrange
    for m in Mrange]
B = [
    (l,m,k)
    for k in Krange
    for l in Lrange
    for m in Mrange]

C = {key: np.random.uniform(1,10) for key in A}

D = {key: np.random.uniform(0,1) for key in B}

E = {}
for i,j,k,l,m in A:
    E[i,j,k] = sum(
        C[i,j,k,l,m] * D[l2,m2,k2]
        for l2,m2,k2 in B if l2==l and m2==m and k2==k)

Answer 1

D 与 B 具有相同的键，那么为什么要遍历 B 并对一个元素求和？直接获取D[l,m,k]即可。

E[i,j,k] = C[i,j,k,l,m] * D[l,m,k]

转换为听写理解：

E = {(i,j,k): C[i,j,k,l,m]*D[l,m,k] for i,j,k,l,m in A}

在我的电脑上，这提供了大约 150 倍的加速（15s → 0.086s），但为了实用，我将你所有的输入尺寸减半，因为你的原始代码运行了超过一分钟而没有产生任何输出。

Answer 2

from collections import defaultdict

b = set(B)  # O(#B)
E = defaultdict(float)
for i,j,k,l,m in A: # O(#A)
    if (l, m, k) in b:
        E[i,j,k] += C[i,j,k,l,m] * D[l, m, k]

这种方法 O(#A + #B) 复杂。撇开正确性问题不谈，天真的实现是 O(#A * #B).

Answer 3

我正在发布我足够快的解决方案。如果您仍然看到改进的可能性，我很乐意对其进行测试。（我期待一些图书馆已经有一个更快的解决方案；也许，有，但我的 question/solution 方法不够清晰，无法使用一个）。

这里是数据生成代码：

import numpy as np
from datetime import datetime
np.random.seed(1)

Irange = range(50)
Jrange = range(10)
Krange = range(80)
Lrange = range(8)
Mrange = range(18)

A = [
    (i,j,k,l,m)
    for i in Irange
    for j in Jrange
    for k in Krange
    for l in Lrange
    for m in Mrange]
B = [
    (l,m,k)
    for k in Krange
    for l in Lrange
    for m in Mrange]

C = {key: np.random.uniform(1,10) for key in A}

D = {key: np.random.uniform(0,1) for key in B}

首先启动定时器，引入一个列表unique_ijk:

start_timer = datetime.now() #Start counting time
unique_ijk = list(set([(i,j,k) for i,j,k,l,m in A]))

然后，创建一个名为 lm_given_ijk 的字典，它使用对应于给定 i、j、k 元组键的 l、m 索引列表进行赋值。

lm_given_ijk = {(i,j,k):[] for i,j,k in unique_ijk}
for i,j,k,l,m in A:
    lm_given_ijk[i,j,k].append((l,m))

最后使用lm_given_ijk如下创建E.

E = {(i,j,k): sum(C[i,j,k,l,m]*D[l,m,k] for l,m in lm_given_ijk[i,j,k]) 
                  for i,j,k in unique_ijk}
print("Elapsed time is %s seconds.\n"%(datetime.now()-start_timer).total_seconds())

输出：

Elapsed time is 6.446798 seconds.

写下所有这些，我同意评论说这是一个 numpy 数组的东西。它可以提高速度，但我对 6.4 秒感到满意。

使用字典元组键的最后两个元素求和

Sum using the last two elements of a dictionary's tupled key

python

sum