在 python 中，如何将两个具有关联计数列表的非常大的列表合并为一个具有关联计数列表的列表？
In python, how to combine two very large lists with associated counts lists into single list with associated counts list?
首先，请注意我一般使用“列表”一词。我怀疑最好的解决方案将使用某种 collection，例如有序字典、“有序集”等
我使用两个列表表示 collection 个 object 列表——一个 object 列表和一个计数列表。 object 列表包含 object，每个都是唯一的。 object 由长整数表示。第二个列表与第一个列表对齐，项目是整数，表示 object 列表中每个关联的 object 在 collection 中的数量（计数，如直方图） .
唯一的object可能的数量很大，比如2**64。然而实际上，在 collection.
中可能会有 20,000-30,000 个唯一的 objects
现在，给定两个 collections：collection A（由列表 obj_A 和 cnt_A 表示）和 collection B（由列表 obj_B 和 cnt_B)，我需要将它们 combine/add 到一个新的 collection，C。因此，我需要找到 A 中所有的 object同样在 B 中，并对那些 object 的 A 和 B 计数求和。仅在 A 或仅在 B 中的 Objects 将保留其各自 collection 中的计数。
例如，在下面的列表中，object 750 在两个列表中，因此组合 collection、C 中 750 的计数是 A 和B collections.
ojb_A = [4903, 750, 29868, 833]
cnt_A = [1, 3, 24, 3 ]
ojb_B = [2357, 39, 750, 38 ]
cnt_B = [8, 52, 6, 2 ]
将 A 和 B 组合成 C 得到：
ojb_C = [4903, 750, 29868, 833, 2357, 39, 38]
cnt_C = [1, 9, 24, 3, 8, 52, 2 ]
正如最初提到的，我怀疑 object 列表的一些有序表示将需要效率，尽管我没有按照上面示例中的顺序显示项目。
[编辑]：
我刚刚发现 collections.Counter 可能满足我的需要。但是同样，我的 collection 有大量独特的 object，所以我正在寻找高度 efficient/fast 的解决方案。
您可以使用 defaultdict 来计算所有计数：
from collections import defaultdict
ojb_A = [4903, 750, 29868, 833]
cnt_A = [1, 3, 24, 3 ]
ojb_B = [2357, 39, 750, 38 ]
cnt_B = [8, 52, 6, 2 ]
def count(out, ojb, cnt):
for index,obj in enumerate(ojb):
out[obj] += cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = defaultdict(int)
count(out, ojb_A, cnt_A)
count(out, ojb_B, cnt_B)
ojb_C, cnt_C = split_out(out)
print(ojb_C, cnt_C)
collections.Counter 和 zip 的组合可能是最简洁的方式，应该也相当有效。
from collections import Counter
counts = Counter(dict(zip(ojb_A, cnt_A)))
counts.update(dict(zip(ojb_B, cnt_B)))
ojb_C, cnt_C = zip(*counts.items())
（仅供参考，ojb_C 和 cnt_C 是元组。）
您可以使用 pandas 高效地做到这一点：
import pandas as pd
df1 = pd.DataFrame(zip(ojb_A,cnt_A))
df2 = pd.DataFrame(zip(ojb_B,cnt_B))
df_combined = pd.concat([df1,df2]).groupby(0).sum()
ojb_C = list(df_combined.index.values)
cnt_C = list(df_combined[1])
只需 303 ms ± 24.9 ms 即可组合 2 个长度为 ~100000
的对象
最新更新
我调整了下面的代码以使用 numba 并且对于更大的输入速度快 2 倍并且可以处理更大的输入而不会在我的本地被杀死。
这会将用 numba.njit 修饰的函数转换为机器代码，并在输入巨大时发光。由于编译原因，后续 运行 总是比第一个 运行 快。我知道这对于 10k-20k 可能不是必需的，但对于 2**64 可能需要。 （P.S。我在工作中使用 numba 来提高速度 ）
使用 numba
import numpy as np
import numba as nb
ojb_A = np.array(ojb_A)
ojb_B = np.array(ojb_B)
cnt_A = np.array(cnt_A)
cnt_B = np.array(cnt_B)
@nb.njit
def count(out, ojb, cnt, i):
for index in nb.prange(ojb.shape[0]):
out[ojb[i]] = out.get(ojb[i], 0) + cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = nb.typed.Dict.empty(
key_type=nb.core.types.int64,
value_type=nb.core.types.int64,
)
count(out, ojb_A, cnt_A, 0)
count(out, ojb_B, cnt_B, 1)
ojb_C, cnt_C = split_out(out)
new_test.py
import random
import sys
import time
import numba as nb
random.seed(31212223)
MAX = 2 ** int(sys.argv[2])
def f3():
ojb_A = random.sample(range(1, 2**30), MAX)
cnt_A = random.sample(range(1, 2**30), MAX)
ojb_B = random.sample(range(1, 2**30), MAX)
cnt_B = random.sample(range(1, 2**30), MAX)
s1 = time.time()
from collections import defaultdict
# @nb.jit
def count(out, ojb, cnt):
for index,obj in enumerate(ojb):
out[obj] += cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = defaultdict(int)
count(out, ojb_A, cnt_A)
count(out, ojb_B, cnt_B)
ojb_C, cnt_C = split_out(out)
# print(ojb_C, cnt_C)
s2 = time.time()
print('quamrana', s2 - s1)
def f3_1():
ojb_A = random.sample(range(1, 2**30), MAX)
cnt_A = random.sample(range(1, 2**30), MAX)
ojb_B = random.sample(range(1, 2**30), MAX)
cnt_B = random.sample(range(1, 2**30), MAX)
s1 = time.time()
import numpy as np
import numba as nb
ojb_A = np.array(ojb_A)
ojb_B = np.array(ojb_B)
cnt_A = np.array(cnt_A)
cnt_B = np.array(cnt_B)
@nb.njit
def count(out, ojb, cnt, i):
for index in nb.prange(ojb.shape[0]):
out[ojb[i]] = out.get(ojb[i], 0) + cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = nb.typed.Dict.empty(
key_type=nb.core.types.int64,
value_type=nb.core.types.int64,
)
count(out, ojb_A, cnt_A, 0)
count(out, ojb_B, cnt_B, 1)
ojb_C, cnt_C = split_out(out)
# print(ojb_C, cnt_C)
s2 = time.time()
print('eroot163pi', s2 - s1)
if __name__ == '__main__':
# Two runs to show subsequent run is faster
eval(f'{sys.argv[1]}()')
eval(f'{sys.argv[1]}()')
运行 巨型案例 2^22-27
- Numba 进程成功完成 2^26，但正常 python 被终止
- Numba 对于这些输入始终更快，并且能够处理受 2^27
限制的更大输入
(base) xxx@xxx:~$ python test.py f3 22
quamrana 3.2768890857696533
quamrana 3.2760112285614014
(base) xxx@xxx:~$ python test.py f3_1 22
eroot163pi 2.4150922298431396
eroot163pi 1.8658664226531982
(base) xxx@xxx:~$ python test.py f3 23
quamrana 6.903605937957764
quamrana 7.187666654586792
(base) xxx@xxx:~$ python test.py f3_1 23
eroot163pi 4.326314926147461
eroot163pi 3.6970062255859375
(base) xxx@xxx:~$ python test.py f3 24
quamrana 14.135217905044556
quamrana 14.102455615997314
(base) xxx@xxx:~$ python test.py f3_1 24
eroot163pi 8.097218751907349
eroot163pi 7.514840602874756
(base) xxx@xxx:~$ python test.py f3 25
quamrana 29.825793743133545
quamrana 30.300193786621094
(base) xxx@xxx:~$ python test.py f3_1 25
eroot163pi 16.243808031082153
eroot163pi 15.114825010299683
(base) xxx@xxx:~$ python test.py f3 26
Killed
(base) xxx@xxx:~$ python test.py f3_1 26
eroot163pi 35.73880386352539
eroot163pi 34.74332834847338
(base) xxx@xxx:~$ python test.py f3_1 27
Killed
其他方法的表现
这是对上述一些方法在庞大的测试用例上的比较。由于我自己对性能很好奇，quamrana的性能真的很好。
对于大于 2**26 的数组长度，上述所有解决方案尝试均被终止。 （由于我自己的系统限制，16gb，12core）
对于其余部分，quamrana 的解决方案始终表现最好，Kapil 的解决方案排名第二。每个解决方案几乎 2-3 倍的加速比下一个 一致
test.py
import random
import sys
import time
random.seed(31212223)
MAX = 2 ** int(sys.argv[2])
ojb_A = random.sample(range(1, 2**30), MAX)
cnt_A = random.sample(range(1, 2**30), MAX)
ojb_B = random.sample(range(1, 2**30), MAX)
cnt_B = random.sample(range(1, 2**30), MAX)
def f1():
s1 = time.time()
import pandas as pd
df1 = pd.DataFrame(zip(ojb_A,cnt_A))
df2 = pd.DataFrame(zip(ojb_B,cnt_B))
df_combined = pd.concat([df1,df2]).groupby(0).sum()
ojb_C = list(df_combined.index.values)
cnt_C = list(df_combined[1])
s2 = time.time()
print('Kapil', s2 - s1)
def f2():
s1 = time.time()
from collections import Counter
counts = Counter(dict(zip(ojb_A, cnt_A)))
counts.update(dict(zip(ojb_B, cnt_B)))
ojb_C, cnt_C = zip(*counts.items())
s2 = time.time()
print('fsimonjetz', s2 - s1)
def f3():
s1 = time.time()
from collections import defaultdict
def count(out, ojb, cnt):
for index,obj in enumerate(ojb):
out[obj] += cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = defaultdict(int)
count(out, ojb_A, cnt_A)
count(out, ojb_B, cnt_B)
ojb_C, cnt_C = split_out(out)
# print(ojb_C, cnt_C)
s2 = time.time()
print('quamrana', s2 - s1)
if __name__ == '__main__':
eval(f'{sys.argv[1]}()')
2^20、2^21、2^22
的表现
(base) xxx@xxx:~$ python test.py f1 20
Kapil 2.0021448135375977
(base) xxx@xxx:~$ python test.py f2 20
fsimonjetz 2.720785617828369
(base) xxx@xxx:~$ python test.py f3 20
quamrana 0.717628002166748
(base) xxx@xxx:~$ python test.py f1 21
Kapil 4.06165337562561
(base) xxx@xxx:~$ python test.py f2 21
fsimonjetz 6.2198286056518555
(base) xxx@xxx:~$ python test.py f3 21
quamrana 1.563591718673706
(base) xxx@xxx:~$ python test.py f1 22
Kapil 8.361187934875488
(base) xxx@xxx:~$ python test.py f2 22
fsimonjetz 14.354418992996216
(base) xxx@xxx:~$ python test.py f3 22
quamrana 3.355391025543213
首先，请注意我一般使用“列表”一词。我怀疑最好的解决方案将使用某种 collection，例如有序字典、“有序集”等
我使用两个列表表示 collection 个 object 列表——一个 object 列表和一个计数列表。 object 列表包含 object，每个都是唯一的。 object 由长整数表示。第二个列表与第一个列表对齐，项目是整数，表示 object 列表中每个关联的 object 在 collection 中的数量（计数，如直方图） .
唯一的object可能的数量很大，比如2**64。然而实际上，在 collection.
中可能会有 20,000-30,000 个唯一的 objects现在，给定两个 collections：collection A（由列表 obj_A 和 cnt_A 表示）和 collection B（由列表 obj_B 和 cnt_B)，我需要将它们 combine/add 到一个新的 collection，C。因此，我需要找到 A 中所有的 object同样在 B 中，并对那些 object 的 A 和 B 计数求和。仅在 A 或仅在 B 中的 Objects 将保留其各自 collection 中的计数。
例如，在下面的列表中，object 750 在两个列表中，因此组合 collection、C 中 750 的计数是 A 和B collections.
ojb_A = [4903, 750, 29868, 833]
cnt_A = [1, 3, 24, 3 ]
ojb_B = [2357, 39, 750, 38 ]
cnt_B = [8, 52, 6, 2 ]
将 A 和 B 组合成 C 得到：
ojb_C = [4903, 750, 29868, 833, 2357, 39, 38]
cnt_C = [1, 9, 24, 3, 8, 52, 2 ]
正如最初提到的，我怀疑 object 列表的一些有序表示将需要效率，尽管我没有按照上面示例中的顺序显示项目。
[编辑]：
我刚刚发现 collections.Counter 可能满足我的需要。但是同样，我的 collection 有大量独特的 object，所以我正在寻找高度 efficient/fast 的解决方案。
您可以使用 defaultdict 来计算所有计数：
from collections import defaultdict
ojb_A = [4903, 750, 29868, 833]
cnt_A = [1, 3, 24, 3 ]
ojb_B = [2357, 39, 750, 38 ]
cnt_B = [8, 52, 6, 2 ]
def count(out, ojb, cnt):
for index,obj in enumerate(ojb):
out[obj] += cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = defaultdict(int)
count(out, ojb_A, cnt_A)
count(out, ojb_B, cnt_B)
ojb_C, cnt_C = split_out(out)
print(ojb_C, cnt_C)
collections.Counter 和 zip 的组合可能是最简洁的方式，应该也相当有效。
from collections import Counter
counts = Counter(dict(zip(ojb_A, cnt_A)))
counts.update(dict(zip(ojb_B, cnt_B)))
ojb_C, cnt_C = zip(*counts.items())
（仅供参考，ojb_C 和 cnt_C 是元组。）
您可以使用 pandas 高效地做到这一点：
import pandas as pd
df1 = pd.DataFrame(zip(ojb_A,cnt_A))
df2 = pd.DataFrame(zip(ojb_B,cnt_B))
df_combined = pd.concat([df1,df2]).groupby(0).sum()
ojb_C = list(df_combined.index.values)
cnt_C = list(df_combined[1])
只需 303 ms ± 24.9 ms 即可组合 2 个长度为 ~100000
最新更新
我调整了下面的代码以使用 numba 并且对于更大的输入速度快 2 倍并且可以处理更大的输入而不会在我的本地被杀死。
这会将用 numba.njit 修饰的函数转换为机器代码，并在输入巨大时发光。由于编译原因，后续 运行 总是比第一个 运行 快。我知道这对于 10k-20k 可能不是必需的，但对于 2**64 可能需要。 （P.S。我在工作中使用 numba 来提高速度
使用 numba
import numpy as np
import numba as nb
ojb_A = np.array(ojb_A)
ojb_B = np.array(ojb_B)
cnt_A = np.array(cnt_A)
cnt_B = np.array(cnt_B)
@nb.njit
def count(out, ojb, cnt, i):
for index in nb.prange(ojb.shape[0]):
out[ojb[i]] = out.get(ojb[i], 0) + cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = nb.typed.Dict.empty(
key_type=nb.core.types.int64,
value_type=nb.core.types.int64,
)
count(out, ojb_A, cnt_A, 0)
count(out, ojb_B, cnt_B, 1)
ojb_C, cnt_C = split_out(out)
new_test.py
import random
import sys
import time
import numba as nb
random.seed(31212223)
MAX = 2 ** int(sys.argv[2])
def f3():
ojb_A = random.sample(range(1, 2**30), MAX)
cnt_A = random.sample(range(1, 2**30), MAX)
ojb_B = random.sample(range(1, 2**30), MAX)
cnt_B = random.sample(range(1, 2**30), MAX)
s1 = time.time()
from collections import defaultdict
# @nb.jit
def count(out, ojb, cnt):
for index,obj in enumerate(ojb):
out[obj] += cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = defaultdict(int)
count(out, ojb_A, cnt_A)
count(out, ojb_B, cnt_B)
ojb_C, cnt_C = split_out(out)
# print(ojb_C, cnt_C)
s2 = time.time()
print('quamrana', s2 - s1)
def f3_1():
ojb_A = random.sample(range(1, 2**30), MAX)
cnt_A = random.sample(range(1, 2**30), MAX)
ojb_B = random.sample(range(1, 2**30), MAX)
cnt_B = random.sample(range(1, 2**30), MAX)
s1 = time.time()
import numpy as np
import numba as nb
ojb_A = np.array(ojb_A)
ojb_B = np.array(ojb_B)
cnt_A = np.array(cnt_A)
cnt_B = np.array(cnt_B)
@nb.njit
def count(out, ojb, cnt, i):
for index in nb.prange(ojb.shape[0]):
out[ojb[i]] = out.get(ojb[i], 0) + cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = nb.typed.Dict.empty(
key_type=nb.core.types.int64,
value_type=nb.core.types.int64,
)
count(out, ojb_A, cnt_A, 0)
count(out, ojb_B, cnt_B, 1)
ojb_C, cnt_C = split_out(out)
# print(ojb_C, cnt_C)
s2 = time.time()
print('eroot163pi', s2 - s1)
if __name__ == '__main__':
# Two runs to show subsequent run is faster
eval(f'{sys.argv[1]}()')
eval(f'{sys.argv[1]}()')
运行 巨型案例 2^22-27
- Numba 进程成功完成 2^26，但正常 python 被终止
- Numba 对于这些输入始终更快，并且能够处理受 2^27 限制的更大输入
(base) xxx@xxx:~$ python test.py f3 22
quamrana 3.2768890857696533
quamrana 3.2760112285614014
(base) xxx@xxx:~$ python test.py f3_1 22
eroot163pi 2.4150922298431396
eroot163pi 1.8658664226531982
(base) xxx@xxx:~$ python test.py f3 23
quamrana 6.903605937957764
quamrana 7.187666654586792
(base) xxx@xxx:~$ python test.py f3_1 23
eroot163pi 4.326314926147461
eroot163pi 3.6970062255859375
(base) xxx@xxx:~$ python test.py f3 24
quamrana 14.135217905044556
quamrana 14.102455615997314
(base) xxx@xxx:~$ python test.py f3_1 24
eroot163pi 8.097218751907349
eroot163pi 7.514840602874756
(base) xxx@xxx:~$ python test.py f3 25
quamrana 29.825793743133545
quamrana 30.300193786621094
(base) xxx@xxx:~$ python test.py f3_1 25
eroot163pi 16.243808031082153
eroot163pi 15.114825010299683
(base) xxx@xxx:~$ python test.py f3 26
Killed
(base) xxx@xxx:~$ python test.py f3_1 26
eroot163pi 35.73880386352539
eroot163pi 34.74332834847338
(base) xxx@xxx:~$ python test.py f3_1 27
Killed
其他方法的表现
这是对上述一些方法在庞大的测试用例上的比较。由于我自己对性能很好奇，quamrana的性能真的很好。
对于大于 2**26 的数组长度，上述所有解决方案尝试均被终止。 （由于我自己的系统限制，16gb，12core）
对于其余部分，quamrana 的解决方案始终表现最好，Kapil 的解决方案排名第二。每个解决方案几乎 2-3 倍的加速比下一个 一致
test.py
import random
import sys
import time
random.seed(31212223)
MAX = 2 ** int(sys.argv[2])
ojb_A = random.sample(range(1, 2**30), MAX)
cnt_A = random.sample(range(1, 2**30), MAX)
ojb_B = random.sample(range(1, 2**30), MAX)
cnt_B = random.sample(range(1, 2**30), MAX)
def f1():
s1 = time.time()
import pandas as pd
df1 = pd.DataFrame(zip(ojb_A,cnt_A))
df2 = pd.DataFrame(zip(ojb_B,cnt_B))
df_combined = pd.concat([df1,df2]).groupby(0).sum()
ojb_C = list(df_combined.index.values)
cnt_C = list(df_combined[1])
s2 = time.time()
print('Kapil', s2 - s1)
def f2():
s1 = time.time()
from collections import Counter
counts = Counter(dict(zip(ojb_A, cnt_A)))
counts.update(dict(zip(ojb_B, cnt_B)))
ojb_C, cnt_C = zip(*counts.items())
s2 = time.time()
print('fsimonjetz', s2 - s1)
def f3():
s1 = time.time()
from collections import defaultdict
def count(out, ojb, cnt):
for index,obj in enumerate(ojb):
out[obj] += cnt[index]
def split_out(out):
return list(out.keys()), list(out.values())
out = defaultdict(int)
count(out, ojb_A, cnt_A)
count(out, ojb_B, cnt_B)
ojb_C, cnt_C = split_out(out)
# print(ojb_C, cnt_C)
s2 = time.time()
print('quamrana', s2 - s1)
if __name__ == '__main__':
eval(f'{sys.argv[1]}()')
2^20、2^21、2^22
的表现(base) xxx@xxx:~$ python test.py f1 20
Kapil 2.0021448135375977
(base) xxx@xxx:~$ python test.py f2 20
fsimonjetz 2.720785617828369
(base) xxx@xxx:~$ python test.py f3 20
quamrana 0.717628002166748
(base) xxx@xxx:~$ python test.py f1 21
Kapil 4.06165337562561
(base) xxx@xxx:~$ python test.py f2 21
fsimonjetz 6.2198286056518555
(base) xxx@xxx:~$ python test.py f3 21
quamrana 1.563591718673706
(base) xxx@xxx:~$ python test.py f1 22
Kapil 8.361187934875488
(base) xxx@xxx:~$ python test.py f2 22
fsimonjetz 14.354418992996216
(base) xxx@xxx:~$ python test.py f3 22
quamrana 3.355391025543213