Why is OrderedDict () ~ 10x slower than dict () and list ()?

Question

Just run the tests below and notice that filling OrderedDict() about an order of magnitude slower than filling dict() or list() .

Why?

 # list() In [1]: timeit test_list() 1000 loops, best of 3: 298 us per loop # dict() In [3]: timeit test_dict() 1000 loops, best of 3: 269 us per loop # dict() In [3]: timeit test_ord_dict() 100 loops, best of 3: 1.77 ms per loop 

from:

 def test_ord_dict(): a = OrderedDict() for el in xrange(1000): a[el] = np.random.randint(100) return a def test_dict(): a = dict() for el in xrange(1000): a[el] = np.random.randint(100) return a def test_list(): a = list() for el in xrange(1000): a.append(np.random.randint(100)) return a 

Answer 1

OrderedDict implemented in pure Python, so here is the corresponding part of the source:

 def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 'od.__setitem__(i, y) <==> od[i]=y' # Setting a new item creates a new link at the end of the linked list, # and the inherited dictionary is updated with the new key/value pair. if key not in self: root = self.__root last = root[0] last[1] = root[0] = self.__map[key] = [last, root, key] return dict_setitem(self, key, value) 

If the key does not exist, you will create a new list and get access to two elements from the list, which will slow down the work.

Answer 2

Two reasons:

• An OrderedDict , by definition, should do more work than a dict .

• (which is much more important) OrderedDict written in Python , and dict and list are written in C.