Mapping std :: map to Python

Question

Иногда имеет смысл иметь словарь с ключом. В C++ это часто реализуется с красно-черным деревом. Но любое самобалансирующееся двоичное дерево поиска будет делать (fwiw, Knuth особенно ясен по этому вопросу). Лучшим решением, которое я смог придумать до сих пор, является принятие R. McGraw's AVL-tree type и создание класса-оболочки, который в основном реализует интерфейс карты STL (также рассчитывая на удобное упорядочение пар (двух элементов кортежей) в Python). Такой кортеж в основном соответствует std :: map :: value_type.

Да, есть модуль Bisect Python, и хотя это логарифмически во время вставки так же, как самобалансирующиеся двоичные деревья логарифмичны во время вставки (справа?), Честно говоря, я просто хочу объект. Вызывается OrderedDict или что-то (и нет, Python 3.1 OrderedDict не подходит - это для заказа «вставки-времени» - и, откровенно говоря, то, что порядок ввода-времени имеет отношение к заказу, не совсем очевидно).

Примечание. Словарь, упорядоченный по ключевым словам, очень полезен во многих отраслях промышленности (например, в финансах, например, для отслеживания ценных книг данных, которые являются в основном упорядоченными словарями цены -> количества, агрегированной информации о заказе и т. Д. .).

Если у кого-то есть другие идеи, это здорово. Все, что я знаю, я только что получил в пять миллионов раз умнее ответы Алекса Мартелли. Поэтому я подумал, что спрошу.

Answer 1

Как вы сказали, вы можете свернуть свою собственную реализацию с Bisect:

class OrderedDict: 
    def __init__(self, keyvalues_iter): 
    self.__srtlst__ = sorted(keyvalues_iter) 
    def __len__(self): 
    return len(self.__srtlst__) 
    def __contains__(self, key): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return True 
    else: 
     return False  
    def __getitem__(self, key): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return self.__srtlst__[index][1] 
    else: 
     raise KeyError(key) 
    def __setitem__(sekf, key, value): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     self.__srtlst__[index][1] = value 
    else: 
     self.__srtlst__[index]=(key, value) 
    def __delitem__(sekf, key, value): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     del __srtlst__[index] 
    else: 
     raise KeyError(key) 
    def __iter__(self): 
    return (v for k,v in self.__srtlst__) 
    def clear(self): 
    self.__srtlst__ = [] 
    def get(self, key, default=None): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return self.__srtlst__[index][1] 
    else: 
     return default 
    def items(self): 
    return self.__srtlst__[:] 
    def iteritems(self): 
    return iter(self.__srtlst__) 
    def iterkeys(self): 
    return (k for k,v in self.__srtlst__) 
    def itervalues(self): 
    return (v for k,v in self.__srtlst__) 
    def keys(self): 
    return [k for k,v in self.__srtlst__] 
    def values(self): 
    return [v for k,v in self.__srtlst__] 
    def setdefault(self, key, default): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return self.__srtlst__[index][1] 
    else: 
     self.__srtlst__[index]=(key, default) 
     return default 
    def update(self, other): 
    #a more efficient implementation could be done merging the sorted lists 
    for k, v in other.iteritems(): 
     self[k] = v 

хммм ... мне кажется, что я уже сделал это за вас, d'ах!

Answer 2

У меня точно такая же потребность, и ответ Алекс Мартелли полностью убедил меня: лучше всего хранить словарь и список частично отсортированных ключей, а затем сортировать по мере необходимости. Это эффективно из-за очень специфического поведения алгоритма сортировки python (AKA Timsort). Key-ordered dict in Python

Я проверил его осуществления и мой, и был его лучшим (потому что он не вставляет в середине списка)

(я настоятельно советую вам прочитать статью, связанную с комментарием АМ о timsort , что является жемчужиной).

Answer 3

Списки являются жалким заменителем дерева.

Вставки должны перемещать весь список вокруг, чтобы освободить место; удаления необходимо переместить список назад. Добавление или удаление материала в пакетном режиме является прекрасным, когда это возможно, но это очень часто бывает, или принимает неестественные искажения, чтобы организовать его. Фундаментальным атрибутом дерева является то, что вставками и удалениями являются O (log n); никакое количество перемотки не превратит O (n) в O (log n).

Вставка элемента в дерево, когда вы уже знаете, куда он собирается идти, - O (1). Эквивалентно, удаление элемента из дерева на основе его узла также равно O (1). std :: map поддерживает оба этих параметра. Это O (n) со списком.

Другим фундаментальным свойством дерева является то, что итерация по диапазону значений равна O (1) для каждой итерации. Объединение списка и dict теряет это, потому что каждая итерация должна выполнять поиск по типу. (Этот подход не имеет такой проблемы.)

Деревья являются одними из самых основных типов данных. Недостаток Python типа контейнера дерева - бородавка. Возможно, существует библиотека сторонних разработчиков, например, одна из которых связана с «Неизвестным», которую я не пытался, поэтому я не могу ручаться за нее), но для нее нет стандартного типа Python.

Answer 4

Для списка, который сортируется, вы можете попробовать модуль heapq.

Answer 5

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

from bisect import * 

class OrderedMap: 
    """Much less efficient than a dict, 
    but keys don't need to be hashable.""" 
    __default_arg = object() 
    def __init__(self, keyvalues_iter = None): 
     self.clear() 
     if keyvalues_iter is not None: 
      self.update(keyvalues_iter) 
    def clear(self): 
     self.__keys = [] 
     self.__values = [] 
    def __index(self, key): 
     if self.__keys: 
      index = bisect(self.__keys, key)-1 
      if self.__keys[index] == key: 
       return index 
     raise KeyError(key) 
    def __len__(self): 
     return len(self.__keys) 
    def __contains__(self, key): 
     try: 
      self.__index(key) 
      return True 
     except KeyError: 
      return False 
    def __getitem__(self, key): 
     index = self.__index(key) 
     return self.__values[index] 
    def __setitem__(self, key, value): 
     try: 
      index = self.__index(key) 
      # exists 
      self.__values[index] = value 
     except KeyError: 
      # new 
      index = bisect(self.__keys, key) 
      self.__keys.insert(index, key) 
      self.__values.insert(index, value) 
    def __delitem__(self, key): 
     index = self.__index(key) 
     self.__keys.pop(index) 
     self.__values.pop(index) 
    def __iter__(self): 
     return iter(self.__keys) 
    def get(self, key, default=__default_arg): 
     try: 
      return self[key] 
     except KeyError: 
      if default != OrderedMap.__default_arg: 
       return default 
      raise 
    def setdefault(self, key, default = None): 
     try: 
      return self[key] 
     except KeyError: 
      if default != OrderedMap.__default_arg: 
       self[key] = default 
       return default 
      raise 
    def items(self): 
     return zip(self.__keys, self.__values) 
    def iteritems(self): 
     return iter((self.__keys[x], self.__values[x]) 
        for x in xrange(len(self))) 
    def keys(self): 
     return self.__keys[:] 
    def iterkeys(self): 
     return iter(self.__keys) 
    def values(self): 
     return self.__values[:] 
    def itervalues(self): 
     return iter(self.__values) 
    def update(self, other): 
     for k, v in other.iteritems(): 
      self[k] = v 
    def __repr__(self): 
     s = ", ".join("%s: %s" % (repr(self.__keys[x]), 
            repr(self.__values[x])) 
         for x in xrange(len(self))) 
     return "OrderedMap{%s}" % (s,) 

Answer 6

Вы могли бы искать SortedCollection: http://code.activestate.com/recipes/577197-sortedcollection/

Answer 7

Питон sortedcontainers модуль обеспечивает тип SortedDict данных для именно этих целей. Он использует измененную структуру данных типа B-дерева и написан на чистом Python. Модуль имеет 100% -ный охват тестирования и часы стресса. Хотя чистый-Python, быстрее C-реализации и имеет performance comparison для резервного копирования.

Потому что это чисто Python, установка ветер с пип:

pip install sortedcontainers 

Тогда вы просто:

from sortedcontainers import SortedDict 
help(SortedDict) 

performance comparison включает в себя довольно полный список альтернативных реализаций. Это стоит посмотреть.