Details about pythons set implementation

[Achim Domma]

Hi,

I'm interested in details about how sets are implemented in python.
They seem to be quite fast and I found some remarks who state, that
the implementation is highly optimized. I need to implemented sets in
C/C++ and need a starting point on how to do it right. Could somebody
give me a starting point?

regards,
Achim

[Hrvoje Niksic]

Achim Domma <do***@procoders.netwrites:

I'm interested in details about how sets are implemented in python.
They seem to be quite fast and I found some remarks who state, that
the implementation is highly optimized. I need to implemented sets
in C/C++ and need a starting point on how to do it right. Could
somebody give me a starting point?

You can simply look at the implementation, Objects/setobject.c in the
Python source code. Most that it's mostly copy-paste from the dict
implementation (dictobject.c) and that both are quite involved and
optimized for the use by Python. They're not general implementation
of sets from use in C.

The "highly optimized" remarks should be understood in the context of
Python, not in the context of other C and C++ set libraries. I don't
know how well Python sets compare to other set libraries, but I doubt
that it's much faster than the median (which "highly optimized" could
be understood to imply).

BTW if you're using C++, why not simply use std::set? If you need it
called from C, you can wrap the needed methods in a C-accessible API.

[Sion Arrowsmith]

Hrvoje Niksic <hn*****@xemacs.orgwrote:

>BTW if you're using C++, why not simply use std::set?

Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence -- if you're lucky,
this is a heap or a C array, and you've got O(log n) performance.
But the real killer is that requirement for a std::set<Tis that
T::operator< exists. Which means, for instance, that you can't
have a set of complex numbers....

--
\S -- si***@chiark.greenend.org.uk -- http://www.chaos.org.uk/~sion/
"Frankly I have no feelings towards penguins one way or the other"
-- Arthur C. Clarke
her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump

[bukzor]

On Jan 4, 9:08 am, Sion Arrowsmith <[e-mail]>
wrote:

Hrvoje Niksic <[e-mail]:

BTW if you're using C++, why not simply use std::set?

Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence -- if you're lucky,
this is a heap or a C array, and you've got O(log n) performance.
But the real killer is that requirement for a std::set<Tis that
T::operator< exists. Which means, for instance, that you can't
have a set of complex numbers....

--
\S -- [e-mail] --http://www.chaos.org.uk/~sion/
"Frankly I have no feelings towards penguins one way or the other"
-- Arthur C. Clarke
her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump

Why cant you implement < for complex numbers? Maybe I'm being naive,
but isn't this the normal definition?
a + bi < c + di iff sqrt(a**2 + b**2) < sqrt(c**2, d**2)

How do you implement a set without sorting?

Are you expecting better than O(log n)?

--Buck

[Diez B. Roggisch]

bukzor schrieb:

On Jan 4, 9:08 am, Sion Arrowsmith <[e-mail]>
wrote:

>Hrvoje Niksic <[e-mail]:

>>BTW if you're using C++, why not simply use std::set?

Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence -- if you're lucky,
this is a heap or a C array, and you've got O(log n) performance.
But the real killer is that requirement for a std::set<Tis that
T::operator< exists. Which means, for instance, that you can't
have a set of complex numbers....

--
\S -- [e-mail] --http://www.chaos.org.uk/~sion/
"Frankly I have no feelings towards penguins one way or the other"
-- Arthur C. Clarke
her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump

Why cant you implement < for complex numbers? Maybe I'm being naive,
but isn't this the normal definition?
a + bi < c + di iff sqrt(a**2 + b**2) < sqrt(c**2, d**2)

How do you implement a set without sorting?

Are you expecting better than O(log n)?

Of course, hashing does O(1) (most of the time, with a sane hash of course.)

Diez

[r.grimm]

On Jan 4, 6:08 pm, Sion Arrowsmith <[e-mail]>
wrote:

Hrvoje Niksic <[e-mail]:

BTW if you're using C++, why not simply use std::set?

Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence -- if you're lucky,
this is a heap or a C array, and you've got O(log n) performance.
But the real killer is that requirement for a std::set<Tis that
T::operator< exists. Which means, for instance, that you can't
have a set of complex numbers....

--

Hallo and Sorry for being OT.
As Arnaud pointed out, you must only overload the < Operator for the
requested type.
Something like
bool operator < ( const Type& fir, const Type& sec )....
similar to python with __lt__ .
The rest of magic will be done by the compiler/interpreter.
Assoziative Arrays (set,map,multi_set,multi_map) in the classical STL
are implemented as binary trees. Therefore the keys must be comparable
and the access time is O(log n ).
To get a dictionary with O(1), the most STL implementation support a
extension called hash_set.
The new standard TR1 support unsorted_set ... . You can download it
from www.boost.org. Newer gcc runtimes also including the new
subnamespace tr1.
There is no need to implement set in c++ to get O(1).
Greetings Rainer

[bearophileHUGS]

Sion Arrowsmith:

Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence

What about using hash_map instead? You can use it with GCC too (but
you have to use a trick if you want to use string keys).

Bye,
bearophile