我会将元组列表简单地分成N个子列表,其中N是我的计算机上处理器的数量,创建一个大小为N的多进程池,然后并行搜索N个子列表。我还将使用一个集合
search_list
初始化池中的每个进程,以便测试子列表的元素是否是所需元素之一成为O(1)操作(如果
search_list
实际上比2个元素更大)。
然后工作函数search_the_tuple
将传递的列表转换为一个集合,并执行与search_list
的集合交集,并返回结果。一旦第一个并行进程找到一个非零长度的集合返回,剩余的进程就会终止。
问题是将子列表转换为集合并执行交集,这是由库例程完成的,是否比循环遍历子列表并测试集合成员资格快得多,这将主要是Python字节码。
import multiprocessing as mp
def init_pool(s_list):
global search_list
search_list = set(s_list)
def search_the_tuple(t_sub_lib):
for item in t_sub_lib:
if item in search_list:
return(item)
def split(lst, n):
k, m = divmod(len(lst), n)
return (lst[i * k + min(i, m):(i + 1) * k + min(i + 1, m)] for i in range(n))
def main():
search_list = [('a','a','1'), ('m', '1', 'l')]
tuple_library = [
('g', 'z', '1'), ('h', '3', 'b'), ('i', 'a', 'l'), ('j', 'z', '1'), ('k', '3', 'b'), ('l', '1', 'l'),
('m', 'z', '1'), ('n', '3', 'b'), ('o', '1', 'l'), ('p', 'z', '1'), ('q', '3', 'b'), ('r', '1', 'l'),
('a', 'z', '1'), ('r', '3', 'b'), ('m', '1', 'l'), ('d', 'z', '1'), ('e', '3', 'b'), ('f', '1', 'l')
]
n_processors = mp.cpu_count()
with mp.Pool(n_processors, initializer=init_pool, initargs=(search_list,)) as pool:
t_sub_libs = split(tuple_library, n_processors)
for t in pool.imap_unordered(search_the_tuple, t_sub_libs):
if t is not None:
print(t)
break
if __name__ == '__main__':
main()
输出:
('m', '1', 'l')
更新
我做了一个小基准测试,看看把列表转换成集合并执行交集是否值得。在这个基准测试中,我有一个包含20,000个元素的列表,并将要查找的元素放在最后,以让转换成集合有优势:
import timeit
s = set([(19999, 19999), (21000, 21000)])
lst = [(i,i) for i in range(20000)]
def s1():
for i in lst:
if i in s:
return i
def s2():
s2 = set(lst)
return s & s2
print(timeit.timeit('s1()', number=1000, globals=globals()))
print(timeit.timeit('s2()', number=1000, globals=globals()))
输出:
0.9409163000000262
1.8975496000000476
但即使是在这里,集合转换版本s2
的速度也几乎慢了一倍。但当我要查找的值位于列表中间时(平均情况下会是这样),我们有:
import timeit
s = set([(10000, 10000), (21000, 21000)])
lst = [(i,i) for i in range(20000)]
def s1():
for i in lst:
if i in s:
return i
def s2():
s2 = set(lst)
return s & s2
print(timeit.timeit('s1()', number=1000, globals=globals()))
print(timeit.timeit('s2()', number=1000, globals=globals()))
打印:
0.5094996000000265
1.8004526000001988
正如您所预期的那样,s1
现在运行速度几乎快了一倍。
结论
- 您应该将
search_list
转换为集合,因为它将被多次搜索。这可能是您唯一可用的优化。
- 您只指定了
tuple_library
是非常大的。这相当不具体。我的基准测试表明,将您的 tuple_library
转换为集合并没有优势,因为它只被搜索一次。
- 虽然我已经展示了如何使用 multiprocessing 进行“分而治之”,但我并不清楚(再次不知道您的
tuple_library
实际上有多大,甚至可能无关紧要),multiprocessing 是否会提高性能(它甚至可能会降低性能)。创建进程池时存在开销,将子列表传递到“生活”在不同地址空间中的进程时也存在开销。您只需要尝试一下,看看它是否有帮助。
更新 2
@lllrnr101的基准测试存在问题。我原本想将此作为评论提供,但很遗憾,这篇内容太长了。首先,函数normal_search_multiple_tuples_in_tuples_list
应该编写为:
def normal_search_multiple_tuples_in_tuples_list(tuples_to_search, big_tuple_list):
s = set(tuples_to_search)
for t in big_tuple_list:
if t in s:
return t
请注意,在 OP 的问题中,OP 在找到第一个匹配项后返回,并且并没有尝试查找所有匹配项。将
tuples_to_search
至少转换为集合可能更有效,因为它将被多次搜索。
其次,真正需要比较的只有两种策略:
normal_search_multiple_tuples_in_tuples_list
和
intersect_search_tuples_in_tuples_list
。后者涉及首先将列表转换为集合并进行搜索的基准测试并没有正确考虑转换的成本,并且与实际问题不符(打印转换列表为集合的时间是单次转换的成本,而其他打印的时间是 100000 次迭代的成本)。
第三,OP 指定了问题中的列表非常大,无论什么意思,但我认为它比 10、100 和 1000 更大。因此,应该针对更大的列表进行基准测试,使用
timeit
进行较少的迭代,以便在合理的时间内完成。这导致以下基准测试:
import timeit
import time
import random
import string
from random import randint
from random import sample
data_values = string.ascii_lowercase + string.digits
len_data_values = len(data_values)
random_lower_limit = 0
random_upper_limit = len_data_values - 1
def normal_search_multiple_tuples_in_tuples_list(tuples_to_search, big_tuple_list):
s = set(tuples_to_search)
for t in big_tuple_list:
if t in s:
return t
def intersect_search_tuples_in_tuples_list(tuples_to_search, big_tuple_list):
tuples_to_search_set = set(tuples_to_search)
big_tuple_set = set(big_tuple_list)
return tuples_to_search_set.intersection(big_tuple_set)
def get_big_data(big_tuple_list_size):
big_tuple_list = [(
data_values[randint(random_lower_limit, random_upper_limit)],
data_values[randint(random_lower_limit, random_upper_limit)],
data_values[randint(random_lower_limit, random_upper_limit)]
) for _ in range(big_tuple_list_size)]
return big_tuple_list
def get_small_data(big_tuple_list, tuples_to_search_size):
return sample(big_tuple_list, tuples_to_search_size)
def get_required_data(big_tuple_list_size, tuples_to_search_size):
big_tuple_list = get_big_data(big_tuple_list_size)
tuples_to_search = get_small_data(big_tuple_list, tuples_to_search_size)
return (big_tuple_list, tuples_to_search)
if __name__ == '__main__':
test_combinations = [(10000, 5), (20000, 5), (100000, 5)]
functions_to_test = [
normal_search_multiple_tuples_in_tuples_list,
intersect_search_tuples_in_tuples_list
]
for big_tuple_list_size, tuples_to_search_size in test_combinations:
tuples_to_search, big_tuple_list = get_required_data(big_tuple_list_size, tuples_to_search_size)
print(f'For a run of searching {tuples_to_search_size} needles in {big_tuple_list_size} size haystack')
for func in functions_to_test:
print(f'''Time taken by {func.__name__}: {timeit.timeit('func(tuples_to_search, big_tuple_list)', number=1000, globals=globals())}''')
print()
输出:
For a run of searching 5 needles in 10000 size haystack
Time taken by normal_search_multiple_tuples_in_tuples_list: 0.681931
Time taken by intersect_search_tuples_in_tuples_list: 0.5806513
For a run of searching 5 needles in 20000 size haystack
Time taken by normal_search_multiple_tuples_in_tuples_list: 0.8495027999999998
Time taken by intersect_search_tuples_in_tuples_list: 0.8799418999999999
For a run of searching 5 needles in 100000 size haystack
Time taken by normal_search_multiple_tuples_in_tuples_list: 8.51018
Time taken by intersect_search_tuples_in_tuples_list: 8.115366799999999
时间上没有太大的差异。我的基准测试显示,在列表中寻找一个中间元素的情况下,不将列表转换为集合要比转换为集合快得多。但是这个基准测试和我的区别在于,我的基准测试不会将tuples_to_search
列表转换为集合;这个集合是预先创建的,因为 OP 知道他们正在寻找什么。如果我们从基准测试中删除创建该集合的成本,我们有:
import timeit
import time
import random
import string
from random import randint
from random import sample
data_values = string.ascii_lowercase + string.digits
len_data_values = len(data_values)
random_lower_limit = 0
random_upper_limit = len_data_values - 1
def normal_search_multiple_tuples_in_tuples_list(tuples_to_search, big_tuple_list):
for t in big_tuple_list:
if t in tuples_to_search:
return t
def intersect_search_tuples_in_tuples_list(tuples_to_search, big_tuple_list):
big_tuple_set = set(big_tuple_list)
return tuples_to_search.intersection(big_tuple_set)
def get_big_data(big_tuple_list_size):
big_tuple_list = [(
data_values[randint(random_lower_limit, random_upper_limit)],
data_values[randint(random_lower_limit, random_upper_limit)],
data_values[randint(random_lower_limit, random_upper_limit)]
) for _ in range(big_tuple_list_size)]
return big_tuple_list
def get_small_data(big_tuple_list, tuples_to_search_size):
return sample(big_tuple_list, tuples_to_search_size)
def get_required_data(big_tuple_list_size, tuples_to_search_size):
big_tuple_list = get_big_data(big_tuple_list_size)
tuples_to_search = get_small_data(big_tuple_list, tuples_to_search_size)
return (big_tuple_list, tuples_to_search)
if __name__ == '__main__':
test_combinations = [(10000, 5), (20000, 5), (100000, 5)]
functions_to_test = [
normal_search_multiple_tuples_in_tuples_list,
intersect_search_tuples_in_tuples_list
]
for big_tuple_list_size, tuples_to_search_size in test_combinations:
tuples_to_search, big_tuple_list = get_required_data(big_tuple_list_size, tuples_to_search_size)
print(f'For a run of searching {tuples_to_search_size} needles in {big_tuple_list_size} size haystack')
s = set(tuples_to_search)
for func in functions_to_test:
print(f'''Time taken by {func.__name__}: {timeit.timeit('func(s, big_tuple_list)', number=1000000, globals=globals())}''')
print()
输出:
For a run of searching 5 needles in 10000 size haystack
Time taken by normal_search_multiple_tuples_in_tuples_list: 0.16306289999999998
Time taken by intersect_search_tuples_in_tuples_list: 0.6508408
For a run of searching 5 needles in 20000 size haystack
Time taken by normal_search_multiple_tuples_in_tuples_list: 0.16933260000000006
Time taken by intersect_search_tuples_in_tuples_list: 0.6473307000000001
For a run of searching 5 needles in 100000 size haystack
Time taken by normal_search_multiple_tuples_in_tuples_list: 0.1777871999999996
Time taken by intersect_search_tuples_in_tuples_list: 0.7130949000000002
你可以清楚地看到,不应该将列表转换为集合。最后,如果这还不令人信服,这里是我的基准测试,在其中我对我们试图匹配搜索函数中的列表元素进行了集合转换,并且我们正在搜索的列表元素与这些元素之一匹配的元素是最后一个元素。这应该给使用集合交集方法的方法带来最大的优势:
import timeit
def s1(s, lst):
s = set(s)
for i in lst:
if i in s:
return i
def s2(s, lst):
s = set(s)
s2 = set(lst)
return s & s2
lst = [(i,i) for i in range(20000)]
s = [(19999, 19999), (21000, 21000)]
print(timeit.timeit('s1(s, lst)', number=1000, globals=globals()))
print(timeit.timeit('s2(s, lst)', number=1000, globals=globals()))
输出:
0.887862600000517
1.8508867000000464
set
是最佳选择。 - Reti43