使用 Pandas 和 Numpy 通过 ID 索引查找比率的昂贵计算时间
Expensive computation time with finding ratios by ID index using Pandas and Numpy
我目前正在制作一个 table,其中包含对的比率,应用了某种最小最大标量逻辑。但是,我的代码经历了非常长且昂贵的时间复杂度;一个重要的原因是数据的大小。但是,我正在寻找更有效的代码来做同样的事情。
这是我编写的代码,将解释我在代码中所做的事情。
import pandas as pd
import numpy as np
import itertools
indexColumn = 'id'
limit_ratio = 0.6
result_data = pd.DataFrame([['id1', 1], ['id2', 1], ['id3', 1], ['id1', 2], ['id3', 2], ['id1', 4], ['id2', 4], ['id1', 5], ['id2', 5], ['id1', 6], ['id5', 6], ['id5', 7], ['id6', 7]], columns=['id', 'labels'])
result_data = result_data.groupby('labels')[indexColumn].apply(lambda x: list(itertools.combinations(x, 2))).reset_index()
result_data = result_data.explode(indexColumn)
result_data = result_data.groupby(indexColumn)['labels'].agg('count').rename('count').reset_index()
result_data[['id1', 'id2']] = pd.DataFrame(result_data[indexColumn].tolist(),index=result_data.index)
此时,result_data
看起来像
id
count
id1
id2
(id1,id2)
3
id1
id2
(id1,id3)
2
id1
id3
(id1,id5)
1
id1
id5
(id2,id3)
1
id2
id3
(id5,id6)
1
id5
id6
基本上,上面的代码计算了一对具有相同标签的数量。
例如,id1
和 id2
具有标签 1 数据。然后,计数将增加 1。
(我特别要感谢 Joseph Fernandez,他曾帮助我完成上述代码)
result_data['ratio'] = result_data['count'] / float(result_data['count'].max())
result_data = result_data.sort_values(by='ratio', ascending=False)
那么,result_data
就是
id
count
id1
id2
ratio
(id1,id2)
3
id1
id2
1.000
(id1,id3)
2
id1
id3
0.667
(id1,id5)
1
id1
id5
0.333
(id2,id3)
1
id2
id3
0.333
(id5,id6)
1
id5
id6
0.333
对于这里的ratio
,我计算
- (id1, id2) = 3 / max(计数) = 3 / 3 = 1
- (id1, id3) = 2 / max(计数) = 2 / 3 = 0.667
- (id1, id5) = 1 / max(count) = 1 / 3 = 0.333
这是解释代码的简单数据版本,但此时我实际上有 result_data
,其中有 1.2 亿行。以下代码是我在指数计算时间上遇到的问题,因为它的大小。
if limit_ratio is not None:
result_data[['ratio1', 'ratio2']] = np.NaN
idlist = np.unique(result_data[['id1', 'id2']])
for id in idlist:
tmp = result_data[(result_data['id1'] == id) | (result_data['id2'] == id)][['id1', 'id2', 'count', 'ratio']]
tmp['ratio1'] = tmp['count'] / float(tmp['count'].max())
tmp['ratio2'] = tmp['ratio1']
tmp.loc[tmp['id1'] == id, ['ratio2']] = np.NaN
tmp.loc[tmp['id2'] == id, ['ratio1']] = np.NaN
tmp = tmp[['id1', 'id2', 'ratio1', 'ratio2']]
result_data = pd.merge(result_data, tmp, how='outer', on=['id1', 'id2'])
result_data['ratio1'] = result_data['ratio1_x'].where(result_data['ratio1_x'].notna(), result_data['ratio1_y'])
result_data['ratio2'] = result_data['ratio2_x'].where(result_data['ratio2_x'].notna(), result_data['ratio2_y'])
result_data = result_data[['id1', 'id2', 'count', 'ratio', 'ratio1', 'ratio2']]
那么,结果就是
id1
id2
count
ratio
ratio1
ratio2
id1
id2
3
1.000
1.000
1.0
id1
id3
2
0.667
0.667
1.0
id1
id5
1
0.333
0.333
1.0
id2
id3
1
0.333
0.333
0.5
id5
id6
1
0.333
1.000
1.0
要详细解释比率 1 和比率 2,
ratio1
由
计算
- (id1,id2) 计数/最大值(id1_count) = 3/3 = 1
- (id1,id3) 计数/最大值(id1_count) = 2/3 = 0.667
- (id1,id5) 计数/最大值(id1_count) = 1/3 = 0.333
- (id2,id3) 计数/最大值(id2_count) = 1/3 = 0.333
- (id5,id6) 计数/最大值(id5_count) = 1/1 = 1
ratio2
由
计算
- (id1,id2) 计数/最大值(id2_count) = 3/3 = 1
- (id1,id3) 计数/最大值(id3_count) = 2/2 = 1
- (id1,id5) 计数/最大值(id5_count) = 1/1 = 1
- (id2,id3) 计数/最大值(id3_count) = 1/2 = 0.5
- (id5,id6) 计数/最大值(id6_count) = 1/1 = 1
毕竟,我们的最终目标是过滤掉 threshold
.
的行
result_data = result_data[(result_data['ratio1'] >= float(limit_ratio)) | (result_data['ratio2'] >= float(limit_ratio))]
这会给我
id1
id2
count
ratio
ratio1
ratio2
id1
id2
3
1.000
1.000
1.0
id1
id3
2
0.667
0.667
1.0
id1
id5
1
0.333
0.333
1.0
id5
id6
1
0.333
1.000
1.0
在这里,代码每次循环需要 12 分钟。数据有 50,000 个唯一 ID,预计 12 * 50000 = 60,000 分钟 = 10,000 小时计算。供您参考,我目前使用的是 python 3.8.8、pandas == 1.2.3 和 numpy == 1.19.5.
设置
>>> result_data
id count id1 id2 ratio
0 (id1, id2) 3 id1 id2 1.000000
1 (id1, id3) 2 id1 id3 0.666667
2 (id1, id5) 1 id1 id5 0.333333
3 (id2, id3) 1 id2 id3 0.333333
4 (id5, id6) 1 id5 id6 0.333333
解决方案
melted = result_data.melt('count', ['id1', 'id2'])
maxima = melted.groupby('value')['count'].max()
result_data['ratio1'] = result_data['count'] / result_data['id1'].map(maxima)
result_data['ratio2'] = result_data['count'] / result_data['id2'].map(maxima)
result_data = result_data.query("ratio1 >= @limit_ratio or ratio2 >= @limit_ratio")
解释
Melt
通过指定 id_vars
为 count
和 value_vars
为 id1, id2
的数据帧
>>> melted
count variable value
0 3 id1 id1
1 2 id1 id1
2 1 id1 id1
3 1 id1 id2
4 1 id1 id5
5 3 id2 id2
6 2 id2 id3
7 1 id2 id5
8 1 id2 id3
9 1 id2 id6
现在 group
melted
数据帧由 value
列和聚合 count
使用 max
计算每个 maximum
计数值28=]
>>> maxima
value
id1 3
id2 3
id3 2
id5 1
id6 1
Name: count, dtype: int64
map
在 id1
和 id2
列上计算的 maxima
>>> result_data['id1'].map(maxima)
0 3
1 3
2 3
3 3
4 1
Name: id1, dtype: int64
>>> result_data['id1'].map(maxima)
0 3
1 2
2 1
3 2
4 1
Name: id2, dtype: int64
现在用上面映射的id1
和id2
列分别划分count
列来计算ratio1
和ratio2
>>> result_data[['ratio1', 'ratio2']]
ratio1 ratio2
0 1.000000 1.0
1 0.666667 1.0
2 0.333333 1.0
3 0.333333 0.5
4 1.000000 1.0
Query
根据 limit_ratio
中给定的 threshold
值过滤掉行的数据框
>>> result_data
id count id1 id2 ratio ratio1 ratio2
0 (id1, id2) 3 id1 id2 1.000000 1.000000 1.0
1 (id1, id3) 2 id1 id3 0.666667 0.666667 1.0
2 (id1, id5) 1 id1 id5 0.333333 0.333333 1.0
4 (id5, id6) 1 id5 id6 0.333333 1.000000 1.0
我目前正在制作一个 table,其中包含对的比率,应用了某种最小最大标量逻辑。但是,我的代码经历了非常长且昂贵的时间复杂度;一个重要的原因是数据的大小。但是,我正在寻找更有效的代码来做同样的事情。
这是我编写的代码,将解释我在代码中所做的事情。
import pandas as pd
import numpy as np
import itertools
indexColumn = 'id'
limit_ratio = 0.6
result_data = pd.DataFrame([['id1', 1], ['id2', 1], ['id3', 1], ['id1', 2], ['id3', 2], ['id1', 4], ['id2', 4], ['id1', 5], ['id2', 5], ['id1', 6], ['id5', 6], ['id5', 7], ['id6', 7]], columns=['id', 'labels'])
result_data = result_data.groupby('labels')[indexColumn].apply(lambda x: list(itertools.combinations(x, 2))).reset_index()
result_data = result_data.explode(indexColumn)
result_data = result_data.groupby(indexColumn)['labels'].agg('count').rename('count').reset_index()
result_data[['id1', 'id2']] = pd.DataFrame(result_data[indexColumn].tolist(),index=result_data.index)
此时,result_data
看起来像
id | count | id1 | id2 |
---|---|---|---|
(id1,id2) | 3 | id1 | id2 |
(id1,id3) | 2 | id1 | id3 |
(id1,id5) | 1 | id1 | id5 |
(id2,id3) | 1 | id2 | id3 |
(id5,id6) | 1 | id5 | id6 |
基本上,上面的代码计算了一对具有相同标签的数量。
例如,id1
和 id2
具有标签 1 数据。然后,计数将增加 1。
(我特别要感谢 Joseph Fernandez,他曾帮助我完成上述代码)
result_data['ratio'] = result_data['count'] / float(result_data['count'].max())
result_data = result_data.sort_values(by='ratio', ascending=False)
那么,result_data
就是
id | count | id1 | id2 | ratio |
---|---|---|---|---|
(id1,id2) | 3 | id1 | id2 | 1.000 |
(id1,id3) | 2 | id1 | id3 | 0.667 |
(id1,id5) | 1 | id1 | id5 | 0.333 |
(id2,id3) | 1 | id2 | id3 | 0.333 |
(id5,id6) | 1 | id5 | id6 | 0.333 |
对于这里的ratio
,我计算
- (id1, id2) = 3 / max(计数) = 3 / 3 = 1
- (id1, id3) = 2 / max(计数) = 2 / 3 = 0.667
- (id1, id5) = 1 / max(count) = 1 / 3 = 0.333
这是解释代码的简单数据版本,但此时我实际上有 result_data
,其中有 1.2 亿行。以下代码是我在指数计算时间上遇到的问题,因为它的大小。
if limit_ratio is not None:
result_data[['ratio1', 'ratio2']] = np.NaN
idlist = np.unique(result_data[['id1', 'id2']])
for id in idlist:
tmp = result_data[(result_data['id1'] == id) | (result_data['id2'] == id)][['id1', 'id2', 'count', 'ratio']]
tmp['ratio1'] = tmp['count'] / float(tmp['count'].max())
tmp['ratio2'] = tmp['ratio1']
tmp.loc[tmp['id1'] == id, ['ratio2']] = np.NaN
tmp.loc[tmp['id2'] == id, ['ratio1']] = np.NaN
tmp = tmp[['id1', 'id2', 'ratio1', 'ratio2']]
result_data = pd.merge(result_data, tmp, how='outer', on=['id1', 'id2'])
result_data['ratio1'] = result_data['ratio1_x'].where(result_data['ratio1_x'].notna(), result_data['ratio1_y'])
result_data['ratio2'] = result_data['ratio2_x'].where(result_data['ratio2_x'].notna(), result_data['ratio2_y'])
result_data = result_data[['id1', 'id2', 'count', 'ratio', 'ratio1', 'ratio2']]
那么,结果就是
id1 | id2 | count | ratio | ratio1 | ratio2 |
---|---|---|---|---|---|
id1 | id2 | 3 | 1.000 | 1.000 | 1.0 |
id1 | id3 | 2 | 0.667 | 0.667 | 1.0 |
id1 | id5 | 1 | 0.333 | 0.333 | 1.0 |
id2 | id3 | 1 | 0.333 | 0.333 | 0.5 |
id5 | id6 | 1 | 0.333 | 1.000 | 1.0 |
要详细解释比率 1 和比率 2,
ratio1
由
- (id1,id2) 计数/最大值(id1_count) = 3/3 = 1
- (id1,id3) 计数/最大值(id1_count) = 2/3 = 0.667
- (id1,id5) 计数/最大值(id1_count) = 1/3 = 0.333
- (id2,id3) 计数/最大值(id2_count) = 1/3 = 0.333
- (id5,id6) 计数/最大值(id5_count) = 1/1 = 1
ratio2
由
- (id1,id2) 计数/最大值(id2_count) = 3/3 = 1
- (id1,id3) 计数/最大值(id3_count) = 2/2 = 1
- (id1,id5) 计数/最大值(id5_count) = 1/1 = 1
- (id2,id3) 计数/最大值(id3_count) = 1/2 = 0.5
- (id5,id6) 计数/最大值(id6_count) = 1/1 = 1
毕竟,我们的最终目标是过滤掉 threshold
.
result_data = result_data[(result_data['ratio1'] >= float(limit_ratio)) | (result_data['ratio2'] >= float(limit_ratio))]
这会给我
id1 | id2 | count | ratio | ratio1 | ratio2 |
---|---|---|---|---|---|
id1 | id2 | 3 | 1.000 | 1.000 | 1.0 |
id1 | id3 | 2 | 0.667 | 0.667 | 1.0 |
id1 | id5 | 1 | 0.333 | 0.333 | 1.0 |
id5 | id6 | 1 | 0.333 | 1.000 | 1.0 |
在这里,代码每次循环需要 12 分钟。数据有 50,000 个唯一 ID,预计 12 * 50000 = 60,000 分钟 = 10,000 小时计算。供您参考,我目前使用的是 python 3.8.8、pandas == 1.2.3 和 numpy == 1.19.5.
设置
>>> result_data
id count id1 id2 ratio
0 (id1, id2) 3 id1 id2 1.000000
1 (id1, id3) 2 id1 id3 0.666667
2 (id1, id5) 1 id1 id5 0.333333
3 (id2, id3) 1 id2 id3 0.333333
4 (id5, id6) 1 id5 id6 0.333333
解决方案
melted = result_data.melt('count', ['id1', 'id2'])
maxima = melted.groupby('value')['count'].max()
result_data['ratio1'] = result_data['count'] / result_data['id1'].map(maxima)
result_data['ratio2'] = result_data['count'] / result_data['id2'].map(maxima)
result_data = result_data.query("ratio1 >= @limit_ratio or ratio2 >= @limit_ratio")
解释
Melt
通过指定 id_vars
为 count
和 value_vars
为 id1, id2
>>> melted
count variable value
0 3 id1 id1
1 2 id1 id1
2 1 id1 id1
3 1 id1 id2
4 1 id1 id5
5 3 id2 id2
6 2 id2 id3
7 1 id2 id5
8 1 id2 id3
9 1 id2 id6
现在 group
melted
数据帧由 value
列和聚合 count
使用 max
计算每个 maximum
计数值28=]
>>> maxima
value
id1 3
id2 3
id3 2
id5 1
id6 1
Name: count, dtype: int64
map
在 id1
和 id2
maxima
>>> result_data['id1'].map(maxima)
0 3
1 3
2 3
3 3
4 1
Name: id1, dtype: int64
>>> result_data['id1'].map(maxima)
0 3
1 2
2 1
3 2
4 1
Name: id2, dtype: int64
现在用上面映射的id1
和id2
列分别划分count
列来计算ratio1
和ratio2
>>> result_data[['ratio1', 'ratio2']]
ratio1 ratio2
0 1.000000 1.0
1 0.666667 1.0
2 0.333333 1.0
3 0.333333 0.5
4 1.000000 1.0
Query
根据 limit_ratio
threshold
值过滤掉行的数据框
>>> result_data
id count id1 id2 ratio ratio1 ratio2
0 (id1, id2) 3 id1 id2 1.000000 1.000000 1.0
1 (id1, id3) 2 id1 id3 0.666667 0.666667 1.0
2 (id1, id5) 1 id1 id5 0.333333 0.333333 1.0
4 (id5, id6) 1 id5 id6 0.333333 1.000000 1.0