Да, set (l1) .union (l2) определенно мой любимый :)

ите за плохо сформулированный заголовок, но я задал вопрос ранее о получении уникального списка элементов из двух списков. Люди сказали мне, чтобы сделать список -> наборы, а затем объединение.

Так что теперь мне интересно, если это быстрее:

При добавленииодин элемент в список, отсканируйте весь список на наличие дубликатов.Сделайте этот один набор набором, а затем объедините наборы.

Я должен, наверное, просто прочитать о наборах задним числом ...

В Python, кстати - простите за не выяснение.

 Karl Knechtel12 янв. 2011 г., 23:19
Набор - это контейнер, такой же, как список. Вы не превращаете один элемент в набор, вы превращаете весь список в набор. Вы не помещаете элементы в набор по одному. Вы просто создаете набор из списка.
 Steven Rumbalski12 янв. 2011 г., 23:14
зачем использовать списки для начала?
 kriss15 янв. 2011 г., 18:14
@ Карл Кнетчел: ну, этовозможно, все еще любопытно на актуальную проблему. Поскольку я понимаю вопрос о добавлении элементов один за другим, я удивляюсь, что причина, по которой этот вопрос задается таким образом, заключается не в каком-то вызове процессу, который создает эти элементы один за другим.
 bmargulies12 янв. 2011 г., 22:25
На каком языке? С какой библиотекой? Там нет ответа на это в аннотации.
 S.Lott12 янв. 2011 г., 22:25
Вы знакомы сtimeit модуль? Вы можете собрать некоторые данные и включитьtimeit результаты как часть вашего вопроса.

Ответы на вопрос(4)

что вы можете сделать, это собрать два набора из списков и объединить их. И конструкция множеств из списка, и объединение множеств реализованы во время выполнения, в очень оптимизированном C, так что это очень быстро.

В коде, если спискиl1 а такжеl2, ты можешь сделать

unique_elems = set(l1) | set(l2)

РЕДАКТИРОВАТЬ: как @kriss отмечает, расширяяl1 с участиемl2 быстрее. Этот код, однако, не меняетсяl1, и работает также, еслиl1 а такжеl2 являются общими итерациями.

 kriss12 янв. 2011 г., 23:20
как вы видите, глядя на ответ @virhilo, ваш ответ не соответствует действительности. Начальный список быстрее расширить, чем преобразовать в набор. Это имеет смысл, поскольку также вызывает очень оптимизированный C, и расширяет проверки почти ничего, и это намного проще, чем создание набора. Однако я не буду опускать голос, так как подозреваю, что ваше предложение может быть еще быстрее с некоторыми наборами тестов (например, списки, содержащие много дубликатов при запуске).
 Giuseppe Ottaviano12 янв. 2011 г., 23:47
@kriss: это быстрее, если есть много дубликатов. В любом случае, я все еще предпочитаю этот код, потому что он не имеет побочных эффектов в первом списке (в то время как код @ virhilo делает), и он работает также, еслиl1 а такжеl2 являются повторяемыми, которые не являютсяlists
 Giuseppe Ottaviano13 янв. 2011 г., 01:19
Да, set (l1) .union (l2) определенно мой любимый :)
 kriss13 янв. 2011 г., 01:11
Вы также можете сделатьnewlist = list(l1); newlist.extend(l2); return newlist; это также работает на любой итерируемой и не изменяет начальный список, или (даже быстрее)return set(l1).union(l2) этот последний избежать одной операции (создание второго набора) по сравнению с вашей версией.
 kriss12 янв. 2011 г., 23:30
Я проверил сl1 = range(200) * 100; l2 = range(150, 250) * 100 использование кода @virhilo и действительно преобразование обоих списков в наборы становится немного быстрее, чем первое расширение начального списка ... но я считаю, что этот набор тестов является крайним случаем.
Решение Вопроса

расширяя один список за другим, затем удаляйте дубликаты, делая set самым быстрым способом (по крайней мере, в python;))

>>> def foo():
...     """
...     extending one list by another end then remove duplicates by making set
...     """
...     l1 = range(200)
...     l2 = range(150, 250)
...     l1.extend(l2)
...     set(l1)
... 
>>> def bar():
...     """
...     checking if element is on one list end adding it only if not
...     """
...     l1 = range(200)
...     l2 = range(150, 250)
...     for elem in l2:
...             if elem not in l1:
...                     l1.append(elem)
... 
>>> def baz():
...     """
...     making sets from both lists and then union from them
...     """
...     l1 = range(200)
...     l2 = range(150, 250)
...     set(l1) | set(l2)
... 
>>> from timeit import Timer
>>> Timer(foo).timeit(10000)
0.265153169631958
>>> Timer(bar).timeit(10000)
7.921358108520508
>>> Timer(baz).timeit(10000)
0.3845551013946533
>>> 
 kriss13 янв. 2011 г., 01:15
или еще быстрееset(l1).union(l2) ничего не модифицирует, а также эффективно использует память.
 Justin Peel13 янв. 2011 г., 00:22
делаx = set(l1); x.update(l2) так быстро, какfoo метод (возможно, немного быстрее на моем компьютере) и использует меньше памяти. Это также не меняетl1.
 John La Rooy12 янв. 2011 г., 23:55
set(itertools.chain(l1,l2)) только чуть-чуть медленнее и не нуждается в измененииl1, Также более эффективно использовать память, если l1 и l2 большие
 Justin Peel13 янв. 2011 г., 03:34
@kriss, ты успел? Это примерно на 25% медленнее, чем при использовании метода обновления по моим подсчетам. Я уверен, что использование такого объединения медленнее, потому что сначала создаетсяset(l1) и затем создает другой набор (который он возвращает), когда он выполняет объединение.
 kriss13 янв. 2011 г., 08:05
@Justin Peel: Да, я успел это сделать, но у меня была опечатка в моем наборе тестов, а я быстрее (но все же медленнее в большинстве случаев - в три раза в этом сценарии - чем расширение начального списка).

который сделал virhilo, но это довольно специфический набор данных, которые он тестировал. Во всем этом не просто проверяйте функции, но проверяйте их, как вы будете это делать. Я собрал гораздо более исчерпывающий набор тестов. Он запускает каждую указанную вами функцию (с помощью небольшого декоратора) через список сравнений и выясняет, сколько времени занимает каждая функция и, следовательно, насколько она медленнее. В результате не всегда понятно, какую функцию вы должны выполнять, не зная больше о размере, перекрытии и типе ваших данных.

Вот моя тестовая программа, ниже будет вывод.

from timeit import Timer
from copy import copy
import random
import sys

funcs = []

class timeMe(object):
    def __init__(self, f):
        funcs.append(f)
        self.f = f

    def __call__(self, *args, **kwargs):
        return self.f(*args, **kwargs)

@timeMe
def extend_list_then_set(input1, input2):
    """
    extending one list by another end then remove duplicates by making set
    """
    l1 = copy(input1)
    l2 = copy(input2)
    l1.extend(l2)
    set(l1)

@timeMe
def per_element_append_to_list(input1, input2):
    """
    checking if element is on one list end adding it only if not
    """
    l1 = copy(input1)
    l2 = copy(input2)
    for elem in l2:
            if elem not in l1:
                    l1.append(elem)

@timeMe
def union_sets(input1, input2):
    """
    making sets from both lists and then union from them
    """
    l1 = copy(input1)
    l2 = copy(input2)
    set(l1) | set(l2)

@timeMe
def set_from_one_add_from_two(input1, input2):
    """
    make set from list 1, then add elements for set 2
    """
    l1 = copy(input1)
    l2 = copy(input2)
    l1 = set(l1)
    for element in l2:
        l1.add(element)

@timeMe
def set_from_one_union_two(input1, input2):
    """
    make set from list 1, then union list 2
    """
    l1 = copy(input1)
    l2 = copy(input2)
    x = set(l1).union(l2)

@timeMe
def chain_then_set(input1, input2):
    """
    chain l1 & l2, then make a set out of that
    """
    l1 = copy(input1)
    l2 = copy(input2)
    set(itertools.chain(l1, l2))

def run_results(l1, l2, times):
    for f in funcs:
        t = Timer('%s(l1, l2)' % f.__name__,
            'from __main__ import %s; l1 = %s; l2 = %s' % (f.__name__, l1, l2))
        yield (f.__name__, t.timeit(times))    

test_datasets = [
    ('original, small, some overlap', range(200), range(150, 250), 10000),
    ('no overlap: l1 = [1], l2 = [2..100]', [1], range(2, 100), 10000),
    ('lots of overlap: l1 = [1], l2 = [1]*100', [1], [1]*100, 10000),
    ('50 random ints below 2000 in each', [random.randint(0, 2000) for x in range(50)], [random.randint(0, 2000) for x in range(50)], 10000),
    ('50 elements in each, no overlap', range(50), range(51, 100), 10000),
    ('50 elements in each, total overlap', range(50), range(50), 10000),
    ('500 random ints below 500 in each', [random.randint(0, 500) for x in range(500)], [random.randint(0, 500) for x in range(500)], 1000),
    ('500 random ints below 2000 in each', [random.randint(0, 2000) for x in range(500)], [random.randint(0, 2000) for x in range(500)], 1000),
    ('500 random ints below 200000 in each', [random.randint(0, 200000) for x in range(500)], [random.randint(0, 200000) for x in range(500)], 1000),
    ('500 elements in each, no overlap', range(500), range(501, 1000), 10000),
    ('500 elements in each, total overlap', range(500), range(500), 10000),
    ('10000 random ints below 200000 in each', [random.randint(0, 200000) for x in range(10000)], [random.randint(0, 200000) for x in range(10000)], 50),
    ('10000 elements in each, no overlap', range(10000), range(10001, 20000), 10),
    ('10000 elements in each, total overlap', range(10000), range(10000), 10),
    ('original lists 100 times', range(200)*100, range(150, 250)*100, 10),
]

fullresults = []
for description, l1, l2, times in test_datasets:
    print "Now running %s times: %s" % (times, description)
    results = list(run_results(l1, l2, times))
    speedresults = [x for x in sorted(results, key=lambda x: x[1])]
    for name, speed in results:
        finish = speedresults.index((name, speed)) + 1
        timesslower = speed / speedresults[0][1]
        fullresults.append((description, name, speed, finish, timesslower))
        print '\t', finish, ('%.2fx' % timesslower).ljust(10), name.ljust(40), speed

print
import csv
out = csv.writer(sys.stdout)
out.writerow(('Test', 'Function', 'Speed', 'Place', 'timesslower'))
out.writerows(fullresults)
Результаты, достижения

Я хочу побудить вас протестировать свои данные, поэтому я не хочу вдаваться в подробности. Однако ... Первый метод расширения является самым быстрым методом усреднения, но set_from_one_union_two (x = set(l1).union(l2)) побеждает несколько раз. Вы можете получить более подробную информацию, если вы запустите скрипт самостоятельно.

Числа, о которых я сообщаю, в несколько раз медленнее, чем эта функция, чем самая быстрая функция в этом тесте. Если это был самый быстрый, это будет 1.

                                            Functions                                                                                                                           
Tests                                       extend_list_then_set     per_element_append_to_list    set_from_one_add_from_two  set_from_one_union_two     union_sets      chain_then_set
original, small, some overlap               1                          25.04                        1.53                        1.18                       1.39           1.08
no overlap: l1 = [1], l2 = [2..100]         1.08                       13.31                        2.10                        1                          1.27           1.07
lots of overlap: l1 = [1], l2 = [1]*100     1.10                        1.30                        2.43                        1                          1.25           1.05
50 random ints below 2000 in each           1                           7.76                        1.35                        1.20                       1.31           1   
50 elements in each, no overlap             1                           9.00                        1.48                        1.13                       1.18           1.10
50 elements in each, total overlap          1.08                        4.07                        1.64                        1.04                       1.41           1   
500 random ints below 500 in each           1.16                       68.24                        1.75                        1                          1.28           1.03
500 random ints below 2000 in each          1                         102.42                        1.64                        1.43                       1.81           1.20
500 random ints below 200000 in each        1.14                      118.96                        1.99                        1.52                       1.98           1   
500 elements in each, no overlap            1.01                      145.84                        1.86                        1.25                       1.53           1   
500 elements in each, total overlap         1                          53.10                        1.95                        1.16                       1.57           1.05          
10000 random ints below 200000 in each      1                        2588.99                        1.73                        1.35                       1.88           1.12
10000 elements in each, no overlap          1                        3164.01                        1.91                        1.26                       1.65           1.02
10000 elements in each, total overlap       1                        1068.67                        1.89                        1.26                       1.70           1.05
original lists 100 times                    1.11                     2068.06                        2.03                        1                          1.04           1.17

                                 Average    1.04                      629.25                       1.82                         1.19                       1.48           1.06
                      Standard Deviation    0.05                     1040.76                       0.26                         0.15                       0.26           0.05
                                     Max    1.16                     3164.01                       2.43                         1.52                       1.98           1.20
 chmullig13 янв. 2011 г., 15:57
Я согласен, что операция копирования нечетная, но все они делают это, поэтому она должна быть одинаково эффективной для всех. Я хотел выровнять игровое поле того, кто изменяет исходный l1, а кто нет, насколько это возможно, с последовательным аспектом. Я добавлю цепочку @ gnibbler сейчас.
 kriss13 янв. 2011 г., 07:52
+1 за хороший набор тестов. Еще есть несколько реализаций, которые можно добавить в тест, например, ichain из @gnibbler. Также сомнительно, что при реальном использовании время создания списка (l1.copy ()) должно учитываться ... в некоторых случаях, например, объединение копирования множества l1 - просто потеря времени, и во всех случаях копирование l2 совершенно бесполезно (l2 не был изменен в начале), это может изменить «победителя» ... в целом, зная больше о фактическом сценарии использования ОП, было бы интересно интерпретировать результаты.

что вы имеете в качестве входных данных и хотите в качестве выходных.

Если у вас есть списокli в начале и хотите получить модифицированный список в конце, затем более быстрый методif not elt in li: li.append(elt) проблема заключается в преобразовании начального списка в набор, а затем обратном преобразовании в список, который слишком медленный.

Но если вы можете работать с наборомs в любое время (вам не важен порядок списка, а методы, получающие его, просто нуждаются в повторении), простоs.add(elt) быстрее.

Если в начале вам нужны списки и вам нужен список в конце, даже с окончательным преобразованием из набора списков в список, быстрее управлять уникальностью элементов с помощью наборов, но вы можете легко проверить, посмотрев пример, предоставленный @virhilo в этом ответе, чем объединение двух списков с использованием extends, преобразование результата в набор происходит быстрее, чем преобразование двух списков в наборы и выполнение объединения.

Я не знаю точно, каковы ограничения ваших программ, но если уникальность так важна, как кажется, и если нет необходимости сохранять порядок вставки, вам будет рекомендовано использовать наборы всегда, никогда не меняя их на списки , Большинство алгоритмов будут работать в любом случае, благодаряУтка набрав поскольку они оба разные виды итераций.

Ваш ответ на вопрос