Fun with fancy slicing

[Dave Benjamin]

Hey all,

I just realized you can very easily implement a sequence grouping function
using Python 2.3's fancy slicing support:

def group(values, size):
return map(None, *[values[i::size] for i in range(size)])
[color=blue][color=green][color=darkred]
>>> group(range(20) , 4)[/color][/color][/color]
[(0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15),
(16, 17, 18, 19)]
[color=blue][color=green][color=darkred]
>>> group(range(14) , 3)[/color][/color][/color]
[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11), (12, 13, None)]

I had to use map(None, *...) instead of zip(*...) to transpose the result
because zip throws away the "orphans" at the end. Anyway, this is a useful
function to have in your toolkit if you need to do pagination or
multi-column display, among other things...

Anyone have any other interesting applications of the extended slice syntax?

Peace,
Dave

--
..:[ dave benjamin (ramenboy) -:- www.ramenfest.com -:- www.3dex.com ]:.
: d r i n k i n g l i f e o u t o f t h e c o n t a i n e r :

[Michael Hudson]

Re: Fun with fancy slicing

Dave Benjamin <ramen@lackingt alent.com> writes:
[color=blue]
> Anyone have any other interesting applications of the extended slice syntax?[/color]

You can use it in a sieve prime finder (ooh, thread crossing :-):

/>> def sieve(p):
|.. candidates = range(p)
|.. for i in candidates[2:]:
|.. if not candidates[i]: continue
|.. n = len(candidates[2*i::i])
|.. candidates[2*i::i] = [0]*n
|.. return filter(None, candidates[2:])
\__
->> sieve(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

but it's not especially efficient (in speed or memory). Quite cute,
though.

Cheers,
mwh

--
A typical luser can perform truly superhuman feats of strength &
dexterity to avoid reading documentation. -- Lionel, asr

[Dave Benjamin]

Re: Fun with fancy slicing

In article <7h3isnaz6qw.fs f@pc150.maths.b ris.ac.uk>, Michael Hudson wrote:[color=blue]
> Dave Benjamin <ramen@lackingt alent.com> writes:
>[color=green]
>> Anyone have any other interesting applications of the extended slice syntax?[/color]
>
> You can use it in a sieve prime finder (ooh, thread crossing :-):
> ...
> but it's not especially efficient (in speed or memory). Quite cute,
> though.[/color]

But quite expressive! I'm amazed at how small that code was. It reminds me
of the trademark quicksort implementation in Haskell, ie. it may not be
great in practice, but you can see the algorithm at a high level which makes
it easier to figure out what's going on.

Anyway, thanks. That was cool. =)

Peace,
Dave

--
..:[ dave benjamin (ramenboy) -:- www.ramenfest.com -:- www.3dex.com ]:.
: d r i n k i n g l i f e o u t o f t h e c o n t a i n e r :

[Alex Martelli]

Re: Fun with fancy slicing

Dave Benjamin wrote:
...[color=blue]
> of the trademark quicksort implementation in Haskell, ie. it may not be
> great in practice, but you can see the algorithm at a high level which
> makes it easier to figure out what's going on.[/color]

Hmmm, you mean as in...:

def quicksort(alist ):
head = alist[0]
return quicksort([ x in alist[1:] if x<=head ]) + [
head ] + quicksort([ x in alist[1:] if x>head ])

....?


Alex

[David Eppstein]

Re: Fun with fancy slicing

In article <ueEeb.206007$R 32.6624508@news 2.tin.it>,
Alex Martelli <aleax@aleax.it > wrote:
[color=blue]
> Dave Benjamin wrote:
> ...[color=green]
> > of the trademark quicksort implementation in Haskell, ie. it may not be
> > great in practice, but you can see the algorithm at a high level which
> > makes it easier to figure out what's going on.[/color]
>
> Hmmm, you mean as in...:
>
> def quicksort(alist ):
> head = alist[0]
> return quicksort([ x in alist[1:] if x<=head ]) + [
> head ] + quicksort([ x in alist[1:] if x>head ])
>
> ...?[/color]

Well, except that it gets a syntax error. And if you correct the syntax
it gets an IndexError due to the lack of a base case for the recursion.
And if you correct that, it still doesn't work correctly for lists with
repeated items.

How about:

def quicksort(L):
if len(L) < 2: return L
return quicksort([x for x in L if x < L[0]]) + \
[x for x in L if x == L[0]] + \
quicksort([x for x in L if x > L[0]])

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

[Gerrit Holl]

Missing messagen (Was: Re: Fun with fancy slicing)

Dave Benjamin wrote:[color=blue]
> In article <7h3isnaz6qw.fs f@pc150.maths.b ris.ac.uk>, Michael Hudson wrote:[color=green]
> > Dave Benjamin <ramen@lackingt alent.com> writes:
> >[color=darkred]
> >> Anyone have any other interesting applications of the extended slice syntax?[/color]
> >
> > You can use it in a sieve prime finder (ooh, thread crossing :-):
> > ...
> > but it's not especially efficient (in speed or memory). Quite cute,
> > though.[/color][/color]

I do not seem to have received this message from Michael Hudson through
python-list. I am able to locate it on the newsgroup. Does anyone else
have this problem?

Gerrit Holl.

--
278. If any one buy a male or female slave, and before a month has
elapsed the benu-disease be developed, he shall return the slave to the
seller, and receive the money which he had paid.
-- 1780 BC, Hammurabi, Code of Law
--
Asperger Syndroom - een persoonlijke benadering:

http://people.nl.linux.org/~gerrit/

Het zijn tijden om je zelf met politiek te bemoeien:

http://www.sp.nl/

[Alex Martelli]

Re: Fun with fancy slicing

David Eppstein wrote:
...[color=blue][color=green]
>> def quicksort(alist ):
>> head = alist[0]
>> return quicksort([ x in alist[1:] if x<=head ]) + [
>> head ] + quicksort([ x in alist[1:] if x>head ])[/color]
>
> Well, except that it gets a syntax error. And if you correct the syntax
> it gets an IndexError due to the lack of a base case for the recursion.[/color]

Right on both counts -- sorry.
[color=blue]
> And if you correct that, it still doesn't work correctly for lists with
> repeated items.[/color]

Why not? Having fixed the syntax and added the base-case, I see:

[alex@lancelot perex]$ python -i se.py[color=blue][color=green][color=darkred]
>>> import random
>>> x=4*range(5)
>>> random.shuffle( x)
>>> x[/color][/color][/color]
[4, 4, 3, 1, 1, 1, 1, 2, 0, 0, 3, 4, 3, 4, 2, 0, 3, 0, 2, 2][color=blue][color=green][color=darkred]
>>> quicksort(x)[/color][/color][/color]
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

So what am I missing? Please show a case of "list with repeated
items" where the fixed quicksort "doesn't work correctly", thanks.

btw, my favourite fixed version is:

def quicksort(alist ):
try: head = alist[0]
except IndexError: return alist
return quicksort([ x for x in alist[1:] if x<=head ]) + [
head ] + quicksort([ x for x in alist[1:] if x>head ])

but I do see that testing len(alist) is probably better.

How sweet it would be to be able to unpack by coding:
head, *tail = alist
....


Alex

[David Eppstein]

Re: Fun with fancy slicing

In article <xdJeb.208403$R 32.6721730@news 2.tin.it>,
Alex Martelli <aleax@aleax.it > wrote:
[color=blue]
> David Eppstein wrote:
> ...[color=green][color=darkred]
> >> def quicksort(alist ):
> >> head = alist[0]
> >> return quicksort([ x in alist[1:] if x<=head ]) + [
> >> head ] + quicksort([ x in alist[1:] if x>head ])[/color]
> >
> > Well, except that it gets a syntax error. And if you correct the syntax
> > it gets an IndexError due to the lack of a base case for the recursion.[/color]
>
> Right on both counts -- sorry.
>[color=green]
> > And if you correct that, it still doesn't work correctly for lists with
> > repeated items.[/color]
>
> Why not? Having fixed the syntax and added the base-case, I see:[/color]

Sorry, does work correctly, just not efficiently. I didn't see the = in
the first recursive call. But if you call your quicksort on say [0]*n,
each call will split the list as unevenly as possible and you get
quadratic runtime. Of course we know that nonrandom quicksort pivoting
can be quadratic anyway (e.g. on sorted input) but this to my mind is
worse because randomization doesn't make it any better. The fact that
some textbooks (e.g. CLRS!) make this mistake doesn't excuse it either.

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

[Damien Wyart]

Re: Fun with fancy slicing

* David Eppstein <eppstein@ics.u ci.edu> in comp.lang.pytho n:[color=blue]
> Of course we know that nonrandom quicksort pivoting can be quadratic
> anyway (e.g. on sorted input) but this to my mind is worse because
> randomization doesn't make it any better. The fact that some textbooks
> (e.g. CLRS!) make this mistake doesn't excuse it either.[/color]

Could you explain in more detail the error made in CLRS on this topic
(with a reference if possible) ? I did not precisely catch your
explanation here.

Thanks in advance,
--
Damien Wyart

[Michael Hudson]

Re: Missing messagen (Was: Re: Fun with fancy slicing)

Gerrit Holl <gerrit@nl.linu x.org> writes:
[color=blue]
> Dave Benjamin wrote:[color=green]
> > In article <7h3isnaz6qw.fs f@pc150.maths.b ris.ac.uk>, Michael Hudson wrote:[color=darkred]
> > > Dave Benjamin <ramen@lackingt alent.com> writes:
> > >
> > >> Anyone have any other interesting applications of the extended slice syntax?
> > >
> > > You can use it in a sieve prime finder (ooh, thread crossing :-):
> > > ...
> > > but it's not especially efficient (in speed or memory). Quite cute,
> > > though.[/color][/color]
>
> I do not seem to have received this message from Michael Hudson through
> python-list. I am able to locate it on the newsgroup. Does anyone else
> have this problem?[/color]

Hmm, I saw it :-)

Google also has it:

http://groups.google.com/groups?selm=7h3isnaz6qw.fsf%40pc150.maths.bris.ac.uk

I don't really read the newsgroup closely enough any more to know if
any messages are going missing, I'm afraid.

Cheers,
mwh


--
Screaming 14-year-old boys attempting to prove to each other that
they are more 3133t than j00.
-- Reason #8 for quitting slashdot today, from

http://www.cs.washington.edu/homes/klee/misc/slashdot.html

[David Eppstein]

Re: Fun with fancy slicing

In article <3f7bf423$0$206 54$626a54ce@new s.free.fr>,
Damien Wyart <damien.wyart@f ree.fr> wrote:
[color=blue]
> * David Eppstein <eppstein@ics.u ci.edu> in comp.lang.pytho n:[color=green]
> > Of course we know that nonrandom quicksort pivoting can be quadratic
> > anyway (e.g. on sorted input) but this to my mind is worse because
> > randomization doesn't make it any better. The fact that some textbooks
> > (e.g. CLRS!) make this mistake doesn't excuse it either.[/color]
>
> Could you explain in more detail the error made in CLRS on this topic
> (with a reference if possible) ? I did not precisely catch your
> explanation here.
>
> Thanks in advance,[/color]

CLRS' partition routine ends up partitioning an n-item array into the
items <= the pivot, the pivot itself, and the items > the pivot.
If the items are all equal, that means that the first part gets n-1
items and the last part gets nothing, regardless of which item you
select as pivot. If you analyze the algorithm on this input, you get
the recurrence T(n)=O(n)+T(n-1)+T(0) which solves to O(n^2).

Throughout most of the quicksort chapter, CLRS at least include
exercises mentioning the case of all equal inputs, asking what happens
for those inputs, and in one exercise suggesting a partition routine
that might partition those inputs more equally (but who knows what it
should do when merely most of the inputs are equal...) However in the
randomized quicksort section they ignored this complication and seemed
to be claiming that their randomized quicksort has O(n log n) expected
time, unconditionally .

This problem was finally corrected in the fourth printing of the second
edition; see the errata at
<http://www.cs.dartmout h.edu/~thc/clrs-2e-bugs/bugs.php>
for more details.

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

[Greg Ewing (using news.cis.dfn.de)]

*-unpacking (Re: Fun with fancy slicing)

Alex Martelli wrote:[color=blue]
> How sweet it would be to be able to unpack by coding:
> head, *tail = alist[/color]

Indeed! I came across another use case for this
recently, as well. I was trying to parse some
command strings of the form

command arg arg ...

where some commands had args and some didn't.
I wanted to split the command off the front
and keep the args for later processing once
I'd decoded the command. My first attempt
went something like

command, args = cmdstring.split (" ", maxsplit = 1)

but this fails when there are no arguments,
because the returned list has only one element
in that case.

It would have been very nice to be able to
simply say

command, *args = cmdstring.split ()

and get the command as a string and a
list of 0 or more argument strings.

I really ought to write a PEP about this...

--
Greg Ewing, Computer Science Dept,
University of Canterbury,
Christchurch, New Zealand

http://www.cosc.canterbury.ac.nz/~greg

[David C. Fox]

Re: *-unpacking (Re: Fun with fancy slicing)

Greg Ewing (using news.cis.dfn.de ) wrote:[color=blue]
> Alex Martelli wrote:
>[color=green]
>> How sweet it would be to be able to unpack by coding:
>> head, *tail = alist[/color]
>
>
> Indeed! I came across another use case for this
> recently, as well. I was trying to parse some
> command strings of the form
>
> command arg arg ...
>
> where some commands had args and some didn't.
> I wanted to split the command off the front
> and keep the args for later processing once
> I'd decoded the command. My first attempt
> went something like
>
> command, args = cmdstring.split (" ", maxsplit = 1)
>
> but this fails when there are no arguments,
> because the returned list has only one element
> in that case.
>
> It would have been very nice to be able to
> simply say
>
> command, *args = cmdstring.split ()
>
> and get the command as a string and a
> list of 0 or more argument strings.
>
> I really ought to write a PEP about this...
>[/color]

In the mean time, it isn't too hard to write a function which does this:

def first_rest(x):
return x[0], x[1:]

command, args = first_rest(cmds tring.split())

or, in one step

def chop_word(s):
return first_rest(s.sp lit())

command, args = chop_word(cmdst ring)

David

[Lulu of the Lotus-Eaters]

Re: *-unpacking

|Alex Martelli wrote:
|> How sweet it would be to be able to unpack by coding:
|> head, *tail = alist

"Greg Ewing (using news.cis.dfn.de )" <g2h5dqi002@sne akemail.com> wrote previously:
| command arg arg ...
| command, *args = cmdstring.split ()
|and get the command as a string and a list of 0 or more argument strings.

I think I've written on this list before that I would like this
too--Ruby does this, IIRC. If anyone writes a PEP, you have my +1 in
advance.

For Greg's particular case, one approach that doesn't look too bad is:

command = args.pop(0)
# ... do stuff ...
try:
more = args.pop(0)
except IndexError:
# no more

For a really long list, it would be faster to do an 'args.reverse() ' up
front, and '.pop()' off the end (Greg and Alex know all this, of course).

Yours, Lulu...

--
mertz@ _/_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY: \_\_\_\_ n o
gnosis _/_/ Postmodern Enterprises \_\_
..cx _/_/ \_\_ d o
_/_/_/ IN A WORLD W/O WALLS, THERE WOULD BE NO GATES \_\_\_ z e

[David Eppstein]

Re: *-unpacking (Re: Fun with fancy slicing)

In article <Jd7fb.484435$c F.170532@rwcrns c53>,
"David C. Fox" <davidcfox@post .harvard.edu> wrote:
[color=blue]
> In the mean time, it isn't too hard to write a function which does this:
>
> def first_rest(x):
> return x[0], x[1:][/color]

Shouldn't that be called cons?

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