Сравнение производительности: операции вставки и сборки набора Python

#python #set #time-complexity

#python #набор #временная сложность

Вопрос:

Быстрее ли в python а) Создавать набор из списка из n элементов б) вставлять n элементов в набор?

Я нашел эту страницу (http://wiki .python.org/moin/TimeComplexity ) но у него не было достаточной информации, чтобы сделать вывод, что было быстрее.

Кажется, что вставка элементов по одному в худшем случае может занять O (n * n) времени (учитывая, что он использует dicts) и O (n * 1) в среднем случае. Обеспечивает ли инициализация набора с помощью списка какое-либо улучшение производительности?

1. Кажется, вы хотите сравнить построение набора из списка с вставкой n элементов в set, но первая строка вопроса означает что-то другое.

2. Упс! спасибо, что указал на это, сатиш.

3. Это легко выяснить самостоятельно с помощью timeit .

Ответ №1:

С точки зрения O() сложности — это определенно одно и то же, потому что оба подхода выполняют абсолютно одинаковое — вставляют n элементы в набор.

Разница заключается в реализации: Одним из явных преимуществ инициализации с помощью iterable является то, что вы экономите много вызовов функций на уровне Python — инициализация с помощью iterable выполняется полностью на уровне C (**).

Действительно, некоторые тесты в списке из 5 000 000 случайных целых чисел показывают, что добавление одного за другим происходит медленнее:

 lst = [random.random() for i in xrange(5000000)]
set1 = set(lst)    # takes 2.4 seconds

set2 = set()       # takes 3.37 seconds
for item in lst:
    set2.add(item)

(**) Заглядывая внутрь кода наборов ( Objects/setobject.c ), в конечном итоге вставка элемента сводится к вызову set_add_key . При инициализации из iterable эта функция вызывается в тесном цикле C:

 while ((key = PyIter_Next(it)) != NULL) {
  if (set_add_key(so, key) == -1) {
    Py_DECREF(it);
    Py_DECREF(key);
    return -1;
  } 
  Py_DECREF(key);
}

С другой стороны, каждый вызов set.add вызывает поиск атрибута, который преобразуется в set_add функцию C, которая, в свою очередь, вызывает set_add_key . Поскольку само добавление элемента происходит относительно быстро (реализация хэш-таблицы в Python очень эффективна), все эти дополнительные вызовы накапливаются.

1. Цикл Python намного ближе по производительности, чем я ожидал, и вы можете стать еще ближе, создав локальную переменную, содержащую ссылку на set.add , и вызывая ее в цикле, избегая поиска атрибута. В моих тестах это было всего на 15% медленнее, чем при использовании set() конструктора!

Ответ №2:

 $ python -V
Python 2.5.2
$ python -m timeit -s "l = range(1000)" "set(l)"
10000 loops, best of 3: 64.6 usec per loop
$ python -m timeit -s "l = range(1000)" "s = set()" "for i in l:s.add(i)"
1000 loops, best of 3: 307 usec per loop

Ответ №3:

На моем Thinkpad:

 In [37]: timeit.timeit('for a in x: y.add(a)',
                       'y=set(); x=range(10000)', number=10000)
Out[37]: 12.18006706237793

In [38]: timeit.timeit('y=set(x)', 'y=set(); x=range(10000)', number=10000)
Out[38]: 3.8137960433959961

Ответ №4:

Вот результаты выполнения сравнения с использованием timeit . Кажется, инициализация набора с использованием списка выполняется быстрее, любопытно узнать, почему это так:

 from timeit import timeit
timeit("set(a)","a=range(10)")
# 0.9944498532640864

timeit("for i in a:x.add(i)","a=range(10);x=set()")
# 1.6878826778265648

Версия Python: 2.7