如何构建一个高效的函数来计算多深度嵌套字典中特定元素的百分比？

Question

我有一个DataFrame如下:

source =
HM    IM    Ratio 
A     B     50%
A     C     20%
A     D     30% 
E     B     40%
E     C     20%
E     F     40%
H     C     50%
H     E     10%
H     G     40%
G     B     80% 
G     D     10%
J     B     10%
J     H     80%
J     X     5%
J     E     5%

我想知道在"HM"列中的每个项目，它占总"C"的百分比是多少，例如:

总C % ' H ' = 50% (C) + 10% (E) * 20% (C)

= 52%我使用递归构建一个函数，如下所示:

root = ['C']
BPB = []
BPB_ratio = {}
def spB(mat,root,ratio,level,lay):
items = source.loc[source['HM']==mat,'IM'].tolist()
for item in items:
items_item = source.loc[source['HM']==item,'IM'].tolist()
item_ratio = source.loc[(source['HM']==mat)&(source['IM']==item),'Ratio'].tolist()[0]
BPB.append([level,item,ratio*item_ratio])
if item in root:
BPB_ratio[level] =+ ratio*item_ratio
continue
if len(items_item)==0:
continue
else:
nlevel = level + 1
spB(item,root,ratio*item_ratio,nlevel,lay)
if lay == 0:
return sum(BPB_ratio.values())
else:
return BPB_ratio[lay]
for ss in list(set(source['HM'].tolist())):
percent = spB(ss,root,1,0,0)
print(BPB_ratio)

它可以给我正确的结果;但是，它的效率太慢....我有一个有近60,000行的源DataFrame。遍历整个数据帧将花费非常长的时间来给出结果。我想知道是否有比使用递归更好的解决方案?

Answer 1

我会尝试在数据框架上使用merge，而不是使用递归。

首先，我将定义一个函数，通过一个中间步骤从数据框架中计算路径:

def onestep(df):
df2 = df.merge(df, left_on='IM', right_on='HM')
df2['Ratio'] = df2['Ratio_x'] * df2['Ratio_y']    # compute resulting ratio
# only keep relevant columns and rename them
df2 = df2[['HM_x', 'IM_y', 'Ratio']].rename(
columns={'HM_x': 'HM', 'IM_y': 'IM'})
# sum up paths with same origin and destination
return df2.groupby(['HM', 'IM']).sum().reset_index()

从你方样品中，我们可以看到:

>>> onestep(df)
HM IM  Ratio
0  H  B   0.36
1  H  C   0.02
2  H  D   0.04
3  H  F   0.04
4  J  B   0.02
5  J  C   0.41
6  J  E   0.08
7  J  F   0.02
8  J  G   0.32

我们正确地得到H->C(通过E)在2%

然后我会尝试迭代一步，直到结果数据帧为空(或达到最大深度)，最后组合所有内容:

dfs = [df]
temp=df
n = 10               # give up at depth 10 (adapt it to your actual use case)
for i in range(n):
temp = onestep(temp)
if (len(temp) == 0):    # break when the df is empty
break
dfs.append(temp)
else:
# we gave up before exploring all the paths: warn user
print(f"BEWARE: exiting after {n} steps")
resul = pd.concat(dfs, ignore_index=True).groupby(
['HM', 'IM']).sum().reset_index()

对于您的示例数据，它给出(步骤2的迭代给出了一个空数据框):

HM IM  Ratio
0   A  B   0.50
1   A  C   0.20
2   A  D   0.30
3   E  B   0.40
4   E  C   0.20
5   E  F   0.40
6   G  B   0.80
7   G  D   0.10
8   H  B   0.36
9   H  C   0.52
10  H  D   0.04
11  H  E   0.10
12  H  F   0.04
13  H  G   0.40
14  J  B   0.12
15  J  C   0.41
16  J  E   0.13
17  J  F   0.02
18  J  G   0.32
19  J  H   0.80
20  J  X   0.05

我们正确地发现H->C在52%

---

我不能确定在大数据帧上的实际效率，因为这将取决于实际的图形复杂性…