Is there a way to get an element from a set O (1) times?

Question

Possible duplicate:
Python: getting elements from a set

Consider the following code:

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

So new_item is in s because it is equivalent to one of its elements, but it is a different object.

I want to get item1 from s , the specified new_item is in s .

One of the solutions that I came up with is simple, but not very effective:

 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 

Another solution seems more efficient, but actually doesn't work:

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

And this one:

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

Since the intersection works in an undefined way:

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

If that matters, I'm using Python 2.7 x64 on Windows 7, but I need a cross-platform solution.

---

Thanks to everyone. I came up with the following workaround:

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

which in the future will be replaced by the following solution (which is now very incomplete):

 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

Do not use set , then. Just use a dict that displays some value for yourself. In your case, it displays:

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

So, everything that is equal to item1 will be found in d , but that is the value of item1 . And it is much better than linear time; -)

PS I hope I correctly understood the intent of your question. If not, check it out.

Answer 2

If you absolutely need O (1) search and object identity (and not just equality) and fast dialing operations (without having to create new sets every time you want to perform dialing operations), then one pretty simple approach is to use as a dict , so a set . You will need to support both structures in order to synchronize them, but this will allow you to support O (1) access (only with a large constant coefficient). (And perhaps this is what you are heading for your "future decision, which is very incomplete now" in your editing.)

However, you did not indicate the amount of data you are working with, or what performance problems you have, if any. So I'm not sure if you really need to do this. It is possible that a dict with the required type set or set with a linear search is already fast enough.