Details about pythons set implementation

[Albert van der Horst]

In article <83b78deb-b7c4-4fa3-b9ad-1a40be4f9231 at n22g2000prh.googlegroups.com>,
bukzor  <workitharder at gmail.com> wrote:
>On Jan 4, 2:15 pm, Steven D'Aprano <st... at REMOVE-THIS-
>cybersource.com.au> wrote:
>> On Fri, 04 Jan 2008 09:29:50 -0800, bukzor wrote:
>> > 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)
>>
>> No, it is not. Ordered comparisons are not defined for complex numbers.

Mathematically speaking, it depends what you require from ordering.
Mostly (and what we need for fast lookup) we want transitivity:
A>=B & B>=C => A>=C

Requiring transitivity you are right with your concern
about the OP's version of <. Although in mathematics you can
define things as you like, a non-transitive < is frowned upon.

>> Which is bigger, 4+2j or 2+4j?

We can make a useful ordering by defining
A<=B :  if RE(A) /= RE(B) then RE(A) <= RE(B)
     else   IM(A) <= IM(B)

So for the OP's example: 4+2i is bigger.

This is sufficient to put a bunch of complex numbers in an
array, sort the array, and have a lookup using binary search.
(Or a heap: a heap is better for frequent additions and deletions.)

>>
>> > How do you implement a set without sorting?
>>
>> With a hash table.
>>
>> Or if you are willing to limit yourself to sets of small integers, you
>> can implement it using bit flipping. E.g. 5 is an element of the set if
>> bit 5 is on.

Or if you can live with O(n) implementations are trivial.

>>
>> > Are you expecting better than O(log n)?
>>
>> Sure.

The same applies to sets of complex numbers the C++ way with the
above definition of for < for complex  numbers.

>>
>> --
>> Steven
>
>Good Answers!


--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- like all pyramid schemes -- ultimately falters.
albert at spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst