Come si può tagliare con le chiavi stringa invece degli interi su un oggetto OrderedDict?

Question

Poiché uno OrderedDict ha le caratteristiche di entrambi un elenco (con elementi ordinati) e un dizionario (con le chiavi anziché gli indici), sembrerebbe naturale che si possa eseguire il troncamento utilizzando le chiavi.

>>> 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 

La cosa interessante di questo è che non è l'errore che si vede a causa di OrderedDictionary.__getslice__ non in corso di attuazione. Ho provato ad aggiungere un mio metodo __getslice__ a OrderedDict, ma continuo a ricorrere in questo problema TypeError. Sembra che Python stia facendo un tipo di controllo del tipo per far rispettare le chiavi di sezione come numeri interi, prima ancora che siano passati alla funzione __getslice__, come unpitone!

>>> 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! 

Quindi la mia domanda è: perché non posso implemento fette non-INT, che tipo di tipo controllo impedisce le chiavi fetta da raggiungendo anche la mia funzione __getslice__, e posso ignorare che implementando il mio BetterOrderedDict in C con attacchi?

Answer 1

__getslice__ è un modo deprecato di implementazione dell'affettatura. Invece si dovrebbe gestire slice oggetti 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)' 

E se avete bisogno di più di patate, che è possibile implementare tutte le tre operazioni di affettamento seguente modo:

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) 

Answer 2

Prova questa implementazione (molto brutta)

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)]) 

N.B. questo probabilmente funziona solo perché in questo esempio, il OrderedDict non è stato solo ordinato, ma anche ordinato. In un dizionario non ordinato la slice 'a':'c' non contiene 'b', quindi la mia logica if key.start <= k <= key.stop non riesce. Il seguente codice dovrebbe rispettare quello:

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

Questa è l'implementazione effettiva della funzionalità di slicing che si prevede.

OrderedDict mantiene internamente l'ordine delle chiavi sotto forma di una lista doppiamente collegata. Quoting the actual comment from 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]. 

Ora, per affettare il dizionario, abbiamo bisogno di iterare la lista doppiamente collegata, __root, che in realtà è una variabile privata, protetta dal name mangling mechanism.

Nota: Ciò implica che il nome di hacky venga districato per utilizzare le strutture di dati interne di 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) 

paio di basi di esempio:

>>> 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)]