Tuple slices

[Terry Reedy]

Re: Tuple slices


"George Sakkis" <gsakkis@rutger s.edu> wrote in message
news:35lbvdF4k3 ss4U1@individua l.net...[color=blue]
> Actually my initial motivation was not a huge tuple I had to slice many
> times. It was something much
> less extraordinarily unlikely, a recursive function with a sequence
> parameter:
>
> def foo(sequence):
> # base_case
> # do_stuff()
> combine(foo(seq uence[:n]),
> foo(sequence[n:]))
>
> Having each slice be a view of the original sequence instead of a fresh
> copy would be a Good Thing[/color]

Why? To save time? memory? Either would require more that a few bytes per
slice. If they are, you can probably use virtual slices as follows.

def foo(sequence):
def _foo(seq, start, stop)
# base_case
# do_stuff()
combine(_foo(se q, start, n), _foo(seq, n, stop))
_foo(sequence, 0, len(sequence)

In other words, if you don't really want slices copied out of the sequence,
then don't slice! Just use 2 ints to indicate the working region or view.
Both this and using a nested function with additional params are standard
techniques. This also works when the seq is mutable and you want changes
to the 'slice' to change the original, as in quicksort.

Terry J. Reedy

[Nick Coghlan]

Re: Tuple slices

George Sakkis wrote:[color=blue]
> You're probably right about the allocation time, but my main concern is the memory required for each
> slice, which can be O(n) wrt the length of the whole tuple. I would like this to be constant (at
> least if there was a way around to the problem of deleting the underlying sequence).[/color]

If you really want a view into a tuple (or any sequence for that matter):

from itertools import islice
islice(iter(seq ), start, end, step)

Then use the various functions in itertools to work with the resulting iterator
(since the syntactic support for working with iterators is currently quite
limited - slicing, concatenation and repetition are spelt with
itertools.islic e(), itertools.chain () and itertools.repea t(), rather than with
their standard syntactic equivalents "[x:y:z]", "+" and "*").

The above approach does suffer from the problem of holding a reference to the
original sequence, though.

Cheers,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[gsakkis@rutgers.edu]

Re: Tuple slices


Terry Reedy wrote:[color=blue]
> "George Sakkis" <gsakkis@rutger s.edu> wrote in message
> news:35lbvdF4k3 ss4U1@individua l.net...[color=green]
> > Actually my initial motivation was not a huge tuple I had to slice[/color][/color]
many[color=blue][color=green]
> > times. It was something much
> > less extraordinarily unlikely, a recursive function with a sequence[/color][/color]
[color=blue][color=green]
> > parameter:
> >
> > def foo(sequence):
> > # base_case
> > # do_stuff()
> > combine(foo(seq uence[:n]),
> > foo(sequence[n:]))
> >
> > Having each slice be a view of the original sequence instead of a[/color][/color]
fresh[color=blue][color=green]
> > copy would be a Good Thing[/color]
>
> Why? To save time? memory? Either would require more that a few[/color]
bytes per[color=blue]
> slice. If they are, you can probably use virtual slices as follows.
>
> def foo(sequence):
> def _foo(seq, start, stop)
> # base_case
> # do_stuff()
> combine(_foo(se q, start, n), _foo(seq, n, stop))
> _foo(sequence, 0, len(sequence)
>
> In other words, if you don't really want slices copied out of the[/color]
sequence,[color=blue]
> then don't slice! Just use 2 ints to indicate the working region or[/color]
view.[color=blue]
> Both this and using a nested function with additional params are[/color]
standard[color=blue]
> techniques. This also works when the seq is mutable and you want[/color]
changes[color=blue]
> to the 'slice' to change the original, as in quicksort.
>
> Terry J. Reedy[/color]


I would say these are standard *C/C++* techniques; slicing simplifies
things and thus seems more 'pythonic' to me.

George

[George Sakkis]

Re: Tuple slices

An iterator is perfectly ok if all you want is to iterate over the
elements of a view, but as you noted, iterators are less flexible than
the underlying sequence. The view should be (or at least appear)
identical in functionality (i.e. public methods) with its underlying
sequence.

George

[Terry Reedy]

Re: Tuple slices


<gsakkis@rutger s.edu> wrote in message
news:1106666051 .334641.70740@z 14g2000cwz.goog legroups.com...[color=blue]
>
> Terry Reedy wrote:[color=green]
>> In other words, if you don't really want slices copied out of the
>> sequence,
>> then don't slice! Just use 2 ints to indicate the working region or
>> view.
>> Both this and using a nested function with additional params are
>> standard
>> techniques. This also works when the seq is mutable and you want
>> changes
>> to the 'slice' to change the original, as in quicksort.[/color]
>
> I would say these are standard *C/C++* techniques; slicing simplifies
> things and thus seems more 'pythonic' to me.[/color]

Unless you are GvR or Tim Peters, throwing 'pythonic' at me doesn't cut it
with me, especially when you use it so shallowly. The current Pythonic
meaning of 'slice', as defined by GvR and implemented in core Python
sequence objects and documented in the reference manuals and reiterated by
GvR on PyDev in just the last day, is to make an independent in-memory
#copy# of the indicated part of a sequence. Both aspects are intentional
and desired features, not accidents.

Yes, slicing, even in the Pythonic sense, may well simplify the OP's
algorithm (of which he gave almost no detail), but the whole point of this
thread is that he does not want to do that (make copy slices). While he
might shortsightedly think that he wants Guido to redefine slice and
replace the current implementation of tuple with a more spacious, possibly
slower one that would allow that definition, that will not solve his
current problem, if indeed he has one.

As George Sakkis the OP noted, the essential data constituting a contiguous
section view are the underlying sequence and two position markers. Whether
one works with these directly or packages them into a tuple or user class
instance is a matter of relative conveniences. As it turns out, I was
thinking about the design choices involved in a generic sequence view class
just the morning before reading the original post. But I have no idea
whether GS's foo function would justify the added overhead of such a thing.
It partly depends on what he wishes to optimize, which I asked about, but
have not yet seen an answer about. So I suggested the simplest approach
that would work. And that, to me, *is* pythonic!

Terry J. Reedy

[Jeff Shannon]

Re: Tuple slices

George Sakkis wrote:
[color=blue]
> An iterator is perfectly ok if all you want is to iterate over the
> elements of a view, but as you noted, iterators are less flexible than
> the underlying sequence. The view should be (or at least appear)
> identical in functionality (i.e. public methods) with its underlying
> sequence.[/color]

So, what problem is it, exactly, that you think you'd solve by making
tuple slices a view rather than a copy?

As I see it, you get the *possibility* of saving a few bytes (which
may go in the other direction) at a cost of complexity and speed. You
have greater dependence of internal objects on each other, you can't
get rid of the original tuple while any slice views of it exist, you
gain nothing in the way of syntax/usage simplicity... so what's the
point?

To my mind, one of the best things about Python is that (for the most
part) I don't have to worry about actual memory layout of objects. I
don't *care* how tuples are implemented, they just work. It seems to
me that you're saying that they work perfectly fine as-is, but that
you have a problem with the implementation that the language tries its
best to let you not care about. Is this purely abstract philosophy?

Jeff Shannon
Technician/Programmer
Credit International

[George Sakkis]

Re: Tuple slices

"Terry Reedy" <tjreedy@udel.e du> wrote in message news:mailman.13 08.1106688018.2 2381.python-[color=blue]
>
> Unless you are GvR or Tim Peters,[/color]

Actually I am the OP. I posted my previous mail from Google groups, which for some reason put my
email instead of my name; it should be ok now.
[color=blue]
> throwing 'pythonic' at me doesn't cut it
> with me, especially when you use it so shallowly. The current Pythonic
> meaning of 'slice', as defined by GvR and implemented in core Python
> sequence objects and documented in the reference manuals and reiterated by
> GvR on PyDev in just the last day, is to make an independent in-memory
> #copy# of the indicated part of a sequence. Both aspects are intentional
> and desired features, not accidents.[/color]

Thanks for the info; a citation that supports your claim that the in-memory copy is part of the
*specification* of a tuple slice -- and not a choice that is subject to the implementation -- would
be useful. Note that I'm talking only about slices of *tuples* (or any immutable sequence for that
matter) here, not all slices. As for the "pythonic", I mentioned it as a loosely speaking synonym to
"simpler" or "more intuitive"; I apologize if this term has religious connotations in cl.py.
[color=blue]
> Yes, slicing, even in the Pythonic sense, may well simplify the OP's
> algorithm (of which he gave almost no detail), but the whole point of this
> thread is that he does not want to do that (make copy slices). While he
> might shortsightedly think that he wants Guido to redefine slice and
> replace the current implementation of tuple with a more spacious, possibly
> slower one that would allow that definition, that will not solve his
> current problem, if indeed he has one.[/color]

I fail to understand where does your strongly negative tone come from; certainly not from my posts.
I asked a simple question and I was expecting a simple answer, not defending myself from a
hypothetical shortsighted suggestion to Guido. Thankfully I got one (and only so far) good reason
for the current implementation from Fredrik Lundh, namely the reference to the original object.
[color=blue]
> As George Sakkis the OP noted, the essential data constituting a contiguous
> section view are the underlying sequence and two position markers. Whether
> one works with these directly or packages them into a tuple or user class
> instance is a matter of relative conveniences. As it turns out, I was[/color]

Honestly, I can't imagine a case where supplying these three associated data packaged is *less*
convenient than spelling them out explicitly.
[color=blue]
> thinking about the design choices involved in a generic sequence view class
> just the morning before reading the original post. But I have no idea
> whether GS's foo function would justify the added overhead of such a thing.[/color]

This is not the point; that function was just the motivation for questioning the current tuple slice
implementation. I wouldn't start this thread in the first place if I didn't have the impression that
tuple views would be beneficial for many (most?) cases.
[color=blue]
> It partly depends on what he wishes to optimize, which I asked about, but
> have not yet seen an answer about.[/color]

Are you sure you read the whole thread ? I replied explicitly on this to Jeff Shannon:

"You're probably right about the allocation time, but my main concern is the memory required for
each slice, which can be O(n) wrt the length of the whole tuple. I would like this to be constant
(at least if there was a way around to the problem of deleting the underlying sequence)."
[color=blue]
> So I suggested the simplest approach that would work. And that, to me, *is* pythonic![/color]

Simplest to whom ? The user or the py-dev guy that implements tuples ? It sounds as if you have the
second in mind.
[color=blue]
> Terry J. Reedy
>[/color]

George

[George Sakkis]

Re: Tuple slices

"Jeff Shannon" <jeff@ccvcorp.c om> wrote in message news:10vdj4s9ib 19fe3@corp.supe rnews.com...[color=blue]
> George Sakkis wrote:
>[color=green]
> > An iterator is perfectly ok if all you want is to iterate over the
> > elements of a view, but as you noted, iterators are less flexible than
> > the underlying sequence. The view should be (or at least appear)
> > identical in functionality (i.e. public methods) with its underlying
> > sequence.[/color]
>
> So, what problem is it, exactly, that you think you'd solve by making
> tuple slices a view rather than a copy?
>
> As I see it, you get the *possibility* of saving a few bytes (which[/color]

It all comes down on what you mean by "a few bytes". Since many (most?) slices are linear wrt to the
original sequence's length, it is not hard to think of algorithms that involve the creation of
*many* slices (e.g. most recursive divide-and-conquer algorithms). Implementing these using slices
simply does not scale as the input sequence gets larger. Of course, you can always use the standard
C/C++ approach and pass the original sequence along with the (start,stop,ste p) indices of the slice,
as Terry Reedy mentioned, but then you lose in expressiveness.
[color=blue]
> may go in the other direction) at a cost of complexity and speed. You
> have greater dependence of internal objects on each other, you can't
> get rid of the original tuple while any slice views of it exist, you
> gain nothing in the way of syntax/usage simplicity... so what's the
> point?
>
> To my mind, one of the best things about Python is that (for the most
> part) I don't have to worry about actual memory layout of objects. I
> don't *care* how tuples are implemented, they just work. It seems to
> me that you're saying that they work perfectly fine as-is, but that
> you have a problem with the implementation that the language tries its
> best to let you not care about. Is this purely abstract philosophy?[/color]

No, it's called "scalabilit y", and it's not purely abstract philosophy AFAIK. I fully agree that for
the most part you don't have to care about it, and I'm grateful that python does all its magic
trasparently. However if you do care about it, and at the same time you are unwilling to sacrifice
the elegance of slices, the current implementation is not ideal.
[color=blue]
> Jeff Shannon
> Technician/Programmer
> Credit International[/color]

George

[jfj]

Re: Tuple slices

Jeff Shannon wrote:
[color=blue]
>
>
> So, what problem is it, exactly, that you think you'd solve by making
> tuple slices a view rather than a copy?
>[/color]

I think views are good for
1) saving memory
2) saving time (as you don't have to copy the elements into the new tuple)

And they are worth it. However, (as in other cases with slicing), it is
very easy and fast to create a view for a slice with the default step
'1', while it's a PITA and totally not worth it to create a view for a
slice with non default step. I think it would be good to:

if slice_step == 1
create_view
else
create_new_tupl e

Actually, i think that slices with step, is a bad feature in general
and i think I will write a PEP to suggest their removal in python3k.


Gerald

[Bengt Richter]

Re: Tuple slices

On Tue, 25 Jan 2005 19:25:55 -0500, "George Sakkis" <gsakkis@rutger s.edu> wrote:
[color=blue]
>"Jeff Shannon" <jeff@ccvcorp.c om> wrote in message news:10vdj4s9ib 19fe3@corp.supe rnews.com...[color=green]
>> George Sakkis wrote:
>>[color=darkred]
>> > An iterator is perfectly ok if all you want is to iterate over the
>> > elements of a view, but as you noted, iterators are less flexible than
>> > the underlying sequence. The view should be (or at least appear)
>> > identical in functionality (i.e. public methods) with its underlying
>> > sequence.[/color]
>>
>> So, what problem is it, exactly, that you think you'd solve by making
>> tuple slices a view rather than a copy?
>>
>> As I see it, you get the *possibility* of saving a few bytes (which[/color]
>
>It all comes down on what you mean by "a few bytes". Since many (most?) slices are linear wrt to the
>original sequence's length, it is not hard to think of algorithms that involve the creation of
>*many* slices (e.g. most recursive divide-and-conquer algorithms). Implementing these using slices
>simply does not scale as the input sequence gets larger. Of course, you can always use the standard
>C/C++ approach and pass the original sequence along with the (start,stop,ste p) indices of the slice,
>as Terry Reedy mentioned, but then you lose in expressiveness.[/color]
I didn't see the leadup to this, but what is the problem with just subclassing tuple to
give you the views you want?


Regards,
Bengt Richter

[Bengt Richter]

Re: Tuple slices

On Wed, 26 Jan 2005 11:55:59 -0800, jfj <jfj@freemail.g r> wrote:
[color=blue]
>Jeff Shannon wrote:
>[color=green]
>>
>>
>> So, what problem is it, exactly, that you think you'd solve by making
>> tuple slices a view rather than a copy?
>>[/color]
>
>I think views are good for
> 1) saving memory
> 2) saving time (as you don't have to copy the elements into the new tuple)
>
>And they are worth it. However, (as in other cases with slicing), it is
>very easy and fast to create a view for a slice with the default step
>'1', while it's a PITA and totally not worth it to create a view for a
>slice with non default step. I think it would be good to:
>
> if slice_step == 1
> create_view
> else
> create_new_tupl e
>
>Actually, i think that slices with step, is a bad feature in general
>and i think I will write a PEP to suggest their removal in python3k.
>[/color]
What's the big deal with other than 1 steps? It is just adjusting a few numbers
so that you can either index the new virtual slice with an integer and return the
element, in which case the index into the original tuple will be
someoffset+i*so mefactor once you get past the limit checks for the virtual
slice. By the same token, transforming a few numbers of one virtual slice
into similar numbers for a a new virtual slice of that shouldn't be rocket science.
And it wouldn't have to be done more than once. Don't have time to do it now,
but there are plenty around here that could, I'm sure.

Regards,
Bengt Richter

[Nick Coghlan]

Re: Tuple slices

jfj wrote:[color=blue]
> Jeff Shannon wrote:
>[color=green]
>>
>>
>> So, what problem is it, exactly, that you think you'd solve by making
>> tuple slices a view rather than a copy?
>>[/color]
>
> I think views are good for
> 1) saving memory
> 2) saving time (as you don't have to copy the elements into the new tuple)[/color]

1. Applies only if you are making large slices, or a lot of slices with each
containing at least 3 elements.
A view can also *cost* memory, when it looks at a small piece of a large
item. The view will keep the entire item alive, even though it needs only a
small piece.

2. Hell no. The *elements* aren't copied, pointers to the elements are. If you
*don't* copy the pointers, then every item access through the view involves an
indirection as the index into the original sequence gets calculated.

So views *may* save memory in some applications, but are unlikely to save time
in any application (except any saving resulting from the memory saving).

Cheers,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[Nick Coghlan]

Re: Tuple slices

jfj wrote:[color=blue]
> Actually, i think that slices with step, is a bad feature in general
> and i think I will write a PEP to suggest their removal in python3k.[/color]

I wouldn't bother. Extended slicing was added to support those doing serious
numerical work in Python, and it won't get removed for all the reasons it was
added in the first place.

Cheers,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[George Sakkis]

Re: Tuple slices

"Bengt Richter" <bokr@oz.net> wrote in message news:41f772b2.1 858112584@news. oz.net...[color=blue]
> On Wed, 26 Jan 2005 11:55:59 -0800, jfj <jfj@freemail.g r> wrote:
>[color=green]
> >Jeff Shannon wrote:
> >[color=darkred]
> >>
> >>
> >> So, what problem is it, exactly, that you think you'd solve by making
> >> tuple slices a view rather than a copy?
> >>[/color]
> >
> >I think views are good for
> > 1) saving memory
> > 2) saving time (as you don't have to copy the elements into the new tuple)
> >
> >And they are worth it. However, (as in other cases with slicing), it is
> >very easy and fast to create a view for a slice with the default step
> >'1', while it's a PITA and totally not worth it to create a view for a
> >slice with non default step. I think it would be good to:
> >
> > if slice_step == 1
> > create_view
> > else
> > create_new_tupl e
> >
> >Actually, i think that slices with step, is a bad feature in general
> >and i think I will write a PEP to suggest their removal in python3k.
> >[/color]
> What's the big deal with other than 1 steps? It is just adjusting a few numbers
> so that you can either index the new virtual slice with an integer and return the
> element, in which case the index into the original tuple will be
> someoffset+i*so mefactor once you get past the limit checks for the virtual
> slice. By the same token, transforming a few numbers of one virtual slice
> into similar numbers for a a new virtual slice of that shouldn't be rocket science.
> And it wouldn't have to be done more than once. Don't have time to do it now,
> but there are plenty around here that could, I'm sure.
>
> Regards,
> Bengt Richter[/color]

Here's my (undocumented) version of it: http://rafb.net/paste/results/HkxmHp37.html
and its unit test: http://rafb.net/paste/results/2LIInT68.html

And some useless timing comparisons (I know it's a stupid example, don't flame me for this):

$ python /usr/lib/python2.3/timeit.py \
-s "x=tuple(xrange (10000))" \
"[x[1:-1] for n in xrange(100)]"
10 loops, best of 3: 3.84e+04 usec per loop

$ python /usr/lib/python2.3/timeit.py \
-s "from immutableseq import ImmutableSequen ce" \
-s "x=ImmutableSeq uence(xrange(10 000))" \
"[x[1:-1] for n in xrange(100)]"
100 loops, best of 3: 5.85e+03 usec per loop

Feel free to comment or suggest improvements.

George

[jfj]

Re: Tuple slices

Nick Coghlan wrote:
[color=blue]
>
> 1. Applies only if you are making large slices, or a lot of slices with
> each containing at least 3 elements.
> A view can also *cost* memory, when it looks at a small piece of a
> large item. The view will keep the entire item alive, even though it
> needs only a small piece.[/color]

That is correct.
[color=blue]
>
> 2. Hell no. The *elements* aren't copied, pointers to the elements are.
> If you *don't* copy the pointers, then every item access through the
> view involves an indirection as the index into the original sequence
> gets calculated.[/color]

If you have

x=(1,2,...10000 1)
y=x[:-1]

then you copy 100000 pointers AND you INCREF them AND you DECREF them
when y dies.

The unfortunate case by (1) would be:

x=(1,2,...10000 1)
x=x[:1]
[color=blue]
>
> So views *may* save memory in some applications, but are unlikely to
> save time in any application (except any saving resulting from the
> memory saving).
>[/color]

They do. If tp_dealloc of a tuple view doesn't decref the pointers.

We should look for what is the most common case.


Gerald

-PS: the PEP for the removal ought to have a ":)" at the end.