быстрый способ получить объединение списков - Python

Question

Там в C++ сравнения, чтобы получить объединение списков из списков списков: The fastest way to find union of sets

И есть несколько других вопросов, связанных с питона, но ни один не предложить самый быстрый способ объединять списки:

• Finding a union of lists of lists in Python
• Flattening a shallow list in Python

Из ответов, я понял, что Ther е, по крайней мере 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. 

[out]:

1.22241973877e-05 
1.02684497833e-05 

Вот полный выход, когда я пытаюсь напечатать промежуточные моменты времени (без списка литья): http://pastebin.com/raw/y3i6dXZ8

Почему list(set(chain(*x))) занимает меньше времени, чем list(set().union(*x))?

Есть ли другой способ достижения такого же объединения списков? Использование numpy или pandas или sframe или что-то в этом роде?Является ли альтернатива быстрее?

Answer 1

Что быстро зависит от характера x - будь то длинный список или короткий список, со многими подсписками или несколько подсписков ли подсписки длинные или короткие, и есть ли много дубликатов или несколько дубликатов ,

Вот несколько примеров времени, сравнивающих некоторые альтернативы. Существует так много возможностей, что это далеко не полный анализ, но, возможно, это даст вам основу для изучения вашего варианта использования.

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 

Обязательно запустите тесты времени на своей собственной машине, так как результаты могут отличаться.

---

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')