Czy istnieje sposób, aby uzyskać element z zestawu w czasie O (1)?

Question

Powiel możliwe:
Python: Retrieve items from a set

Rozważmy następujący kod:

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

Więc new_item jest w s ponieważ jest to równoznaczne z jednym z jego elementów, ale jest inny obiekt.

To, czego chcę, to uzyskać item1 z s pod numerem new_item w s.

Jedno rozwiązanie mam wymyślić jest proste, ale nie bardzo wydajny:

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 

Innym rozwiązaniem wydaje się być bardziej skuteczne, ale faktycznie nie działa:

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

Ani to jedno:

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

Ponieważ przecięcie działa w nieokreślony sposób:

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

Jeśli to ma znaczenie, używam Pythona 2.7 x64 na Windows 7, ale potrzebuję rozwiązania wieloplatformowego.

---

Dziękuję wszystkim. Wpadłem następującym rozwiązanie tymczasowe:

class SearchableSet(set): 

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

które zostaną zastąpione w przyszłości z poniższego rozwiązania (co jest bardzo niekompletny teraz):

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

Nie używaj set, a następnie . Po prostu użyj wartości dict, która odwzorowuje wartość dla siebie. W twoim przypadku, to mapy:

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

Więc cokolwiek to równa item1 będzie można znaleźć w d, ale wartość jest sama item1. I jest znacznie lepszy niż czas liniowy ;-)

P.S. Mam nadzieję, że dobrze zrozumiałem intencję twojego pytania. Jeśli nie, wyjaśnij to.

Answer 2

Jeśli koniecznie potrzebujemy O (1) odnośnika i tożsamość przedmiot (nie tylko równość) i szybki zestaw operacji (bez konieczności tworzenia nowych zestawów każdym razem, gdy chcesz zrobić zestaw operacji), a następnie jedną dość prostym podejściem jest użycie zarówno a dict i set. Musiałbyś zachować obie struktury, aby zachować ich synchronizację, ale to pozwoliłoby ci zachować dostęp O (1) (tylko z większym stałym współczynnikiem).(I być może to właśnie zmierzasz do swojego "przyszłego rozwiązania, które jest obecnie bardzo niekompletne").

Nie wspomniano jednak o ilości danych, z którymi pracujesz, ani o tym, problemy z wydajnością, jeśli takie występują. Więc nie jestem przekonany, czy naprawdę musisz to zrobić. Może być tak, że dict z wymaganym set stworzeniem lub set z liniowym odnośnikiem jest już wystarczająco szybki.