15

I checked on this link that set is mutable https://docs.python.org/3/library/stdtypes.html#frozenset while frozenset is immutable and hence hashable. So how is the set implemented in python and what is the element look up time? Actually I had a list of tuples [(1,2),(3,4),(2,1)] where each entry in the tuple is a id and I wanted to create a set/frozenset out of the this list. In this case the set should contain (1,2,3,4) as elements. Can I use frozenset to insert elements into it one by one from the list of tuples or I can only use a set?

Matt
  • 27,170
  • 6
  • 80
  • 74
vkaul11
  • 4,098
  • 12
  • 47
  • 79
  • 3
    This is purely speculation, but I would think that they're both implemented in the same way, but frozenset has a write lock (hence the immutability). The lookup times on a `frozenset` should be faster in the average case, given that with mutability (in `set`s), the interpreter may need to probe longer to find/insert an element. Hopefully though, someone who really knows this will post an answer - I'm interested – inspectorG4dget Jul 15 '13 at 02:51

3 Answers3

8

You can instantiate a frozenset from a generator expression or other iterable. It's not immutable until it's finished being instantiated.

>>> L = [(1,2),(3,4),(2,1)]
>>> from itertools import chain
>>> frozenset(chain.from_iterable(L))
frozenset([1, 2, 3, 4])

Python3.3 also has an optimisation that turns set literals such as {1, 2, 3, 4} into precomputed frozensets when used as the right-hand side of an in operator.

user2357112
  • 260,549
  • 28
  • 431
  • 505
John La Rooy
  • 295,403
  • 53
  • 369
  • 502
  • 1
    What should you prefer set or frozenset and what is the difference in lookup times? – vkaul11 Jul 15 '13 at 03:45
  • @vkaul11, I wouldn't expect there to be a difference in lookup time – John La Rooy Jul 15 '13 at 04:02
  • 1
    @vkaul11, the frozenset optimization should mean that the set is created at compile time, not every time the code is executed (at run time). Depending on the situation this micro-optimization could have a noticeable effect on performance. – Peter Hansen Apr 19 '15 at 15:06
5

Sets and frozensets are implemented the same way, as hashtables. (Why else would they require their elements to implement __hash__?) In fact, if you look at Objects/setobject.c, they share almost all their code. This means that as long as hash collisions don't get out of hand, lookup and deletion are O(1) and insertion is amortized O(1).

The usual way to create a frozenset is to initialize it with some other iterable. As gnibbler suggested, the best fit here would probably be itertools.chain.from_iterable:

>>> L = [(1,2),(3,4),(2,1)]
>>> from itertools import chain
>>> frozenset(chain.from_iterable(L))
frozenset([1, 2, 3, 4])
user2357112
  • 260,549
  • 28
  • 431
  • 505
  • docs.python.org/2.4/lib/types-set.html So the link here is outdated? There are currently two builtin set types, set and frozenset. The set type is mutable -- the contents can be changed using methods like add() and remove(). Since it is mutable, it has no hash value and cannot be used as either a dictionary key or as an element of another set. The frozenset type is immutable and hashable -- its contents cannot be altered after is created; however, it can be used as a dictionary key or as an element of another set – vkaul11 Jul 15 '13 at 03:52
  • While that link is about an old version, the information in it is still mostly correct. It doesn't contradict what I've said, though. Most of the frozenset and set code is the exact same code. They even have the same iterator type. – user2357112 Jul 15 '13 at 04:02
  • According to the link, set does not have a hash value so how is it implemented with hash table? – vkaul11 Jul 15 '13 at 07:15
  • A hash table doesn't have to be hashable; its keys have to be hashable. – user2357112 Jul 15 '13 at 07:17
-2

As for your first question, I haven't actually checked the source, but it seems safe to assume from the fact that sets need to contain objects of hashable types, that it is implemented using a hash table, and that its lookup time is, therefore, O(1).

As for your second question, you cannot insert the elements into a frozenset one by one (obviously, since it's immutable), but there's no reason to use a set instead; just construct it from a list (or other iterable) of the constituent values, e.g. like this:

data = [(1, 2), (3, 4), (2, 1)]
result = frozenset(reduce(list.__add__, [list(x) for x in data], []))
Dolda2000
  • 25,216
  • 4
  • 51
  • 92
  • `list.__add__` will give you quadratic performance. You should use `list.__iadd__` there instead – John La Rooy Jul 15 '13 at 03:35
  • Sure, but it was just an example. I tried to keep it simple for the sake of demonstration, though I'm not sure how well I succeeded in the end. :) – Dolda2000 Jul 15 '13 at 03:36
  • http://docs.python.org/2.4/lib/types-set.html So the link here is outdated? There are currently two builtin set types, set and frozenset. The set type is mutable -- the contents can be changed using methods like add() and remove(). Since it is mutable, it has no hash value and cannot be used as either a dictionary key or as an element of another set. The frozenset type is immutable and hashable -- its contents cannot be altered after is created; however, it can be used as a dictionary key or as an element of another set. – vkaul11 Jul 15 '13 at 03:51
  • What makes you think it is outdated? It seems accurate to me. – Dolda2000 Jul 15 '13 at 04:01
  • You said above "I haven't actually checked the source, but it seems safe to assume from the fact that sets need to contain objects of hashable types, that it is implemented using a hash table, and that its lookup time is, therefore, O(1)." and the link said "it has no hash value and cannot be used as either a dictionary key or as an element of another set." – vkaul11 Jul 15 '13 at 07:14
  • It is true that a `set` itself does not have a hash value, but the elements in it need to have one. – Dolda2000 Jul 15 '13 at 15:25
  • What is the difference between the two? Set is composed of its elements after all. What does a set independent of its elements mean? – vkaul11 Jul 15 '13 at 16:28
  • I don't quite understand what mistaken notion it is that you're laboring under. A `set` in Python is not exactly the same as the mathematical notion of a set; a Python `set` has an identity separate from the elements that compose it, and especially when it comes to mutable sets (as contrasted to `frozenset`s), this should be obvious in that you can have two sets composed of the same elements, but if you modify one of them, the other one remains unmodified. If sets had no identity apart from the elements that compose them, that operation would not make sense. – Dolda2000 Jul 16 '13 at 06:20
  • why reduce? if anything a double-for-loop generator expression – Copperfield Feb 03 '17 at 01:15