Коллекция ключей в Python?

Question

Есть ли какой-либо эквивалент KeyedCollection в Python, т. Е. Набор, в котором элементы имеют (или динамически генерируют) свои собственные ключи?

т.е. цель здесь состоит в том, чтобы избежатьхранение ключа в двух местах , и поэтому словари не идеальны (отсюда и вопрос).

Answer 1

Вы можете смоделировать это очень легко:

class KeyedObject(object):
    def get_key(self):
        raise NotImplementedError("You must subclass this before you can use it.")

class KeyedDict(dict):
    def append(self, obj):
        self[obj.get_key()] = obj

Теперь вы можете использовать KeyedDict вместо dict с подклассами KeyedObject (где get_key возвращает действительный ключ на основе некоторого свойства объекта).

Answer 2

Учитывая ваши ограничения, каждый, кто пытается реализовать то, что вы ищете, используя dict, лает не на то дерево. Вместо этого вы должны написать list подкласс, который переопределяет __getitem__, чтобы обеспечить желаемое поведение. Я написал это так, что сначала он пытается получить нужный элемент по индексу, а затем возвращается к поиску элемента по атрибуту key содержащихся объектов. (Это может быть свойство, если объект должен определять это динамически.)

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

class KeyedCollection(list):
     def __getitem__(self, key):
         if isinstance(key, int) or isinstance(key, slice):
             return list.__getitem__(key)
         for item in self:
             if getattr(item, "key", 0) == key:
                 return item
         raise KeyError('item with key `%s` not found' % key)

Возможно, вы также захотите переопределить __contains__ аналогичным образом, чтобы вы могли сказать if "key" in kc.... Если вы хотите сделать его еще более похожим на dict, вы также можете реализовать keys() и так далее. Они будут одинаково неэффективны, но у вас будет такой API, как dict, который также работает как список.

Answer 3

@ Mehrdad сказал:

Потому что семантически, это не имеет особого смысла.Когда объект знает свой ключ, нет смысла помещать его в словарь - это не пара ключ-значение.Это больше семантическая проблема, чем что-либо еще.

С этим ограничением в Python нет ничего, что делало бы то, что вы хотите.Я предлагаю вам использовать диктовку и не беспокоиться об этом уровне детализации семантики.Ответ @Gabi Purcaru показывает, как вы можете создать объект с нужным вам интерфейсом.Зачем беспокоиться о том, как это работает внутри?

Может случиться так, что KeyedCollection в C # делает то же самое под прикрытием: запрашивает объект у его ключа и затем сохраняет ключ для быстрого доступа.На самом деле, из документов:

По умолчанию KeyedCollection (Of TKey, TItem) включает словарь поиска, который можно получить с помощью свойства Dictionary.Когда элемент добавляется в KeyedCollection (Of TKey, TItem), ключ элемента извлекается один раз и сохраняется в словаре поиска для ускорения поиска.Это поведение переопределяется путем указания порога создания словаря при создании KeyedCollection (Of TKey, TItem).Словарь поиска создается в первый раз, когда количество элементов превышает этот порог.Если в качестве порога указать -1, поисковый словарь никогда не будет создан.

Answer 4

Я не очень люблю C # 'er, но я думаю, что словари - это то, что вам нужно.

http://docs.python.org/tutorial/datastructures.html#dictionaries

http://docs.python.org/tutorial/datastructures.html

Или, может быть, списки:

http://docs.python.org/library/functions.html#list

Answer 5

Чтобы немного подробнее узнать, что уже правильный ответ из ответа @Gabi Purcaru, здесь класс, который делает то же самое, что и gabi one, но также проверяет правильность заданного типа по ключу и значению (как TKey и TValue для .net KeyedCollection).

class KeyedCollection(MutableMapping):
    """
    Provides the abstract base class for a collection (:class:`MutableMappinp`) whose keys are embedded in the values.
    """
    __metaclass__ = abc.ABCMeta
    _dict = None  # type: dict

    def __init__(self, seq={}):
        self._dict = dict(seq)

    @abc.abstractmethod
    def __is_type_key_correct__(self, key):
        """
        Returns: The type of keys in the collection
        """
        pass

    @abc.abstractmethod
    def __is_type_value_correct__(self, value):
        """
        Returns: The type of values in the collection
        """
        pass

    @abc.abstractmethod
    def get_key_for_item(self, value):
        """
        When implemented in a derivated class, extracts the key from the specified element.
        Args:
            value: the element from which to extract the key (of type specified by :meth:`type_value`)

        Returns: The key of specified element (of type specified by :meth:`type_key`)
        """
        pass

    def __assert_type_key(self, key, arg_name='key'):
        if not self.__is_type_key_correct__(key) :
            raise ValueError("{} type is not correct".format(arg_name))

    def __assert_type_value(self, value, arg_name='value'):
        if not self.__is_type_value_correct__(value) :
            raise ValueError("{} type is not correct".format(arg_name))

    def add(self, value):
        """
        Adds an object to the KeyedCollection.
        Args:
            value: The object to be added to the KeyedCollection (of type specified by :meth:`type_value`).
        """
        key = self.get_key_for_item(value)
        self._dict[key] = value

    # Implements abstract method __setitem__ from MutableMapping parent class
    def __setitem__(self, key, value):
        self.__assert_type_key(key)
        self.__assert_type_value(value)
        if value.get_key() != key:
            raise ValueError("provided key does not correspond to the given KeyedObject value")
        self._dict[key] = value

    # Implements abstract method __delitem__ from MutableMapping parent class
    def __delitem__(self, key):
        self.__assert_type_key(key)
        self._dict.pop(key)

    # Implements abstract method __getitem__ from MutableMapping parent class (Mapping base class)
    def __getitem__(self, key):
        self.__assert_type_key(key)
        return self._dict[key]

    # Implements abstract method __len__ from MutableMapping parent class (Sized mixin on Mapping base class)
    def __len__(self):
        return len(self._dict)

    # Implements abstract method __iter__ from MutableMapping parent class (Iterable mixin on Mapping base class)
    def __iter__(self):
        return iter(self._dict)
        pass

    # Implements abstract method __contains__ from MutableMapping parent class (Container mixin on Mapping base class)
    def __contains__(self, x):
        self.__assert_type_key(x, 'x')
        return x in self._dict

Answer 6

Как насчет set()? Элементы могут иметь свои собственные k

Answer 7

Я не уверен, что это то, что вы имели в виду, но этот словарь создаст свои собственные ключи, когда вы добавите к нему ...

class KeyedCollection(dict):
    def __init__(self):
        self.current_key = 0
    def add(self, item):
        self[self.current_key] = item

abc = KeyedCollection()
abc.add('bob')
abc.add('jane')
>>> abc
{0: 'bob', 1: 'jane'}

Answer 8

Почему бы просто не использовать dict? Если ключ уже существует, ссылка на ключ будет использоваться в dict; это не будет бессмысленно продублировано.

class MyExample(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value

m = MyExample("foo", "bar")
d = {}

d[m.key] = m

first_key = d.keys()[0]
first_key is m.key  # returns True

Если ключ еще не существует, его копия будет сохранена, но я не вижу в этом проблемы.

def lame_hash(s):
    h = 0
    for ch in s:
        h ^= ord(ch)
    return h

d = {}
d[lame_hash(m.key)] = m
print d  # key value is 102 which is stored in the dict

lame_hash(m.key) in d  # returns True