提问人：alvas 提问时间：3/8/2016 最后编辑：Communityalvas 更新时间：3/9/2016 访问量：1776
获取列表并集的最快方法 - Python
Fastest way to get union of lists - Python
问：
有一个 C++ 比较可以从列表列表中获取列表的并集：查找集合并集的最快方法
还有其他几个与 python 相关的问题，但没有一个问题建议将列表联合起来的最快方法：
从答案中，我收集到至少有 2 种方法可以做到这一点：
>>> from itertools import chain
>>> x = [[1,2,3], [3,4,5], [1,7,8]]
>>> list(set().union(*x))
[1, 2, 3, 4, 5, 7, 8]
>>> list(set(chain(*x)))
[1, 2, 3, 4, 5, 7, 8]
请注意，我稍后将集合强制转换为列表，因为我需要固定列表的顺序以进行进一步处理。
经过一番比较，它似乎更稳定，花费的时间更少：list(set(chain(*x)))
from itertools import chain
import time
import random
# Dry run.
x = [[random.choice(range(10000))
for i in range(10)] for j in range(10)]
list(set().union(*x))
list(set(chain(*x)))
y_time = 0
z_time = 0
for _ in range(1000):
x = [[random.choice(range(10000))
for i in range(10)] for j in range(10)]
start = time.time()
y = list(set().union(*x))
y_time += time.time() - start
#print 'list(set().union(*x)):\t', y_time
start = time.time()
z = list(set(chain(*x)))
z_time += time.time() - start
#print 'list(set(chain(*x))):\t', z_time
assert sorted(y) == sorted(z)
#print
print y_time / 1000.
print z_time / 1000.
[输出]：
1.39586925507e-05
1.09834671021e-05
取出铸造集的变量列出：
y_time = 0
z_time = 0
for _ in range(1000):
x = [[random.choice(range(10000))
for i in range(10)] for j in range(10)]
start = time.time()
y = set().union(*x)
y_time += time.time() - start
start = time.time()
z = set(chain(*x))
z_time += time.time() - start
assert sorted(y) == sorted(z)
print y_time / 1000.
print z_time / 1000.
[输出]：
1.22241973877e-05
1.02684497833e-05
这是我尝试打印中间时间（没有列表强制转换）时的完整输出： http://pastebin.com/raw/y3i6dXZ8
为什么 list（set（chain（*x））） 比 list（set（）.union（*x）） 花费的时间少？
有没有另一种方法可以实现相同的列表联合？使用 numpy 或 pandas 或 sframe 或其他东西？ 替代方案更快吗？
答：
7赞
unutbu
3/8/2016
#1
什么最快取决于 -- 是长列表还是短列表，子列表多还是子列表少，子列表是长还是短，重复的多还是少。x
以下是一些比较一些替代方案的 timeit 结果。有太多的可能性，这绝不是一个完整的分析，但也许这会给你一个研究你的用例的框架。
func | x | time
unique_concatenate | many_uniques | 0.863
empty_set_union | many_uniques | 1.191
short_set_union_rest | many_uniques | 1.192
long_set_union_rest | many_uniques | 1.194
set_chain | many_uniques | 1.224
func | x | time
long_set_union_rest | many_duplicates | 0.958
short_set_union_rest | many_duplicates | 0.969
empty_set_union | many_duplicates | 0.971
set_chain | many_duplicates | 1.128
unique_concatenate | many_duplicates | 2.411
func | x | time
empty_set_union | many_small_lists | 1.023
long_set_union_rest | many_small_lists | 1.028
set_chain | many_small_lists | 1.032
short_set_union_rest | many_small_lists | 1.036
unique_concatenate | many_small_lists | 1.351
func | x | time
long_set_union_rest | few_large_lists | 0.791
empty_set_union | few_large_lists | 0.813
unique_concatenate | few_large_lists | 0.814
set_chain | few_large_lists | 0.829
short_set_union_rest | few_large_lists | 0.849
请务必在您自己的计算机上运行 timeit 基准测试，因为结果可能会有所不同。
from __future__ import print_function
import random
import timeit
from itertools import chain
import numpy as np
def unique_concatenate(x):
return np.unique(np.concatenate(x))
def short_set_union_rest(x):
# This assumes x[0] is the shortest list in x
return list(set(x[0]).union(*x[1:]))
def long_set_union_rest(x):
# This assumes x[-1] is the longest list in x
return list(set(x[-1]).union(*x[1:]))
def empty_set_union(x):
return list(set().union(*x))
def set_chain(x):
return list(set(chain(*x)))
big_range = list(range(10**7))
small_range = list(range(10**5))
many_uniques = [[random.choice(big_range) for i in range(j)]
for j in range(10, 10000, 10)]
many_duplicates = [[random.choice(small_range) for i in range(j)]
for j in range(10, 10000, 10)]
many_small_lists = [[random.choice(big_range) for i in range(10)]
for j in range(10, 10000, 10)]
few_large_lists = [[random.choice(big_range) for i in range(1000)]
for j in range(10, 100, 10)]
if __name__=='__main__':
for x, n in [('many_uniques', 1), ('many_duplicates', 4),
('many_small_lists', 800), ('few_large_lists', 800)]:
timing = dict()
for func in [
'unique_concatenate', 'short_set_union_rest', 'long_set_union_rest',
'empty_set_union', 'set_chain']:
timing[func, x] = timeit.timeit(
'{}({})'.format(func, x), number=n,
setup='from __main__ import {}, {}'.format(func, x))
print('{:20} | {:20} | {}'.format('func', 'x', 'time'))
for key, t in sorted(timing.items(), key=lambda item: item[1]):
func, x = key
print('{:20} | {:20} | {:.3f}'.format(func, x, t))
print(end='\n')
评论