iterators and views of lists

[Brendan Miller]

On Thu, Dec 17, 2009 at 8:41 AM, Anh Hai Trinh <anh.hai.trinh at gmail.com> wrote:
>> I have a couple of thoughts:
>> 1. Since [:] by convention already creates a copy, it might violate
>> people's expectations if that syntax were used.
>
> Indeed, listagent returns self on __getitem__[:]. What I meant was
> this:
>
>  x = [0, 1, 2, 3, 4, 5, 6, 7]
>  a = listagent(x)[::2]
>  a[:] = listagent(x)[::-2]
>
> And we get x = [7, 1, 5, 3, 3, 5, 1, 7], the copying happens in-place,
> of course.
>
>
>> 2. I'd give the listagent the mutable sequence interface
>
> Done!  I put the code in a repository here for those who might be
> interested:
> <http://github.com/aht/listagent.py>.
>
> In retrospect, the Python gurus here was right though. Copy, modify
> then replace is good enough, if not better since items are just
> pointers instead of values. For reversing, you need to translate all
> the indices (which cost exactly one addition and one multiplication
> per index). Is that cheaper than copying all the pointers to a new
> list?  For sorting, you definitely need to construct a lookup table
> since the sort algorithm needs to look over the indices multiple
> times, which means you are using two pointer indirections per index.
> Is that cheaper than just copying all the pointers to a new list? Even
> if there is any benefit at all, you'll need to implement listagent in
> C to squeeze it out.
>
> However, using listagents is faster if you just want a few items out
> of the slice. And it's cute.

Well, it doesn't really need to be any slower than a normal list. You
only need to use index and do extra additions because it's in python.
However, if listagent were written in C, you would just have a pointer
into the contents of the original list, and the length, which is all
that list itself has.

I don't actually expect you to write that, I'm just pointing it out.

As for copying pointers not taking much time... that depends on how
long the list is. if you are working with small sets of data, you can
do almost anything and it will be efficient. However, if you have
megabytes or gigabytes of data (say you are working with images or
video), than the difference between an O(1) or an O(n) operation is a
big deal.

I agree though, it doesn't matter to everyone and anyone. The reason I
was interested was because i was trying to solve some specific
problems in an elegant way. I was thinking it would be cool to make
python more usable in programming competitions by giving it its own
port of the STL's algorithm library, which needs something along the
lines of C++'s more powerful iterators.