Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Fun with fancy slicing

Reply
Thread Tools

Fun with fancy slicing

 
 
Ian McMeans
Guest
Posts: n/a
 
      10-05-2003
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)

>>> quicksort([random.randint(0, 20) for dummy in range(20)])

[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]
 
Reply With Quote
 
 
 
 
David Eppstein
Guest
Posts: n/a
 
      10-05-2003
In article <(E-Mail Removed) >,
http://www.velocityreviews.com/forums/(E-Mail Removed) (Ian McMeans) wrote:

> 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)
>
> >>> quicksort([random.randint(0, 20) for dummy in range(20)])

> [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


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.randrange(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
 
Reply With Quote
 
 
 
 
Fernando Perez
Guest
Posts: n/a
 
      10-06-2003
Alex Martelli wrote:

> 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...).


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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
OT Thursday, uh, fun, yeah, fun! Consultant MCSE 17 02-10-2007 03:39 AM
3 PIX VPN questions - FUN FUN FUN frishack@gmail.com Cisco 3 03-16-2006 02:25 PM
OT: Wednesday follow-up-to-Tuesday-Fun Fun Ken Briscoe MCSE 0 07-14-2004 01:41 PM
Programming is not as much fun/more fun than it used to be. Andy Fish Java 65 05-18-2004 08:24 PM
Fun fun fun Luke Computer Support 3 10-07-2003 03:45 PM



Advertisments