Fun with fancy slicing

[Ian McMeans]

Re: Fun with fancy slicing

I've got to drop in my two cents :)
I wanted to see how clean I could make the algorithms look.

def quicksort(lst):
if len(lst) <= 1: return lst

left = [x for x in lst if x < lst[0]]
middle = [x for x in lst if x == lst[0]]
right = [x for x in lst if x > lst[0]]

return quicksort(left) + middle + quicksort(right )
[color=blue][color=green][color=darkred]
>>> quicksort([random.randint( 0, 20) for dummy in range(20)])[/color][/color][/color]
[0, 1, 2, 4, 4, 4, 4, 4, 6, 6, 8, 9, 12, 12, 13, 14, 14, 14, 16, 16]

Hopefully this is still nlogn :)

and then:

def primes():
p = {}
for cand in itertools.count (2):
if not [True for factor in p if not cand % factor]:
p[cand] = None
yield cand

list(itertools. islice(primes() , 0, 20))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

[David Eppstein]

Re: Fun with fancy slicing

In article <7f9e1817.03100 41817.4b5a8c23@ posting.google. com>,
imcmeans@telus. net (Ian McMeans) wrote:
[color=blue]
> def quicksort(lst):
> if len(lst) <= 1: return lst
>
> left = [x for x in lst if x < lst[0]]
> middle = [x for x in lst if x == lst[0]]
> right = [x for x in lst if x > lst[0]]
>
> return quicksort(left) + middle + quicksort(right )
>[color=green][color=darkred]
> >>> quicksort([random.randint( 0, 20) for dummy in range(20)])[/color][/color]
> [0, 1, 2, 4, 4, 4, 4, 4, 6, 6, 8, 9, 12, 12, 13, 14, 14, 14, 16, 16]
>
> Hopefully this is still nlogn :)[/color]

Well, for random inputs it is. If you want it to be O(n log n) even for
sorted inputs you could change it a little:

def quicksort(lst):
if len(lst) <= 1: return lst
pivot = lst[random.randrang e(len(lst))]

left = [x for x in lst if x < pivot]
middle = [x for x in lst if x == pivot]
right = [x for x in lst if x > pivot]

return quicksort(left) + middle + quicksort(right )

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science

[Fernando Perez]

Re: Fun with fancy slicing

Alex Martelli wrote:
[color=blue]
> I would want the type of the rhs to be irrelevant, just as long as it's any
> iterable whatsoever, and bundle the 'excess items' into ONE specified
> kind of sequence. I also think it would be best for that one kind to be
> tuple, by analogy to argument passing: you can use any iterable as the
> actual argument 'expanded' by the *foo form, but whatever type foo
> is, if the formal argument is *bar then in the function bar is a TUPLE --
> period, simplest, no ifs, no buts. Maybe using a list instead might have
> been better, but tuple was chosen, and I think we should stick to that
> for unpacking, because the analogy with argument passing is a good
> part of the reason the *foo syntax appeals to me (maybe for the same
> reason we should at least for now forego the *foo appearing in any
> spot but the last... though that _would_ be a real real pity...).[/color]

Agreed: a single convention (and following tuples is a good one, if nothing
else b/c it's the existing one) is probably the sanest solution. I hadn't
thought of generators and arbitrary iterables, partly b/c I still use pretty
much 'naked' python 2.1 for everything.

Cheers,

f.