Velocity Reviews > Fun with fancy slicing

# Fun with fancy slicing

Dave Benjamin
Guest
Posts: n/a

 09-30-2003
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)])

>>> group(range(20), 4)

[(0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15),
(16, 17, 18, 19)]

>>> group(range(14), 3)

[(0, 1, 2), (3, 4, 5), (6, 7, , (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
Guest
Posts: n/a

 09-30-2003
Dave Benjamin <(E-Mail Removed)> writes:

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

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
Guest
Posts: n/a

 10-01-2003
In article <(E-Mail Removed)>, Michael Hudson wrote:
> Dave Benjamin <(E-Mail Removed)> 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.

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 :

Gerrit Holl
Guest
Posts: n/a

 10-01-2003
Dave Benjamin wrote:
> In article <(E-Mail Removed)>, Michael Hudson wrote:
> > Dave Benjamin <(E-Mail Removed)> 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.

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
-- 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
Guest
Posts: n/a

 10-01-2003
Dave Benjamin wrote:
...
> 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.

Hmmm, you mean as in...:

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

....?

Alex

David Eppstein
Guest
Posts: n/a

 10-01-2003
In article <ueEeb.206007\$(E-Mail Removed)>,
Alex Martelli <(E-Mail Removed)> wrote:

> Dave Benjamin wrote:
> ...
> > 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.

>
> Hmmm, you mean as in...:
>
> def quicksort(alist):
> return quicksort([ x in alist[1:] if x<=head ]) + [
>
> ...?

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.

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

Alex Martelli
Guest
Posts: n/a

 10-01-2003
David Eppstein wrote:
...
>> def quicksort(alist):
>> return quicksort([ x in alist[1:] if x<=head ]) + [

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

Right on both counts -- sorry.

> And if you correct that, it still doesn't work correctly for lists with
> repeated items.

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

[alex@lancelot perex]\$ python -i se.py
>>> import random
>>> x=4*range(5)
>>> random.shuffle(x)
>>> x

[4, 4, 3, 1, 1, 1, 1, 2, 0, 0, 3, 4, 3, 4, 2, 0, 3, 0, 2, 2]
>>> quicksort(x)

[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]
>>>

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

Alex

David Eppstein
Guest
Posts: n/a

 10-02-2003
In article <xdJeb.208403\$(E-Mail Removed)>,
Alex Martelli <(E-Mail Removed)> wrote:

> David Eppstein wrote:
> ...
> >> def quicksort(alist):
> >> return quicksort([ x in alist[1:] if x<=head ]) + [
> >> head ] + quicksort([ x in alist[1:] if x>head ])

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

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

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

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
Guest
Posts: n/a

 10-02-2003
* David Eppstein <(E-Mail Removed)> in comp.lang.python:
> 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.

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.

--
Damien Wyart

Michael Hudson
Guest
Posts: n/a

 10-02-2003
Gerrit Holl <(E-Mail Removed)> writes:

> Dave Benjamin wrote:
> > In article <(E-Mail Removed)>, Michael Hudson wrote:
> > > Dave Benjamin <(E-Mail Removed)> 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.

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

Hmm, I saw it

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/k.../slashdot.html