C'è un modo per ottenere un oggetto da un set in tempo O (1)?

Question

Eventuali duplicati:
Python: Retrieve items from a set

Si consideri il seguente codice:

>>> item1 = (1,) 
>>> item2 = (2,) 
>>> s = set([item1, item2]) 
>>> s 
set([(2,), (1,)]) 
>>> new_item = (1,) 
>>> new_item in s 
True 
>>> new_item == item1 
True 
>>> new_item is item1 
False 

Così new_item è in s perché è equivalente a uno dei suoi elementi, ma è un oggetto diverso.

Quello che voglio è ottenere item1 da s dato new_item è in s.

Una soluzione che ho messo a punto è semplice, ma non molto efficiente:

def get_item(s, new_item): 
    for item in s: 
     if item == new_item: 
      return item 

>>> get_item(s, new_item) is new_item 
False 
>>> get_item(s, new_item) is item1 
True 

Un'altra soluzione sembra più efficiente, ma in realtà non funziona:

def get_item_using_intersection1(s, new_item): 
    return set([new_item]).intersection(s).pop() 

Né questo:

def get_item_using_intersection2(s, new_item): 
    return s.intersection(set([new_item])).pop() 

Perché l'intersezione funziona in modo indefinito:

>>> get_item_using_intersection1(s, new_item) is new_item 
True 
>>> get_item_using_intersection1(s, new_item) is item1 
False 

>>> get_item_using_intersection2(s, new_item) is new_item 
True 
>>> get_item_using_intersection2(s, new_item) is item1 
False 

Se questo è importante, sto usando Python 2.7 x64 su Windows 7, ma ho bisogno di una soluzione multipiattaforma.

---

Grazie a tutti. Sono venuto con la seguente soluzione temporanea:

class SearchableSet(set): 

    def find(self, item): 
     for e in self: 
      if e == item: 
       return e 

che sarà sostituito in futuro con la seguente soluzione (che è molto incompleto in questo momento):

class SearchableSet(object): 

    def __init__(self, iterable=None): 
     self.__data = {} 
     if iterable is not None: 
      for e in iterable: 
       self.__data[e] = e 

    def __iter__(self): 
     return iter(self.__data) 

    def __len__(self): 
     return len(self.__data) 

    def __sub__(self, other): 
     return SearchableSet(set(self).__sub__(set(other))) 

    def add(self, item): 
     if not item in self: 
      self.__data[item] = item 

    def find(self, item): 
     return self.__data.get(item) 

Answer 1

Non utilizzare un set, poi . Basta usare uno dict per mappare un valore su se stesso. Nel tuo caso, si associa:

d[item1] = item1 
d[item2] = item2 

Quindi tutto ciò che è pari a item1 saranno trovati in d, ma il valore è item1 sé. Ed è molto meglio del tempo lineare ;-)

P.S. Spero di aver compreso correttamente l'intenzione della tua domanda. In caso contrario, si prega di chiarirlo.

Answer 2

Se è assolutamente necessario l'O (1) ricerca e l'identità oggetto (non solo uguaglianza) e operazioni di set veloce (senza dover creare nuovi set ogni volta che si vuole fare operazioni di set), poi uno abbastanza approccio diretto è quello di utilizzare sia a dict e uno set. Dovresti mantenere entrambe le strutture per mantenerle sincronizzate, ma questo ti permetterebbe di mantenere l'accesso O (1) (solo con un fattore costante più grande).(E forse questo è ciò a cui ti stai dirigendo con la tua "soluzione futura che è molto incompleta in questo momento" nella tua modifica.)

Tuttavia, non hai menzionato il volume di dati con cui stai lavorando, o cosa tipo di problemi di prestazioni che stai avendo, se del caso. Quindi non sono convinto che tu abbia davvero bisogno di farlo. Potrebbe essere che dict con la necessaria creazione set o set con ricerca lineare, sia già abbastanza veloce.