13

In python, is it faster to a) Build a set from a list of n items b) Insert n items into a set?

I found this page (http://wiki.python.org/moin/TimeComplexity) but it did not have enough information to conclude which was faster.

It seems, inserting items one at a time could in the worst case take O(n*n) time (given it uses dicts), and O(n*1) in the average case. Does initializing a set with a list offer any performance improvement?

3
  • 1
    Seems you want to compare building a set from the list against insertion of n items to set, but the first line of question means something different.
    – sateesh
    Apr 29, 2011 at 18:12
  • Oops! thanks for pointing that out sateesh. Apr 29, 2011 at 18:16
  • 3
    It's easy to find out for yourself using timeit.
    – kindall
    Apr 29, 2011 at 18:20

4 Answers 4

22

In terms of O() complexity - it's definitely the same, because both approaches do exactly the same - insert n items into a set.

The difference comes from implementation: One clear advantage of initialization from an iterable is that you save a lot of Python-level function calls - the initialization from a iterable is done wholly on the C level (**).

Indeed, some tests on a list of 5,000,000 random integers shows that adding one by one is slower:

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)

(**) Looking inside the code of sets (Objects/setobject.c), eventually item insertion boils down to a call to set_add_key. When initializing from an iterable, this function is called in a tight C loop:

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

On the other hand, each call to set.add invokes attribute lookup, which resolves to the C set_add function, which in turn calls set_add_key. Since the item addition itself is relatively quick (the hash table implementation of Python is very efficient), these extra calls all build up.

1
  • 3
    The Python loop is much closer in performance than I would have expected, and you can get even closer by creating a local variable containing a reference to set.add and calling that in the loop, avoiding the attribute lookup. In my tests, that was only about 15% slower than using the set() constructor!
    – kindall
    Apr 29, 2011 at 22:02
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
1
  • 3
    You can speedup the 2nd command 2x times by s_add = s.add: python -m timeit -s "l = range(1000)" "s = set(); s_add=s.add" "for i in l:s_add(i)"
    – jfs
    Apr 30, 2011 at 8:33
0

On my 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
0

Here are the results from running the comparison using timeit. Seems initialization of set using list to be faster, curious to know why it is so:

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 version: 2.7

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.