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

Question

В python это быстрее: а) создать набор из списка из n элементов; б) вставить n элементов в набор?

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

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

Answer 1

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

Различие заключается в реализации: одно явное преимущество инициализациииз итерируемого является то, что вы сохраняете много вызовов функций уровня Python - инициализация из итерируемого выполняется полностью на уровне 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.При инициализации из итерируемого эта функция вызывается в узком цикле 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 вызывает поиск атрибута, который преобразуется в функцию C set_add,что в свою очередь вызывает set_add_key.Поскольку само добавление элементов относительно быстрое (реализация Python для хэш-таблицы очень эффективна), все эти дополнительные вызовы накапливаются.

Answer 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

Answer 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

Answer 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