Key-ordered dict в Python

Я ищу надежную реализацию упорядоченного ассоциативного массива, то есть упорядоченного словаря. Я хочу упорядочить с точки зрения ключей, а не порядка вставки.

Точнее, я ищу пространственно-эффективную реализацию структуры отображения int-to-float (или string-to-float для другого использования), для которой:

Упорядоченная итерация - это O (n)
Случайный доступ - O (1)

Лучшее, что я придумал, - склеить диктофон и список ключей, сохраняя последнее, заказанное с помощью деления пополам и вставки.

Любые лучшие идеи?

Ответ 1

"Случайный доступ O (1)" является чрезвычайно требовательным требованием, которое в основном накладывает основную хеш-таблицу - и я надеюсь, что вы действительно имеете в виду случайные ЧТЕНИЯ, потому что я думаю, что это может быть математически доказано, чем это невозможно в общем случае для записи O (1), а также упорядоченной итерации O (N).

Я не думаю, что вы найдете предварительно упакованный контейнер, соответствующий вашим потребностям, потому что они настолько экстремальны - доступ к O (log N), конечно же, будет иметь большое значение в мире. Чтобы получить поведение большого вывода, которое требуется для чтения и итераций, вам нужно приклеить две структуры данных, по существу, диктовку и кучу (или отсортированный список или дерево) и синхронизировать их. Хотя вы не указываете, я думаю, что вы получите только амортизированное поведение, которое вы хотите, - если вы действительно не готовы платить за достижения производительности за вставки и удаления, что является буквальным следствием спецификаций, которые вы выражаете, но кажется довольно маловероятным реальным требованием.

Для O (1) чтения и амортизации O (N) упорядоченной итерации просто сохраните список всех ключей на стороне dict. Например:.

class Crazy(object):
  def __init__(self):
    self.d = {}
    self.L = []
    self.sorted = True
  def __getitem__(self, k):
    return self.d[k]
  def __setitem__(self, k, v):
    if k not in self.d:
      self.L.append(k)
      self.sorted = False
    self.d[k] = v
  def __delitem__(self, k):
    del self.d[k]
    self.L.remove(k)
  def __iter__(self):
    if not self.sorted:
      self.L.sort()
      self.sorted = True
    return iter(self.L)

Если вам не нравится "амортизированный O (N) порядок", вы можете удалить self.sorted и просто повторить self.L.sort() в __setitem__. Это делает записи O (N log N), конечно (пока я все еще писал в O (1)). Любой подход является жизнеспособным, и трудно думать об одном как по существу превосходящем другого. Если вы склонны делать кучу записей, тогда куча итераций, то подход в коде выше лучше всего; если это обычно одна запись, одна итерация, другая запись, другая итерация, тогда это просто стирка.

Кстати, это приводит к бесстыдному преимуществу необычных (и замечательных;) характеристик производительности Python sort (aka "timsort" ): среди них сортировка списка, который в основном сортируется, но с несколькими дополнительными элементами, прикрепленными в конце в основном O (N) (если привязанные к элементам несколько достаточно по сравнению с сортированной частью префикса). Я слышал, что Java скоро набирает этот вид, так как Josh Block был настолько впечатлен технологическим разговором о Python, что он начал кодировать его для JVM на своем ноутбуке тогда и там. Большинство систем (в том числе я считаю, что Jython на сегодняшний день и IronPython тоже) в основном сортируют как операцию O (N log N), не используя преимущества "в основном упорядоченных" входов; "естественное объединение", которое Тим Петерс ввел сегодня в Python timsort, удивляет в этом отношении.

Ответ 2

Модуль sortedcontainers предоставляет SortedDict, который соответствует вашим требованиям. Он в основном склеивает SortedList и тип dict вместе. Функция dict обеспечивает O (1) поиск, а SortedList обеспечивает O (N) итерацию (это очень быстро). Весь модуль является чистым-Python и имеет эталонные графики для резервного копирования заявлений о производительности (реализации fast-as-C). SortedDict также полностью протестирован со 100% покрытием и часами стресса. Он совместим с Python 2.6 до 3.4.

Ответ 3

Вот моя собственная реализация:

import bisect
class KeyOrderedDict(object):
   __slots__ = ['d', 'l']
   def __init__(self, *args, **kwargs):
      self.l = sorted(kwargs)
      self.d = kwargs

   def __setitem__(self, k, v):
      if not k in self.d:
         idx = bisect.bisect(self.l, k)
         self.l.insert(idx, k)
       self.d[k] = v

   def __getitem__(self, k):
      return self.d[k]

   def __delitem__(self, k):
      idx = bisect.bisect_left(self.l, k)
      del self.l[idx]
      del self.d[k]

   def __iter__(self):
      return iter(self.l)

   def __contains__(self, k):
      return k in self.d

Использование bisect сохраняет self.l, а вставка - O (n) (из-за вставки, но не убийцы в моем случае, потому что я добавляю гораздо чаще, чем по-настоящему вставлять, поэтому обычный случай амортизируется O (1)). Доступ - O (1) и итерация O (n). Но может быть, кто-то придумал (в С) что-то с более умной структурой?

Ответ 4

Приведенное дерево обычно лучше для этих случаев, но произвольный доступ будет log (n). Вы должны также учитывать затраты на вставку и удаление...

Ответ 5

Вы можете построить dict, который позволяет обход, сохраняя пару (value, next_key) в каждой позиции.

Случайный доступ:

my_dict[k][0]   # for a key k

Traversal:

k = start_key   # stored somewhere
while k is not None:     # next_key is None at the end of the list
    v, k = my_dict[k]
    yield v

Сохраняйте указатель на start и end, и у вас будет эффективное обновление для тех случаев, когда вам просто нужно добавить в конец списка.

Вставка в середине, очевидно, O (n). Возможно, вы могли бы построить список пропуска, если вам нужна более высокая скорость.

Ответ 6

Я не уверен, в какой версии python вы работаете, но если вам нравится экспериментировать, Python 3.1 включает и официальную реализацию упорядоченных словарей: http://www.python.org/dev/peps/pep-0372/ http://docs.python.org/3.1/whatsnew/3.1.html#pep-372-ordered-dictionaries

Ответ 7

Пакет упорядоченного пакета (http://anthon.home.xs4all.nl/Python/ordereddict/), который я реализовал в 2007 году, включает в себя sorteddict. sorteddict - словарь KSO (Key Sorted Order). Он реализован в C и очень эффективен в пространстве и в несколько раз быстрее, чем чистая реализация Python. Недостатком является то, что работает только с CPython.

>>> from _ordereddict import sorteddict
>>> x = sorteddict()
>>> x[1] = 1.0
>>> x[3] = 3.3
>>> x[2] = 2.2
>>> print x
sorteddict([(1, 1.0), (2, 2.2), (3, 3.3)])
>>> for i in x:
...    print i, x[i]
... 
1 1.0
2 2.2
3 3.3
>>>

Извините за поздний ответ, может быть, этот ответ поможет другим найти эту библиотеку.

Ответ 8

вот пастель: у меня была потребность в чем-то подобном. Обратите внимание, однако, что эта конкретная реализация неизменна, при создании экземпляра нет вставок. Точная производительность не совсем соответствует тому, что вы просите. Поиск - O (log n), а полное сканирование - O (n). Это работает с использованием модуля bisect по кортелям пар ключ/значение (кортеж). Даже если вы не можете использовать это точно, у вас может быть некоторый успех, адаптировав его к вашим потребностям.

import bisect

class dictuple(object):
    """
        >>> h0 = dictuple()
        >>> h1 = dictuple({"apples": 1, "bananas":2})
        >>> h2 = dictuple({"bananas": 3, "mangoes": 5})
        >>> h1+h2
        ('apples':1, 'bananas':3, 'mangoes':5)
        >>> h1 > h2
        False
        >>> h1 > 6
        False
        >>> 'apples' in h1
        True
        >>> 'apples' in h2
        False
        >>> d1 = {}
        >>> d1[h1] = "salad"
        >>> d1[h1]
        'salad'
        >>> d1[h2]
        Traceback (most recent call last):
        ...
        KeyError: ('bananas':3, 'mangoes':5)
   """


    def __new__(cls, *args, **kwargs):
        initial = {}
        args = [] if args is None else args
        for arg in args:
            initial.update(arg)
        initial.update(kwargs)

        instance = object.__new__(cls)
        instance.__items = tuple(sorted(initial.items(),key=lambda i:i[0]))
        return instance

    def __init__(self,*args, **kwargs):
        pass

    def __find(self,key):
        return bisect.bisect(self.__items, (key,))


    def __getitem__(self, key):
        ind = self.__find(key)
        if self.__items[ind][0] == key:
            return self.__items[ind][1]
        raise KeyError(key)
    def __repr__(self):
        return "({0})".format(", ".join(
                        "{0}:{1}".format(repr(item[0]),repr(item[1]))
                          for item in self.__items))
    def __contains__(self,key):
        ind = self.__find(key)
        return self.__items[ind][0] == key
    def __cmp__(self,other):

        return cmp(self.__class__.__name__, other.__class__.__name__
                  ) or cmp(self.__items, other.__items)
    def __eq__(self,other):
        return self.__items == other.__items
    def __format__(self,key):
        pass
    #def __ge__(self,key):
    #    pass
    #def __getattribute__(self,key):
    #    pass
    #def __gt__(self,key):
    #    pass
    __seed = hash("dictuple")
    def __hash__(self):
        return dictuple.__seed^hash(self.__items)
    def __iter__(self):
        return self.iterkeys()
    def __len__(self):
        return len(self.__items)
    #def __reduce__(self,key):
    #    pass
    #def __reduce_ex__(self,key):
    #    pass
    #def __sizeof__(self,key):
    #    pass

    @classmethod
    def fromkeys(cls,key,v=None):
        cls(dict.fromkeys(key,v))

    def get(self,key, default):
        ind = self.__find(key)
        return self.__items[ind][1] if self.__items[ind][0] == key else default

    def has_key(self,key):
        ind = self.__find(key)
        return self.__items[ind][0] == key

    def items(self):
        return list(self.iteritems())

    def iteritems(self):
        return iter(self.__items)

    def iterkeys(self):
        return (i[0] for i in self.__items)

    def itervalues(self):
        return (i[1] for i in self.__items)

    def keys(self):
        return list(self.iterkeys())

    def values(self):
        return list(self.itervalues())
    def __add__(self, other):
        _sum = dict(self.__items)
        _sum.update(other.__items)
        return self.__class__(_sum)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

Ответ 9

Для проблемы "string to float" вы можете использовать Trie - он обеспечивает время доступа O (1) и O (n) отсортированную итерацию. По "сортировке" я имею в виду "сортировку по алфавиту с помощью ключа" - кажется, что вопрос подразумевает одно и то же.

Некоторые реализации (каждая со своими сильными и слабыми точками):

https://github.com/biopython/biopython имеет модуль Bio.trie с полнофункциональным Trie; другие пакеты Trie более полезны для памяти;
https://github.com/kmike/datrie - случайные вставки могут быть медленными, алфавит алфавита должен быть известен заранее;
https://github.com/kmike/hat-trie - все операции выполняются быстро, но многие методы dict не реализованы; базовая библиотека C поддерживает отсортированную итерацию, но она не реализована в оболочке;
https://github.com/kmike/marisa-trie - очень эффективная память, но не поддерживает вставки; Итерация не сортируется по умолчанию, но может быть отсортирована (есть пример в документах);
https://github.com/kmike/DAWG - можно рассматривать как минимизированное Trie; очень быстрая и эффективная память, но не поддерживает вставки; имеет ограничения по размеру (несколько ГБ данных).