Индексируемое слабое упорядоченное множество в Python - PullRequest
Новая
       5

Индексируемое слабое упорядоченное множество в Python

10 голосов
/ 20 октября 2011

Мне было интересно, есть ли простой способ построить индексируемый слабо упорядоченный набор в Python. Я пытался построить один сам. Вот что я придумал: 

"""
An indexable, ordered set of objects, which are held by weak reference.
"""
from nose.tools import *
import blist
import weakref


class WeakOrderedSet(blist.weaksortedset):
    """
    A blist.weaksortedset whose key is the insertion order.
    """
    def __init__(self, iterable=()):
        self.insertion_order = weakref.WeakKeyDictionary()  # value_type to int
        self.last_key = 0
        super().__init__(key=self.insertion_order.__getitem__)
        for item in iterable:
            self.add(item)

    def __delitem__(self, index):
        values = super().__getitem__(index)
        super().__delitem__(index)
        if not isinstance(index, slice):
            # values is just one element
            values = [values]
        for value in values:
            if value not in self:
                del self.insertion_order[value]

    def add(self, value):
        # Choose a key so that value is on the end.
        if value not in self.insertion_order:
            key = self.last_key
            self.last_key += 1
            self.insertion_order[value] = key
        super().add(value)

    def discard(self, value):
        super().discard(value)
        if value not in self:
            del self.insertion_order[value]

    def remove(self, value):
        super().remove(value)
        if value not in self:
            del self.insertion_order[value]

    def pop(self, *args, **kwargs):
        value = super().pop(*args, **kwargs)
        if value not in self:
            del self.insertion_order[value]

    def clear(self):
        super().clear()
        self.insertion_order.clear()

    def update(self, *args):
        for arg in args:
            for item in arg:
                self.add(item)


if __name__ == '__main__':
    class Dummy:
        def __init__(self, value):
            self.value = value

    x = [Dummy(i) for i in range(10)]
    w = WeakOrderedSet(reversed(x))
    del w[2:8]
    assert_equals([9,8,1,0], [i.value for i in w])
    del w[0]
    assert_equals([8,1,0], [i.value for i in w])
    del x
    assert_equals([], [i.value for i in w])

Есть ли более простой способ сделать это?

Ответы [ 2 ]

25 голосов
/ 20 октября 2011

Самый простой способ - воспользоваться существующими компонентами в стандартной библиотеке.

OrderedDict и MutableSet ABC сделать егоЛегко написать OrderedSet.

Аналогично, вы можете повторно использовать существующий слабый_файл.WeakSet и заменить его базовый set () на OrderedSet.

Индексирование труднее достичь - это самый простой способ преобразовать его в список при необходимости.Это необходимо, потому что наборы и дикты по сути своей редки. 

import collections.abc
import weakref

class OrderedSet(collections.abc.MutableSet):
    def __init__(self, values=()):
        self._od = collections.OrderedDict().fromkeys(values)
    def __len__(self):
        return len(self._od)
    def __iter__(self):
        return iter(self._od)
    def __contains__(self, value):
        return value in self._od
    def add(self, value):
        self._od[value] = None
    def discard(self, value):
        self._od.pop(value, None)

class OrderedWeakrefSet(weakref.WeakSet):
    def __init__(self, values=()):
        super(OrderedWeakrefSet, self).__init__()
        self.data = OrderedSet()
        for elem in values:
            self.add(elem)

Используйте его так: 

>>> names = OrderedSet(['Alice', 'Bob', 'Carol', 'Bob', 'Dave', 'Edna'])
>>> len(names)
5
>>> 'Bob' in names
True
>>> s = list(names)
>>> s[2]
'Carol'
>>> s[4]
'Edna'

Обратите внимание, что в Python 3.7 гарантированно заказываются обычные дикты, поэтому выможет заменить dict на OrderedDict в этом рецепте, и все будет работать нормально: -)

1 голос
/ 07 февраля 2016

У Раймонда, как обычно, отличный и лаконичный ответ, но я действительно пришел сюда некоторое время назад, интересуясь индексируемой частью, а не слабой частью. В конце концов я создал свой собственный ответ, который стал типом IndexedSet в служебной библиотеке boltons . По сути, это все лучшие части API list и set, вместе взятые. 

>>> x = IndexedSet(list(range(4)) + list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'

Если слабая часть критична, вы, вероятно, можете добавить ее с помощью наследования или прямого изменения копии кода (модуль является автономным, полностью совместимым с Python и 2/3).

...