Details about pythons set implementation
Albert van der Horst
albert at spenarnc.xs4all.nl
Sat Jan 19 19:16:59 CET 2008
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-
>> 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)?
The same applies to sets of complex numbers the C++ way with the
above definition of for < for complex numbers.
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
More information about the Python-list