DjangoBB LoFi version

Полная версия: Покататься на велосипеде или OrderedDict по-другому

Начало » Python для новичков » Покататься на велосипеде или OrderedDict по-другому

beelze

Апрель 26, 2012 00:35:37

Всем известен недостаток стандартного объекта dict - элементы в нем не имеют порядка. Этого недостатка лишен collections.OrderedDict, однако его функционал ограничен и не поддерживает никаких операций над взаимным расположением элементов. Посему, попав в ситуацию, где необходим такой тип данных, показалось логичным его создать. Стандартный dict-функционал и интерфейс остался (надеюсь) без изменений, в примере я привел только расширение оного (по большей части). Приглашаю всех желающих обсудить, покритиковать и поделиться полезными замечаниями. Риторические вопросы типа «а зачем это надо» (без приведения альтернатив) будут приветствоваться соответствующим образом.

вот, собственно, самокат

а вот как бы пример:

X = xOrderedDict(('a', 1), ('b', 2), ('c', 3), ('d', 4))
print X                                     # xOrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])
del X['c']
print X                                     # xOrderedDict([('a', 1), ('b', 2), ('d', 4)])
del X[('a', 'b')]
print X                                     # xOrderedDict([('d', 4)])
X.insert([0], ('a', 1))
X.insert([-1], ('b', 2), ('c', 3))
X.insert('b', ('e', 4))                     # xOrderedDict([('a', 1), ('d', 4), ('e', 4), ('b', 2), ('c', 3)])
# X.insert([0], ('a', 1))                   # KeyError: "Duplicate key(s): ['a']"
print X
X.move([-1], 'e', 'a')                      # xOrderedDict([('d', 4), ('b', 2), ('c', 3), ('e', 4), ('a', 1)])
print X
print X.keyof(2), X.keyof(-1), X.indexof('a'), X.indexof('z', 100500)
                                            # c a 4 100500
import pickle, StringIO
s = StringIO.StringIO()
pickle.dump(X, s)
Y = pickle.load(StringIO.StringIO(s.getvalue()))
print X==Y, Y                               # True xOrderedDict([('d', 4), ('b', 2), ('c', 3), ('e', 4), ('a', 1)])                
Y.move([0], 'a')
print X==Y                                  # False

vkopey

Апрель 26, 2012 19:06:21

А почему нельзя использовать для этого list ?
Ведь стандартный list и dict хорошо оптимизированы.

ls=[('a',1),('b',2)] # ordered список-словарь
lsk=[x[0] for x in ls] # список ключей
print ls[lsk.index('b')][1] # значение по ключу

Кстати сравните быстродействие этих вариантов.

beelze

Апрель 26, 2012 19:46:37

vkopey, безусловно, лист можно использовать, однако целью создания этого типа данных являлось именно расширение стандартного словаря, по-максимуму используя его имеющуюся функциональность, что, впрочем, общая практика. В Вашем примере для реализации стандартного «словарного» интерфейса придется не только реализовать большую часть его методов, но еще и поиск по ключу/соблюдение его уникальности (базовая операция словаря) - вследствие чего о быстродействии и оптимизации можно точно будет забыть. Ибо прямой перебор значений - это самый неэффективный метод поиска, а я полагаю, что иного тут без введения индекса в самом его общем смысле - не выйдет.
Собственно по быстродействию - полагаю, что более-менее корректным можно считать только сравнение с collections.OrderedDict, но для стандартных общих операций разница будет минимальной, ибо и там и здесь «надслойка» минимальна и не включает «дорогостоящий» код