Help with sets

[Steven D'Aprano]

On Mon, 04 Oct 2010 22:31:50 -0400, B. M. Whealton wrote:

> I did get a bit confused in reading about the concept of
> sets in python and why you would use them instead of a dictionary for
> example.

Why would you use a spoon instead of a paper clip? Why would you use a 
hat-stand instead of a pencil sharpener?

Sets aren't an alternative to dictionaries. They have a completely 
different purpose.

It so happens that sets and dicts *in Python* happen to share some 
implementation details, and they happen to share similar syntax, but 
don't be fooled by these incidental details. They could be implemented 
differently.

Dicts are used when you need a 1:1 mapping between a key and a value:

{name: address}  # each person has exactly one home address

Sets are used when you have a list of items, but you don't care about the 
order of the items, only whether or not something is in the list.

Since lists are ordered, searching a list to see if something is in it 
can be slow. Sets give up order so that they can make membership testing 
blindingly fast:


>>> from timeit import Timer
>>> Timer("100042 in L", "L=range(100000)").timeit(number=10000)
53.221637010574341
>>> Timer("100042 in S", "S=set(range(100000))").timeit(number=10000)
0.0022180080413818359



>         For example, here we have:
> self._pos = {predicate:{object:set([subject])}} This is said to be a
> dictionary, containing dictionaries, which in turn contain sets. I don't
> know if it would be possible to explain why one would use a set,
> especially in this context without showing more.  I was a bit stumped by
> this for some odd reason.  I don't know if other languages lack certain
> structures and features.

Of course they do. That's why we have more than one programming language. 
Earlier versions of Python didn't have sets. Standard Pascal doesn't have 
dicts. Neither Fortran nor COBOL supported recursion, at least early on. 


> It's been a long time since I did C
> programming too.
>         Anyway, this would be used an a Class as follows:
> 
> class SimpleGraph:
>      def __init__(self):
>           self._spo = {}
>           self._pos = {}
>           self._osp = {}
> 
> This is to create indexes that are permutations of the pattern subject,
> predicate object.  So, using this:
> 
> self._pos = {predicate:{object:set([subject])}}

Sounds complicated. What are the indexes for? Why not just have the 
permutations directly?




>         We have the first dictionary keyed off the first term, the
> second dictionary keyed off the second term, and the set containing the
> third terms(note terms plural). I guess I somewhat understand that sets
> are used to test for membership.  Cannot that be done with dictionaries,
> though?
>          Also, if you ran this for loop, below, what is being yielded,
> the key or the value in the dictionary?  I refer to this for loop here:
> for subject in self._pos[predicate][ojbect]: yield (subject, predicate,
> object)

What is yielded is exactly what you tell Python to yield: a tuple 
containing three items (subject, predicate, object), whatever they are.




-- 
Steven