No trees in the stdlib?

[Tim Golden]

Want sorted order?

sorted(tuple(the_set))

Not sure why you want the tuple () there, but
you probably knew that...

TJG

 

[MRAB]

the_set = set( ... )

if str in the_set :
... "retrieval" case ...
else :
the_set.add(str)
#end if

Want sorted order?

sorted(tuple(the_set))

What could be simpler?

Why not just "sorted(the_set)"?

 

[João Valverde]

In message <[email protected]>, João
Valverde wrote:



the_set = set( ... )

if str in the_set :
... "retrieval" case ...
else :
the_set.add(str)
#end if

Want sorted order?

sorted(tuple(the_set))

What could be simpler?

Try putting that inside a loop with thousands of iterations and you'll
see what the problem is.

 

[zooko]

Try PyJudy:

http://www.dalkescientific.com/Python/PyJudy.html

 

[Lawrence D'Oliveiro]

Try putting that inside a loop with thousands of iterations and you'll
see what the problem is.

You could apply the same argument to anything. E.g. why create a tree
structure with a million elements? Try putting that inside a loop with
thousands of iterations and you'll see what the problem is.

 

[Paul Rubin]

You could apply the same argument to anything. E.g. why create a tree
structure with a million elements? Try putting that inside a loop with
thousands of iterations and you'll see what the problem is.

The idea is you're going to insert or delete something in the tree
structure at each iteration, an O(log n) operation, making the whole
loop O(n log n). If you sort a set (which is O(n log n)) inside the
loop then you end up with O(n**2 log n) which is impractical. A
reason you might sort inside the loop might be to find the nearby
neighbors of the new element or traverse some elements in the middle.
This is trivial with a tree structure but messy with something like
sets.

 

[Steven D'Aprano]

Lawrence D'Oliveiro wrote: [...]

Want sorted order?

sorted(tuple(the_set))

What could be simpler?

Try putting that inside a loop with thousands of iterations and you'll
see what the problem is.

You could apply the same argument to anything. E.g. why create a tree
structure with a million elements? Try putting that inside a loop with
thousands of iterations and you'll see what the problem is.

The difference is, it's vanishingly rare to want to build a tree with
millions of elements thousands of times over and over again, but it is
not unreasonable to want to access sorted data thousands of times.
Needing to re-sort it over and over and over again is wasteful, slow and
stupid. Binary trees were invented, in part, specifically to solve this
use-case.