Вопрос по python, data-structures, collections, dictionary – Диктофон с ключом в Python

26

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

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

Упорядоченная итерация O (n)Произвольный доступ O (1)

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

Есть идеи получше?

@Ned: Понятия не имею, что это значит. int - это ключи, а float - это значения, или нет? Можно'Понять, почему для этого нужен словарь, отсортированный по ключу. " hughdbrown
Я должен изменить содержание на основе ввода пользователя. Примерно в 70% случаев это просто вопрос добавления ключа (последний по порядку), но иногда случается, что мне приходится вставлять / удалять средний. LeMiz
И ты можешьт просто сделать преобразование как требуется? Вам нужно кешировать результаты на потом? И требования к производительности необходимы, потому что это было признано узким местом? hughdbrown
@Ned: Спасибо за разъяснения, я не уловил недоразумение. LeMiz

Ваш Ответ

10   ответов
0

Один вариант, который не был упомянут в других ответах, я думаю:

Использовать двоичное дерево поиска (Treар /AVL /RB) чтобы сохранить отображение.Также используйте hashmap (он же словарь), чтобы сохранить то же отображение (снова).

Это обеспечитНа) упорядоченный обход (через дерево),O (1) произвольный доступ (через хэш-карту) иO (log n) вставка / удаление (потому что вам нужно обновить как дерево, так и хеш).

Недостатком является необходимость хранить все данные дважды, однако альтернативы, которые предлагают хранить список ключей вместе с хэш-картой, не намного лучше в этом смысле.

5

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

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). Но, может быть, кто-то изобрел (на С) что-то с более умной структурой?

0

s a pastie: мне нужно было нечто подобное. Однако обратите внимание, что эта конкретная реализация является неизменной, после создания экземпляра вставок нет: Точная производительность не меняетсяне совсем соответствует тому, что тыпросим, однако. Поиск - 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()
1

Упорядоченный пакет (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

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

1

(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). Возможно, вы могли бы построитьпропустить список Кроме того, если вам нужно больше скорости.

Очевидно, что вы также можете хранить указатель на предыдущий элемент, что облегчит вставку / удаление из середины, особенно если вы делаете слой с пропуском списка сверху. John Fouhy
4

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

это кажется интересной реализацией отсортированного дерева AVL:pyavl.sourceforge.net fortran
Есть ли у вас предложенная реализация (желательно с хорошей документацией, особенно для угловых случаев)? LeMiz
Спасибо за ссылку. Сначала я подумал, что было бы много модификаций, чтобы использовать его в качестве ассоциативного массива (если бы я отказался от требования иметь O (1) время произвольного доступа). LeMiz
0

строка, чтобы плавать " Проблема, которую вы можете использовать в 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 - очень эффективная память, но неt поддержка вставок; итерация не сортируется по умолчанию, но может быть отсортирована (пример есть в документации);https://github.com/kmike/DAWG - можно рассматривать как минимизированное Trie; очень быстро и эффективно использует память, но неt поддержка вставок; имеет ограничения по размеру (несколько ГБ данных)
1

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

Упорядоченные словари упорядочены относительно вставки ключей, а не порядка сортировки ключей, поэтому я неЯ думаю, что LeMiz сможет использовать это решение. SingleNegationElimination
Упс, прости. Я заблудился в вопросе ... Santi
28

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

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

Для 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)). Любой подход жизнеспособен, и этоТрудно представить, что одно по сути превосходит другое. Если вы склонны делать кучу записей, то кучу итераций, тогда подход в приведенном выше коде является лучшим; если оно's обычно одна запись, одна итерация, другая запись, другая итерация, затемПросто мыть.

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

@ LeMiz, не надоНе беспокойтесь о дублировании больших ключей: self.L и self.d - просто наборы ссылок на одни и те же ключевые объекты, копии этих объектов не существует. Alex Martelli
Я убежден :). Чтение газеты о тимсорте имело большое значение, и я был бы рад задать вопрос хотя бы для него. Кстати, если я могу злоупотреблять вашим временем, сколько места стоит ссылка на объект в списке? 16 байт? (Может быть, я должен задать это как еще один вопрос). Спасибо за ваши очень точные ответы! LeMiz
У меня почти то же самое, но с __setitem __ (self, k, v): если не k в self.d: idx = bisect.bisect (self.l, k) # log (n) self.l.insert ( idx, k) # сохраняет список отсортированным self.d [k] = v Это предотвращаетгрязный» флаг вещь. Есть ли документ, подробно описывающий сортировку Python (если нет, я прочитаю исходный код). Но мой вопрос был на самом деле о том, как предотвратить дублирование списка ключей (например, если хеш короткий, может быть предпочтительнее дублировать только хеш вместо длинных). Спасибо за понимание Python, хотя. LeMiz
@LeMiz, тыДобро пожаловать! Ссылка сама по себе занимает 4 байта в 32-битной сборке Python, 8 - в 64-битной; Помимо этого, я считаю, что был бы целесообразен новый вопрос (например, о том, как вы измеряете вещи, как вы сжимаете их, когда ОЧЕНЬ жестко, и так далее ;-). Alex Martelli

Похожие вопросы