OrderedDict против defddict против dict - программирование

В библиотеке python теперь у нас есть две Python Реализация словарей, которая подклассифицирует dict поверх и родного типа dict.

Защитники Python всегда предпочитали defaultdict использовать dict.setdefault, когда это возможно. Даже doc цитирует, что This technique is simpler and faster than an equivalent technique using dict.setdefault():

Аналогичным образом, поскольку словари не поддерживают порядок, использование OrderedDict с использованием dict, за которым следует сортировка элементов, является предпочтительным, когда это возможно для альтернативного использования.

В приведенном выше случае код определенно чище, но ценой штрафа за производительность.

Отвечая и комментируя один из вопросов уникальный список python на основе элемента, я наткнулся на штраф за производительность над native dict при использовании defaultdict и OrderedDict. Также кажется, что размер данных также не несущественен для преимущества производительности. dict решение есть над другими.

Я верю There should be one-- and preferably only one --obvious way to do it., так что это лучший способ?

Ответы

Ответ 1

Существует не один ответ, а не один истинный и единственный dict. Среди многих переменных это зависит от:

Размер набора данных;
Количество уникальных ключей;
Скорость базового factory для defaultdict;
Скорость OrderDict по сравнению с более поздним этапом заказа;
Версия Python.

Я ненавижу обобщать, но вот некоторые общие черты:

Утверждение This technique is simpler and faster than an equivalent technique using dict.setdefault() просто неверно. Это зависит от данных;
setdefault быстрее и проще с небольшими наборами данных;
defaultdict быстрее для больших наборов данных с более однородными наборами ключей;
setdefault имеет преимущество с более гетерогенными наборами ключей;
эти результаты отличаются для Python 3 и Python 2;
OrderedDict медленнее во всех случаях, кроме алгоритма, который зависит от порядка и порядка, нелегко восстановить или отсортировать;
Python 3 обычно быстрее для большинства операций dict;
Python 3.6 dict теперь упорядочивается по порядку вставки.

Единственная истина: Это зависит! Все три метода полезны.

Вот какой код времени для отображения:

from __future__ import print_function
from collections import defaultdict
from collections import OrderedDict

try:
    t=unichr(100)
except NameError:
    unichr=chr

def f1(li):
    '''defaultdict'''
    d = defaultdict(list)
    for k, v in li:
        d[k].append(v)
    return d.items()

def f2(li):
    '''setdefault'''
    d={}
    for k, v in li:
        d.setdefault(k, []).append(v)
    return d.items()

def f3(li):
    '''OrderedDict'''
    d=OrderedDict()
    for k, v in li:
        d.setdefault(k, []).append(v)
    return d.items()      


if __name__ == '__main__':
    import timeit
    import sys
    print(sys.version)
    few=[('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
    fmt='{:>12}: {:10.2f} micro sec/call ({:,} elements, {:,} keys)'
    for tag, m, n in [('small',5,10000), ('medium',20,1000), ('bigger',1000,100), ('large',5000,10)]:
        for f in [f1,f2,f3]:
            s = few*m
            res=timeit.timeit("{}(s)".format(f.__name__), setup="from __main__ import {}, s".format(f.__name__), number=n)
            st=fmt.format(f.__doc__, res/n*1000000, len(s), len(f(s)))
            print(st)
            s = [(unichr(i%0x10000),i) for i in range(1,len(s)+1)]
            res=timeit.timeit("{}(s)".format(f.__name__), setup="from __main__ import {}, s".format(f.__name__), number=n)
            st=fmt.format(f.__doc__, res/n*1000000, len(s), len(f(s)))
            print(st)            
        print()

Результат Python 2.7:

2.7.5 (default, Aug 25 2013, 00:04:04) 
[GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.0.68)]
 defaultdict:      10.20 micro sec/call (25 elements, 3 keys)
 defaultdict:      21.08 micro sec/call (25 elements, 25 keys)
  setdefault:      13.41 micro sec/call (25 elements, 3 keys)
  setdefault:      18.24 micro sec/call (25 elements, 25 keys)
 OrderedDict:      49.47 micro sec/call (25 elements, 3 keys)
 OrderedDict:     102.16 micro sec/call (25 elements, 25 keys)

 defaultdict:      28.28 micro sec/call (100 elements, 3 keys)
 defaultdict:      79.78 micro sec/call (100 elements, 100 keys)
  setdefault:      45.68 micro sec/call (100 elements, 3 keys)
  setdefault:      68.66 micro sec/call (100 elements, 100 keys)
 OrderedDict:     117.78 micro sec/call (100 elements, 3 keys)
 OrderedDict:     343.17 micro sec/call (100 elements, 100 keys)

 defaultdict:    1123.60 micro sec/call (5,000 elements, 3 keys)
 defaultdict:    4250.44 micro sec/call (5,000 elements, 5,000 keys)
  setdefault:    2089.86 micro sec/call (5,000 elements, 3 keys)
  setdefault:    3803.03 micro sec/call (5,000 elements, 5,000 keys)
 OrderedDict:    4399.16 micro sec/call (5,000 elements, 3 keys)
 OrderedDict:   16279.14 micro sec/call (5,000 elements, 5,000 keys)

 defaultdict:    5609.39 micro sec/call (25,000 elements, 3 keys)
 defaultdict:   25351.60 micro sec/call (25,000 elements, 25,000 keys)
  setdefault:   10267.00 micro sec/call (25,000 elements, 3 keys)
  setdefault:   24091.51 micro sec/call (25,000 elements, 25,000 keys)
 OrderedDict:   22091.98 micro sec/call (25,000 elements, 3 keys)
 OrderedDict:   94028.00 micro sec/call (25,000 elements, 25,000 keys)

Результат Python 3.3:

3.3.2 (default, May 21 2013, 11:50:47) 
[GCC 4.2.1 Compatible Apple Clang 4.1 ((tags/Apple/clang-421.11.66))]
 defaultdict:       8.58 micro sec/call (25 elements, 3 keys)
 defaultdict:      21.18 micro sec/call (25 elements, 25 keys)
  setdefault:      10.42 micro sec/call (25 elements, 3 keys)
  setdefault:      14.58 micro sec/call (25 elements, 25 keys)
 OrderedDict:      45.43 micro sec/call (25 elements, 3 keys)
 OrderedDict:      92.69 micro sec/call (25 elements, 25 keys)

 defaultdict:      20.47 micro sec/call (100 elements, 3 keys)
 defaultdict:      77.48 micro sec/call (100 elements, 100 keys)
  setdefault:      34.22 micro sec/call (100 elements, 3 keys)
  setdefault:      54.86 micro sec/call (100 elements, 100 keys)
 OrderedDict:     107.37 micro sec/call (100 elements, 3 keys)
 OrderedDict:     318.98 micro sec/call (100 elements, 100 keys)

 defaultdict:     714.70 micro sec/call (5,000 elements, 3 keys)
 defaultdict:    3892.92 micro sec/call (5,000 elements, 5,000 keys)
  setdefault:    1502.91 micro sec/call (5,000 elements, 3 keys)
  setdefault:    2888.08 micro sec/call (5,000 elements, 5,000 keys)
 OrderedDict:    3912.95 micro sec/call (5,000 elements, 3 keys)
 OrderedDict:   14863.02 micro sec/call (5,000 elements, 5,000 keys)

 defaultdict:    3649.02 micro sec/call (25,000 elements, 3 keys)
 defaultdict:   22313.17 micro sec/call (25,000 elements, 25,000 keys)
  setdefault:    7447.28 micro sec/call (25,000 elements, 3 keys)
  setdefault:   18426.88 micro sec/call (25,000 elements, 25,000 keys)
 OrderedDict:   19202.17 micro sec/call (25,000 elements, 3 keys)
 OrderedDict:   85946.45 micro sec/call (25,000 elements, 25,000 keys)

Ответ 2

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

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

а в

реализация критического критически важного алгоритма в обработке данных, я бы не прочь написать немного более подробный код для более быстрого выполнения. Если алорифм вряд ли изменится, мало понятный код не станет проблемой.