deque python

¿Cómo se puede dividir con claves de cadena en lugar de enteros en un OrderedDict de Python?

Question

Dado que un OrderedDict tiene las características de una lista (con elementos ordenados) y un diccionario (con claves en lugar de índices), parece natural que se pueda cortar con claves.

>>> from collections import OrderedDict
>>> cities = OrderedDict(((''san francisco'', 650), (''new york'', 212), (''shanghai'', 8621), (''barcelona'', 42423)))
>>> test[''shanghai'':]  # I want all the cities from shanghai to the end of the list
TypeError: unhashable type

Lo interesante de esto es que no es el error que OrderedDictionary.__getslice__ debido a OrderedDictionary.__getslice__ no se está implementando. Intenté agregar mi propio método __getslice__ a OrderedDict , pero sigo encontrando este problema TypeError. Parece que Python está haciendo algún tipo de comprobación de tipos para imponer que las claves de __getslice__ sean solo números enteros, incluso antes de __getslice__ a la función __getslice__ , ¡qué impía!

>>> class BetterOrderedDict(OrderedDict):
        def __getslice__(self, start=None, end=None, step=1):
            return ''potato''

>>> test = BetterOrderedDict(((''one'', 1), (''two'', 2), (''three'', 3), (''four'', 4)))
>>> print test[1:4]
''potato''                           # ok this makes sense so far

>>> test[''one'':''four'']
TypeError: unhashable type         # WTF, strings are hashable!

Entonces, mi pregunta es: ¿por qué no puedo implementar segmentos no int, qué tipo de comprobación de tipos impide que las teclas de segmento lleguen a mi función __getslice__ y puedo anularlo implementando mi BetterOrderedDict en C con enlaces?

Answer 1

Esta es la implementación real de la función de división que está esperando.

OrderedDict mantiene internamente el orden de las claves en forma de una lista doblemente enlazada. Citando el comentario real de Python 2.7.9 ,

# The internal self.__map dict maps keys to links in a doubly linked list.
# The circular doubly linked list starts and ends with a sentinel element.
# The sentinel element never gets deleted (this simplifies the algorithm).
# Each link is stored as a list of length three:  [PREV, NEXT, KEY].

Ahora, para dividir el diccionario, necesitamos iterar la lista doblemente enlazada, __root , que en realidad es una variable privada, protegida por el mecanismo de manipulación de nombres .

Nota: Esto implica que el nombre de hacky se desenreda para usar las estructuras de datos internas de OrderedDict .

from collections import OrderedDict

class SlicableDict(OrderedDict):
    def __getitem__(self, key):
        if isinstance(key, slice):
            # Unmangle `__root` to access the doubly linked list
            root = getattr(self, "_OrderedDict__root")
            # By default, make `start` as the first element, `end` as the last
            start, end = root[1][2], root[0][2]
            start = key.start or start
            end = key.stop or end
            step = key.step or 1
            curr, result, begun, counter = root[1], [], False, 0

            # Begin iterating
            curr, result, begun = root[1], [], False
            while curr is not root:
                # If the end value is reached, `break` and `return`
                if curr[2] == end:
                    break
                # If starting value is matched, start appending to `result`
                if curr[2] == start:
                    begun = True
                if begun:
                    if counter % step == 0:
                        result.append((curr[2], self[curr[2]]))
                    counter += 1

                # Make the `curr` point to the next element
                curr = curr[1]

            return result

        return super(SlicableDict, self).__getitem__(key)

Pocas muestras de muestra:

>>> s = SlicableDict(a=1, b=2, c=3, d=4)
>>> s
SlicableDict([(''a'', 1), (''c'', 3), (''b'', 2), (''e'', 5), (''d'', 4), (''f'', 6)])
>>> s[''a'':''c'']
[(''a'', 1)]
>>> s[''a'':]
[(''a'', 1), (''c'', 3), (''b'', 2), (''e'', 5), (''d'', 4)]
>>> s[:''a'']
[]
>>> s[''a'':''f'':2]
[(''a'', 1), (''b'', 2), (''d'', 4)]

Answer 2

Prueba esta implementación (muy fea)

class SliceOrdered(OrderedDict):

    def __getitem__(self, key):
        if isinstance(key, slice):
            tmp = OrderedDict()
            i_self = iter(self)
            for k in i_self:
                if key.start <= k <= key.stop:
                    tmp[k] = self[k]
                    if key.step is not None and key.step > 1:
                        for _ in range(key.step-1):
                            try:
                                next(i_self)
                            except StopIteration:
                                break
            return tmp
        else:
            return super(SliceOrdered, self).__getitem__(key)

DEMO (Python3.4)

>>> s = SliceOrdered([(''a'',2), (''b'',2), (''c'',3), (''d'',4)])
>>> s[''a'':''c'']
OrderedDict([(''a'', 2), (''b'', 2), (''c'', 3)])
>>> s[''a'':''d'':2]
OrderedDict([(''a'', 2), (''c'', 3)])

NB: esto probablemente solo funciona porque en este ejemplo, OrderedDict no solo se ordenó, sino que también se ordenó. En un diccionario sin clasificar, la división ''a'':''c'' no necesariamente contiene ''b'' , por lo que mi if key.start <= k <= key.stop probablemente falla. El siguiente código debe respetar eso:

class SliceOrdered(OrderedDict):
    def __getitem__(self, key):
        if not isinstance(key, slice):
            return super(SliceOrdered,self).__getitem__(key)
        tmp = OrderedDict()
        step = key.step or 1
        accumulating = False
        i_self = iter(self)
        for k in i_self:
            if k == key.start:
                accumulating = True
            if accumulating:
                tmp[k] = self[k]
                for _ in range(step-1):
                    next(i_self)
            if k == key.stop:
                accumulating = False
                break
        return tmp

Answer 3

__getslice__ es una forma obsoleta de implementar la segmentación. En su lugar, debe manejar objetos de __getitem__ con __getitem__ :

from collections import OrderedDict

class SlicableDict(OrderedDict):
    def __getitem__(self, key):
        if isinstance(key, slice):
            return ''potato({},{},{})''.format(key.start, key.stop, key.step)
        return super(SlicableDict, self).__getitem__(key)

>>> s = SlicableDict(a=1, b=2, c=3)
>>> s
SlicableDict([(''a'', 1), (''c'', 3), (''b'', 2)])
>>> s[''a'']
1
>>> s[''a'':''c'']
''potato(a,c,None)''

Y si necesita más que papa, puede implementar las tres operaciones de corte de la siguiente manera:

def _key_slice_to_index_slice(items, key_slice):
    try:
        if key_slice.start is None:
            start = None
        else:
            start = next(idx for idx, (key, value) in enumerate(items)
                         if key == key_slice.start)
        if key_slice.stop is None:
            stop = None
        else:
            stop = next(idx for idx, (key, value) in enumerate(items)
                        if key == key_slice.stop)
    except StopIteration:
        raise KeyError
    return slice(start, stop, key_slice.step)

class SlicableDict(OrderedDict):
    def __getitem__(self, key):
        if isinstance(key, slice):
            items = self.items()
            index_slice = _key_slice_to_index_slice(items, key)
            return SlicableDict(items[index_slice])
        return super(SlicableDict, self).__getitem__(key)

    def __setitem__(self, key, value):
        if isinstance(key, slice):
            items = self.items()
            index_slice = _key_slice_to_index_slice(items, key)
            items[index_slice] = value.items()
            self.clear()
            self.update(items)
            return
        return super(SlicableDict, self).__setitem__(key, value)

    def __delitem__(self, key):
        if isinstance(key, slice):
            items = self.items()
            index_slice = _key_slice_to_index_slice(items, key)
            del items[index_slice]
            self.clear()
            self.update(items)
            return
        return super(SlicableDict, self).__delitem__(key)