Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #90807 > unrolled thread

Slices time complexity

Back to article view | Back to comp.lang.python

Contents

  Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-18 20:23 +0100
    Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 05:36 +1000
      Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-18 20:49 +0100
        Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 06:04 +1000
    Re: Slices time complexity Todd <toddrjen@gmail.com> - 2015-05-18 21:42 +0200
    Re: Slices time complexity Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-18 13:49 -0600
      Re: Slices time complexity Fabien <fabien.maussion@gmail.com> - 2015-05-18 21:54 +0200
        Re: Slices time complexity Todd <toddrjen@gmail.com> - 2015-05-18 22:23 +0200
      Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-18 22:04 +0100
        Re: Slices time complexity Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-18 22:38 +0100
        Re: Slices time complexity Terry Reedy <tjreedy@udel.edu> - 2015-05-18 19:04 -0400
      Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-18 19:20 -0700
        Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 15:13 +1000
          Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-18 22:33 -0700
            Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 10:12 +0300
              Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 18:16 +1000
                Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 11:39 +0300
                  Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 18:50 +1000
                    Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 12:35 +0300
                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 23:44 +1000
                        Re: Slices time complexity Christian Gollwitzer <auriocus@gmx.de> - 2015-05-20 23:54 +0200
                    Re: Slices time complexity Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-19 23:00 +1200
                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 11:47 +1000
                        Re: Slices time complexity Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-05-20 08:07 -0400
                    Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 22:42 +1000
                      Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 23:24 +1000
                      Re: Slices time complexity Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-20 12:31 +1200
                        Re: Slices time complexity Ben Finney <ben+python@benfinney.id.au> - 2015-05-20 10:42 +1000
                          Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 07:24 +0300
                            Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 21:30 -0700
                              Re: Slices time complexity Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-20 06:06 +0100
                              Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 15:57 +1000
                                Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 09:17 +0300
                                Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 23:23 -0700
                                  Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 09:46 +0300
                                    Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-20 00:03 -0700
                                      Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 10:45 +0300
                                  List semantics [was Re: Slices time complexity] Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 17:23 +1000
                                    Re: List semantics [was Re: Slices time complexity] Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-20 20:54 +1200
                                      Re: List semantics [was Re: Slices time complexity] Ned Batchelder <ned@nedbatchelder.com> - 2015-05-20 04:08 -0700
                                      Re: List semantics [was Re: Slices time complexity] Terry Reedy <tjreedy@udel.edu> - 2015-05-20 14:42 -0400
                                        Re: List semantics [was Re: Slices time complexity] Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-21 11:06 +1200
                                      Re: List semantics [was Re: Slices time complexity] Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-21 12:10 +1000
                                Re: Slices time complexity "Bartc" <bartc@freeuk.com> - 2015-05-20 10:56 +0100
                                  Re: Slices time complexity Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2015-05-20 10:16 +0100
                                  Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-21 15:19 +1000
                                    Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-21 09:20 +0300
                                    Re: Slices time complexity bartc <bart4858@gmail.com> - 2015-05-21 06:34 -0700
                                      Re: Slices time complexity MRAB <python@mrabarnett.plus.com> - 2015-05-21 17:50 +0100
                                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-22 03:16 +1000
                                        Re: Slices time complexity bart4858@gmail.com - 2015-05-21 12:48 -0700
                        Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 12:26 +1000
                          Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-20 12:36 +1000
                          Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 20:02 -0700
                  Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 21:43 +1000
                    Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 18:59 +0300
                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 03:46 +1000
                        Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-20 04:12 +1000
                        Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 21:19 +0300
                          Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 10:43 +1000
                            Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 07:30 +0300
                              Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 15:33 +1000
                                Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 15:58 +1000
                  Re: Slices time complexity Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2015-05-19 15:18 +0100
              Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 04:46 -0700
                Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 05:14 -0700
            Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 18:19 +1000
              Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 04:41 -0700
    Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 19:45 +1000
      Re: Slices time complexity Serhiy Storchaka <storchaka@gmail.com> - 2015-05-19 13:15 +0300
      Re: Slices time complexity Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2015-05-19 12:09 +0100
      Re: Slices time complexity "Bartc" <bartc@freeuk.com> - 2015-05-19 15:52 +0100
        Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 03:07 +1000
          Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-20 03:19 +1000
          Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-20 20:51 +0100
            Re: Slices time complexity Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-20 14:33 -0600
            Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-21 06:35 +1000
            Re: Slices time complexity Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-20 21:47 +0100
              Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-20 22:23 +0100
            Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-21 17:35 +1000
              Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-21 18:25 +1000
      Re: Slices time complexity Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-19 09:15 -0600
      Re: Slices time complexity Serhiy Storchaka <storchaka@gmail.com> - 2015-05-19 22:51 +0300

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#90923

Steven D'Aprano <steve+comp.lang.python@pearwood.info>:

> There is a little magic elf hiding inside the computer, and when you
> type an expression like '2 + 3', little tiny hammers bang it out in
> Morse Code on the elf's head; in response, the elf calculates the
> answer on his teeny tiny abacus and passes it back to the interpreter.

That would be a perfectly valid semantic explanation if it really
predicted the output.

> Since this explanation explains the observed behaviour, according to
> you it is equally valid as one involving, you know, actual facts.

It doesn't explain the observed behavior. It doesn't differentiate
between correct and incorrect outcomes.


Marko

[toc] | [prev] | [next] | [standalone]

#90928

On Wednesday 20 May 2015 14:30, Marko Rauhamaa wrote:

> Steven D'Aprano <steve+comp.lang.python@pearwood.info>:
> 
>> There is a little magic elf hiding inside the computer, and when you
>> type an expression like '2 + 3', little tiny hammers bang it out in
>> Morse Code on the elf's head; in response, the elf calculates the
>> answer on his teeny tiny abacus and passes it back to the interpreter.
> 
> That would be a perfectly valid semantic explanation if it really
> predicted the output.

Which it does. State any mathematical expression involving operators and 
operands supported by Python, and I can express it in Morse code, and tell 
you exactly what result the elf will calculate.

Someone sufficiently killed with an abacus can probably even calculate it 
*using the same algorithms* that the elf will use. Being hit on the head by 
hammers is not compulsory.


>> Since this explanation explains the observed behaviour, according to
>> you it is equally valid as one involving, you know, actual facts.
> 
> It doesn't explain the observed behavior. It doesn't differentiate
> between correct and incorrect outcomes.

Perhaps when I wrote "the elf calculates the answer" it was unclear that I 
meant the *correct* answer rather than some arbitrary value which is not 
actually the answer. I will try to be more clear in the future.


-- 
Steve

[toc] | [prev] | [next] | [standalone]

#90931

On Wednesday 20 May 2015 15:33, Steven D'Aprano wrote:


> Someone sufficiently killed with an abacus

Er, *skilled*.


-- 
Steve

[toc] | [prev] | [next] | [standalone]

#90856

On 19 May 2015 at 09:50, Chris Angelico <rosuav@gmail.com> wrote:
> On Tue, May 19, 2015 at 6:39 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> For example, you could explain Python's object references as pointers
>> (memory addresses) if you considered that helpful. (That's how Lisp
>> textbooks often explain cons cells.)
>
> Sorta-kinda-maybe, but if a C programmer's idea of pointers is invoked
> to explain Python's object references, the differences will start to
> be problematic:
>
> 1) Pointer arithmetic simply doesn't exist in Python. Arrays/lists are
> not just pointers to their first elements, and subscripting is most
> definitely NOT "add to pointer and dereference".
> 2) In fact, dereferencing as a whole isn't really a 'thing' either. At
> best, it happens automatically.
> 3) References actually mean something. Copying a pointer doesn't.
> Whether the Python you're using is refcounted (CPython) or
> mark-and-sweep (uPy, I think) or some other model, an additional
> reference to the same object will prevent it from being disposed of,
> which isn't the case in C.
> 4) A pointer is itself a value. You can pass a
> pointer-to-local-variable to another function and have that function
> change a local variable.

I think this is actually one of those areas where the analogy does
make sense. In Python if I pass an object as an argument to another
function I can mutate the object but I can't rebind the name in the
parent frame. Similarly in C I can pass a pointer to anything into
another function and the other function will be able to mutate the
pointed-to variable but not change the value of the pointer in the
parent frame.

int b = 2;

void f(int* d)
{
    *d = 3; // Changes a which is pointed to by c and d.
    d = &b; // Doesn't affect c.
    *d = 4;  // Changes b
}

int main(int argc, char *argv[])
{
    int a = 1;
    int *c = &a;  // a and *c are the same object
    f(c);
    // c still points to a but a is now 3.
    printf("*c = %d\n", *c);
    return 0;
}

The effect is the same in Python except that I can't use an int for
the demo since they're immutable:

b = [2]

def g(d):
    d[0] = 3 # Changes a which is also c and d
    d = b     # Doesn't affect a or c
    d[0] = 4 # Changes b

def main():
    a = [1]
    c = a   # a and c are the same object
    f(c)
    # c is still a but a is now [3]
    print("c =", c)

main()


Having taught beginners to program with C as a first programming
language and with Python as a first programming language I would say
that in either case this is an important fundamental concept that
beginners need to get their heads round. If a C programmer finds it
easier to understand how Python handles it by relating it to pointers
then that's great.


> 5) Furthermore, since a pointer is a value, you can have pointers to
> pointers, etc. Doesn't make any sense in Python.

You can have a reference to a container object which references other
objects. The effect is more or less the same if you want to understand
how something like this works:

a = [[0] * 5] * 5


--
Oscar

[toc] | [prev] | [next] | [standalone]

#90843

On Tuesday, May 19, 2015 at 12:42:50 PM UTC+5:30, Marko Rauhamaa wrote:
> Rustom Mody :
> 
> > However conceptually/pedagogically making a fundamenal distinction of
> > timeless | time
> > value | object
> > immutable | mutable
> > expression | statement
> > function | procedure
> >
> > is key to getting programming [and is something that Pascal got better
> > than most of its successors].
> >
> > The FPers want to squeeze the whole world into column 1
> > The OOPers want to do the opposite and are embarrassed by the existence of
> > column-1 [status of int in java etc]
> > Unless one is committed to some philosophical extreme position --
> > Only One True Way -- I believe accepting two fundamentals is the most
> > sane choice
> 
> I sympathize. Can you get Python without getting a language like C
> first? Can a baby be born without an umbilical cord? Can you skip Newton
> and go straight to quantum mechanics and relativity? I have noticed some
> experienced Java programmers are a bit lost in the woods because they
> don't have an idea of what is going on under the hood.

And how would you classify C# in this scheme (pun unintended)?

Note that C# is in .Net what C is in Unix -- the primary building block language.

But C# also has claims to being higher level than C like java/python etc.

[toc] | [prev] | [next] | [standalone]

#90844

On Tuesday, May 19, 2015 at 5:16:29 PM UTC+5:30, Rustom Mody wrote:
> On Tuesday, May 19, 2015 at 12:42:50 PM UTC+5:30, Marko Rauhamaa wrote:
> > I sympathize. Can you get Python without getting a language like C
> > first? Can a baby be born without an umbilical cord? Can you skip Newton
> > and go straight to quantum mechanics and relativity? I have noticed some
> > experienced Java programmers are a bit lost in the woods because they
> > don't have an idea of what is going on under the hood.
> 
> And how would you classify C# in this scheme (pun unintended)?
> 
> Note that C# is in .Net what C is in Unix -- the primary building block language.
> 
> But C# also has claims to being higher level than C like java/python etc.

To be fair (and to make the opposite point of what I was making above)
I should describe a recent encounter with some C# folks.
They were doing something in what needed to be a fast loop.
Looking over the code I found some dictionary lookups.
I suggested digesting the dict-key into an int and using arrays instead of dicts.

They did it and got a 10x speedup.

So C# (just as your above cited typical Java programmers) certainly can produce
programmers who are clueless of what's 'under the hood'

[toc] | [prev] | [next] | [standalone]

#90830

On Tuesday 19 May 2015 15:33, Rustom Mody wrote:

> However conceptually/pedagogically making a fundamenal distinction of
> timeless | time
> value | object
> immutable | mutable
> expression | statement
> function | procedure
> 
> is key to getting programming [and is something that Pascal got better
> than most of its successors].

Hmmm. Well, I don't quite know what distinction you are making between 
timeless and time, that's ambiguous, and I strongly disagree with the 
value/object distinction, but the rest seems reasonable.


-- 
Steve

[toc] | [prev] | [next] | [standalone]

#90841

On Tuesday, May 19, 2015 at 1:49:31 PM UTC+5:30, Steven D'Aprano wrote:
> On Tuesday 19 May 2015 15:33, Rustom Mody wrote:
> 
> > However conceptually/pedagogically making a fundamenal distinction of
> > timeless | time
> > value | object
> > immutable | mutable
> > expression | statement
> > function | procedure
> > 
> > is key to getting programming [and is something that Pascal got better
> > than most of its successors].
> 
> Hmmm. Well, I don't quite know what distinction you are making between 
> timeless and time, that's ambiguous, and I strongly disagree with the 
> value/object distinction, but the rest seems reasonable.

Take Pascal and the statement:

y := x+1

A Pascal programmer (and more generally any imperative language programmer)
understands this in two frames:

The 'x+1' is understood mathematically; ie we dont need or wish or encourage
to think of it in terms of machine instructions.

OTOH the 'y := <rhs>' is to be understood procedurally or algorithmically or
in terms of some (maybe half-assed) machine abstraction.

It is only after learning to juggle these two framings that we can deal with
things like
x := x+1

C messes all this badly
1. Illegitimately coopting the '=' symbol for the assignment
2. By making expressions like ++ which are enough to confuse everyone
[ including the compiler eg  i = i++ --- does that increment or is it a no-op?]
3. Expressions are statement-ified by a ';' which discards the top-level value

Python is in some respects better than C -- at least assignment is a statement
In some its worse.  Think how frequent are questions out here on/around
- mixing up list.extend with +; sorted with sort
- comprehensions with side-effecting expressions etc

Think of the straigtforwardness of this error
>>> x = while
  File "<stdin>", line 1
    x = while
            ^
SyntaxError: invalid syntax



with clueless silence of this one:

>>> l = [1,2,3]
>>> l = l.append(4)
>>> l
>>> 

Most answers to issues like the second focus on the fact that None at
top-level vanishes.  A minor nuisance compared the to the real culprit, viz
the append allowable as an rhs.

[toc] | [prev] | [next] | [standalone]

#90837

On Tuesday 19 May 2015 05:23, Mario Figueiredo wrote:

> I'd like to understand what I'm being told about slices in
> https://wiki.python.org/moin/TimeComplexity
> 
> Particularly, what's a 'del slice' and a 'set slice' and whether this
> information pertains to both CPython 2.7 and 3.4.


Get a slice: x = mylist[2:15]

Set a slice: mylist[2:15] = [2, 4, 6, 8]

Del a slice: del mylist[2:15]

 
> From the above link it seems slices work in linear time on all cases.

I wouldn't trust that is always the case, e.g. deleting a contiguous slice 
from the end of a list could be O(1).


> And this really has a big impact on certain operations. For instance,
> the code below may surprise some people when they realize it doesn't
> run in linear time on 3.4:

I'm sure that lots of things surprise people who assume that every 
language's performance characteristics are identical.

Python is not Lisp. Lisp is not Java. Java is not Forth. Forth is not Lua. 
Lua is not Fortran. Fortran is not PHP. Do you see a pattern yet? :-)


>     def minimum(values):
>         if len(values) == 1:
>             return values[0]
>         else:
>             m = minimum(values[1:])
>             return m if m < values[0] else values[0]
> 
> Other languages implement slices. I'm currently being faced with a Go
> snippet that mirrors the exact code above and it does run in linear
> time.

I spot a terminology error here. What Go calls a slice and what Python calls 
a slice are *not the same thing*. A Go slice is a view into an array. Python 
slicing is a *method call* to copy, assign, or delete part of a sequence.

Also, Python slices can accept three arguments, not just two, which may be 
arbitrary objects. Go slices cannot.


> Is there any reason why Python 3.4 implementation of slices cannot be
> a near constant operation?

Yes. (1) Backwards compatibility. (2) That would go against the design of 
Python slices that they are copies. (3) That would upset those who want and 
expect a slice to be a copy.

I'll tell you what -- Python slices have worked this way for over 20 years. 
You should propose to the Go designers that Go is confusing because it 
doesn't match Python's behaviour, and they should change the meaning of 
slices in Go to match Python. There's not as much Go code in the world as 
Python code, so that will be far less disruptive. Tell them that Go should 
be just like Python, otherwise it will confuse users who expect Go slices to 
behave like Python slices.

Do let us know what the Go designers say.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#90838

On 19.05.15 12:45, Steven D'Aprano wrote:
> On Tuesday 19 May 2015 05:23, Mario Figueiredo wrote:
>>  From the above link it seems slices work in linear time on all cases.
>
> I wouldn't trust that is always the case, e.g. deleting a contiguous slice
> from the end of a list could be O(1).

It always has linear complexity. You need to decref removed elements.

[toc] | [prev] | [next] | [standalone]

#90840

On 19 May 2015 at 11:15, Serhiy Storchaka <storchaka@gmail.com> wrote:
> On 19.05.15 12:45, Steven D'Aprano wrote:
>>
>> On Tuesday 19 May 2015 05:23, Mario Figueiredo wrote:
>>>
>>>  From the above link it seems slices work in linear time on all cases.
>>
>>
>> I wouldn't trust that is always the case, e.g. deleting a contiguous slice
>> from the end of a list could be O(1).
>
> It always has linear complexity. You need to decref removed elements.

It has linear complexity in the length of the removed slice but not in
the length of the list. So deleting k elements from the end of a list
of length N is O(k) rather than O(N) which could be a big difference.
An algorithm that repeatedly deletes slices from the end until the
entire list was gone would still be O(N) whereas one that deletes from
the beginning would probably be O(N**2).

--
Oscar

[toc] | [prev] | [next] | [standalone]

#90854

"Steven D'Aprano" <steve+comp.lang.python@pearwood.info> wrote in message
news:555b0621$0$2753$c3e8da3$76491128@news.astraweb.com...
> On Tuesday 19 May 2015 05:23, Mario Figueiredo wrote:

>> And this really has a big impact on certain operations. For instance,
>> the code below may surprise some people when they realize it doesn't
>> run in linear time on 3.4:
>
> I'm sure that lots of things surprise people who assume that every
> language's performance characteristics are identical.
>
> Python is not Lisp. Lisp is not Java. Java is not Forth. Forth is not Lua.
> Lua is not Fortran. Fortran is not PHP. Do you see a pattern yet? :-)

But sometimes you want an algorithm that works perfectly well in one
language to work just as well in another. (Subject to understood factors,
eg, one language is implemented as native code, another byte-code.)

>> Other languages implement slices. I'm currently being faced with a Go
>> snippet that mirrors the exact code above and it does run in linear
>> time.
>
> I spot a terminology error here. What Go calls a slice and what Python
> calls
> a slice are *not the same thing*. A Go slice is a view into an array.
> Python
> slicing is a *method call* to copy, assign, or delete part of a sequence.
>
> Also, Python slices can accept three arguments, not just two, which may be
> arbitrary objects. Go slices cannot.

I'm surprised about the slice thing too; I was getting used to the idea of
Python only passing around references, even to small integer values, and now
here it goes and does a copy!

But apparently only a shallow (top-level) copy. Still, it sounds expensive
if you just want to pass part of a list to a function, not the whole thing,
a function which is not going to write into the list (like the OP's
example).

>> Is there any reason why Python 3.4 implementation of slices cannot be
>> a near constant operation?
>
> Yes. (1) Backwards compatibility. (2) That would go against the design of
> Python slices that they are copies. (3) That would upset those who want
> and
> expect a slice to be a copy.

Or you could just have a different kind of slice that is just a 'view'.
(Python is a big language to which almost everything else has been bolted
on, so why not?)

> I'll tell you what -- Python slices have worked this way for over 20
> years.
> You should propose to the Go designers that Go is confusing because it
> doesn't match Python's behaviour, and they should change the meaning of
> slices in Go to match Python. There's not as much Go code in the world as
> Python code, so that will be far less disruptive. Tell them that Go should
> be just like Python, otherwise it will confuse users who expect Go slices
> to
> behave like Python slices.

I agree with the OP, the way slices work in Python is confusing to those who
expect them to work like array assignments. So if B is a million-element
list, then A=B does not copy a million elements, neither shallow or deep.

But A=B[1:] copies 999999 shallow elements. (Pointers I expect, and might
need to change the reference counts of those 999999 elements. And when that
slice is discarded after perhaps a handful of accesses, it might need to
change them all back. if that is the case, then a 'view' kind of slice would
have been better, with an explicit copy operation if needed.)

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#90872

On Wed, 20 May 2015 12:52 am, Bartc wrote:

> "Steven D'Aprano" <steve+comp.lang.python@pearwood.info> wrote in message
> news:555b0621$0$2753$c3e8da3$76491128@news.astraweb.com...
[...]
>> I'm sure that lots of things surprise people who assume that every
>> language's performance characteristics are identical.
>>
>> Python is not Lisp. Lisp is not Java. Java is not Forth. Forth is not
>> Lua. Lua is not Fortran. Fortran is not PHP. Do you see a pattern yet?
>> :-)
> 
> But sometimes you want an algorithm that works perfectly well in one
> language to work just as well in another.

Yeah, and I want a million dollars, a pony, and the ability to eat as much
as I like without getting fat too. Life is cruel, and then you die.


[...]
> I'm surprised about the slice thing too; I was getting used to the idea of
> Python only passing around references, even to small integer values, and
> now here it goes and does a copy!

Yes. And? Are you surprised that dict.copy() makes a copy? Presumably not.
Well, the way we spell list.copy() is list[:]


> But apparently only a shallow (top-level) copy. Still, it sounds expensive
> if you just want to pass part of a list to a function, not the whole
> thing, a function which is not going to write into the list (like the OP's
> example).

Yes, a slice can be expensive, if you have (say) a ten billion element list,
and take a slice list[1:]. And, to be perfectly honest, there's no real
good solution for that in standard Python. Numpy arrays implement slicing
and cloning of arrays as views, but the Python standard library doesn't
have anything that does the same.

But, really... if you're serious about dealing with huge arrays of data, you
want something like numpy, not Python lists. So *in practice* the lack of
views for lists is a minor nuisance, if that. Having list slices return
copies rather than views avoids more problems than it causes.

On the other hand, if Python implementations would implement slices with
copy-on-write, that would give us the best of both worlds!


>>> Is there any reason why Python 3.4 implementation of slices cannot be
>>> a near constant operation?
>>
>> Yes. (1) Backwards compatibility. (2) That would go against the design of
>> Python slices that they are copies. (3) That would upset those who want
>> and
>> expect a slice to be a copy.
> 
> Or you could just have a different kind of slice that is just a 'view'.

Sure. And you can program it yourself, if you like.

True confession time: I've been using Python for over 15 years. For at least
12 of those years, I've found myself feeling guilty every time I write a
loop like "for x in seq[1:]" to skip the first element, because I'm worried
about copying a huge list. Every single time I think "I really ought to
write a list view." And then I think about the effort involved (minor)
versus the benefit (even smaller) and I think "screw it, I'll just make a
copy".

And in 12 years, this lazy "put off until tomorrow" attitude to list views
has failed me exactly *zero* times. I won't say You're Not Gonna Need It,
but I will say *I've* Never Needed It Yet.

I think that's why Python doesn't have a generalised sequence slice view.
It's not that the core developers are against the idea. It's just that,
weighing up the disadvantages, the advantages, and the effort involved, a
slice view has never been high enough on their priority list to get
included. The people who really need it already have numpy.

What will be off the table is changing the behaviour of list slicing. But
adding a sequence view? That's plausible. It just needs somebody to do the
work first.


>> I'll tell you what -- Python slices have worked this way for over 20
>> years.
>> You should propose to the Go designers that Go is confusing because it
>> doesn't match Python's behaviour, and they should change the meaning of
>> slices in Go to match Python. There's not as much Go code in the world as
>> Python code, so that will be far less disruptive. Tell them that Go
>> should be just like Python, otherwise it will confuse users who expect Go
>> slices to
>> behave like Python slices.
> 
> I agree with the OP, the way slices work in Python is confusing to those
> who expect them to work like array assignments. So if B is a
> million-element list, then A=B does not copy a million elements, neither
> shallow or deep.

Why would you expect slicing to be the same as assignment? Do you expect
list.append to be the same as assignment?

mylist = list(range(40))
mylist[3:26:3] = [1, 2, 3, 4, 5, 6, 7, 8]

How do you expect that to work, if not by copying?


> But A=B[1:] copies 999999 shallow elements. (Pointers I expect, and might
> need to change the reference counts of those 999999 elements. And when
> that slice is discarded after perhaps a handful of accesses, it might need
> to change them all back.

You say that as if it were expensive.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#90875

On Wed, May 20, 2015 at 3:07 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> True confession time: I've been using Python for over 15 years. For at least
> 12 of those years, I've found myself feeling guilty every time I write a
> loop like "for x in seq[1:]" to skip the first element, because I'm worried
> about copying a huge list. Every single time I think "I really ought to
> write a list view." And then I think about the effort involved (minor)
> versus the benefit (even smaller) and I think "screw it, I'll just make a
> copy".
>
> And in 12 years, this lazy "put off until tomorrow" attitude to list views
> has failed me exactly *zero* times. I won't say You're Not Gonna Need It,
> but I will say *I've* Never Needed It Yet.

I can't think of many times when I've needed to do this on a large
list - usually it's either a generic iterable handler (so it has to
call iter() and then next(), and then iterate over what's left), or
it's sys.argv. I literally cannot think of any other situation where
I've iterated over seq[1:] than sys.argv. And if you're passing a
million args to a program, frankly, you have more to worry about than
the cost of trimming off the self-name to iterate over the rest of the
args. Worries like, yaknow, actually doing some work with whatever was
passed in as args, which is likely to dwarf the list slicing time.

ChrisA

[toc] | [prev] | [next] | [standalone]

#90980

On Wed, 20 May 2015 03:07:03 +1000, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:

>Yes, a slice can be expensive, if you have (say) a ten billion element list,
>and take a slice list[1:].

Since nothing seems to surprise you and you seem so adamant on calling
anyone being surprised by it, maybe I will surprise you if you
actually run the code I posted on the OP and witness for yourself that
even on a 50 element list will take 3 seconds to execute on an intel
i5.

>But, really... if you're serious about dealing with huge arrays of data, you
>want something like numpy, not Python lists.

You don't need huge. On any algorithm where slices are being used you
will have to account for the linear complexity. You seem to be
dismissive of this fact, but it can have tremendous performance
implications, since it can turn a linear algorithm into a quadratic
one just like that.

Certainly there are alternatives and iterating through the list is a
much better method. There's no arguing against that. But if you are
paying attention to how Python is being taught, [1:] is a little
everywhere on the web announced as a cool trick showcasing Python
strengths. Well, it turns out it is actually a bad practice
performance-wise under many cases and the alternatives should be the
ones being showcased.

> So *in practice* the lack of views for lists is a minor nuisance, if that.

Your opinion was noted.

> Having list slices return copies rather than views avoids more problems than it causes.

Well, I personally wouldn't want to see slices do anything other than
what they are doing now. I think that is the point. Backwards
compatibilioty being just one of the problems.

But no one is arguing for that. Instead, it was said that it would be
interesting if Python offered views.

>On the other hand, if Python implementations would implement slices with
>copy-on-write, that would give us the best of both worlds!

You are a confusing person. You after all agree with what is being
said, but spend all your time talking against it.

[toc] | [prev] | [next] | [standalone]

#90981

On Wed, May 20, 2015 at 1:51 PM, Mario Figueiredo <marfig@gmail.com> wrote:
> On Wed, 20 May 2015 03:07:03 +1000, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>
>>Yes, a slice can be expensive, if you have (say) a ten billion element list,
>>and take a slice list[1:].
>
> Since nothing seems to surprise you and you seem so adamant on calling
> anyone being surprised by it, maybe I will surprise you if you
> actually run the code I posted on the OP and witness for yourself that
> even on a 50 element list will take 3 seconds to execute on an intel
> i5.

I suspect you've made a mistake in your timing. I measure it at 20.8
microseconds on a Xeon W3690.

>>> def minimum(values):
...     if len(values) == 1:
...         return values[0]
...     else:
...         m = minimum(values[1:])
...         return m if m < values[0] else values[0]
...
>>> from timeit import Timer
>>> t = Timer("minimum(values)", setup="from __main__ import minimum; values = list(range(50))")
>>> min(t.repeat(number=100000))
2.077940827002749

[toc] | [prev] | [next] | [standalone]

#90982

On Thu, May 21, 2015 at 5:51 AM, Mario Figueiredo <marfig@gmail.com> wrote:
> But no one is arguing for that. Instead, it was said that it would be
> interesting if Python offered views.

It's pretty easy, actually. (Slightly more complicated once you handle
more details like negative indexing and strides other than 1, but
still not too hard.)

class View:
    def __init__(self, seq, start=0, end=None):
        self.seq = seq
        self.start = start
        if end is None: self.end = len(seq)
        else: self.end = end
    def __getitem__(self, item):
        if isinstance(item, slice):
            start, end, _ = item.indices(self.end-self.start)
            return View(self.seq, self.start + start, self.start + end)
        if self.start + item >= self.end: raise IndexError
        return self.seq[self.start + item]

Start with any sequence (doesn't have to be a list as such) and
construct a View of it, and then all slicing and dicing happens with
index arithmetic instead of list construction. Indexing of views
transparently works on the underlying sequence, and you can coalesce a
view into a concrete list (eg to allow garbage collection of the
original) with list(v), same as you would with a range object or a
generator or any other iterable.

It's really not that hard.

ChrisA

[toc] | [prev] | [next] | [standalone]

#90983

On 20/05/2015 20:51, Mario Figueiredo wrote:
> On Wed, 20 May 2015 03:07:03 +1000, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>
>> Yes, a slice can be expensive, if you have (say) a ten billion element list,
>> and take a slice list[1:].
>
> Since nothing seems to surprise you and you seem so adamant on calling
> anyone being surprised by it, maybe I will surprise you if you
> actually run the code I posted on the OP and witness for yourself that
> even on a 50 element list will take 3 seconds to execute on an intel
> i5.
>

Please provide the figures to back up this claim.  Nothing personal but 
we've had problems with the RUE (amongst others) making nonsensical 
claims, please don't take us down that path, thank you.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#90986

On Wed, 20 May 2015 21:47:46 +0100, Mark Lawrence
<breamoreboy@yahoo.co.uk> wrote:

>Please provide the figures to back up this claim.  Nothing personal but 
>we've had problems with the RUE (amongst others) making nonsensical 
>claims, please don't take us down that path, thank you.

Alright. My apologies. This answer of yours along with Ian's made me
realize something was wrong with my measurements. And it was indeed.
Thankfully not the code which I show below. But the fact I wasn't
aware -- until you guys forced me to dig in what was going on -- that
timeit.timeit defaults to 1 million passes.

>#!/usr/bin/env python3
> 
>import random
>import timeit
> 
>def minimum(values):
>    if len(values) == 1:
>        return values[0]
>    else:
>        m = minimum(values[1:])
>        return m if m < values[0] else values[0]
> 
>a5 = [random.randint(0, 1000) for _ in range(5)]
>a50 = [random.randint(0, 1000) for _ in range(50)]
>a500 = [random.randint(0, 1000) for _ in range(500)]
> 
>setup = 'from __main__ import minimum, a5, a50, a500'
> 
>print('Baseline: {:.2f}s'.format(timeit.timeit('minimum(a5)', setup=setup)))
>print('x10  -> {:.2f}s'.format(timeit.timeit('minimum(a50)', setup=setup)))
>print('x100 -> {:.2f}s'.format(timeit.timeit('minimum(a500)', setup=setup)))

One run output is:
   
   Baseline: 2.86s
   x10  -> 36.72s
   x100 -> 1021.07s

Which, as you can see, I misinterpreted as being the result of a
single pass.

The performance was shocking. And I was going to get to that on
another thread. The slice linear time alone couldn't explain it. But
looking more carefully at the documentation revealed my error.

[toc] | [prev] | [next] | [standalone]

#91000

On Thursday 21 May 2015 05:51, Mario Figueiredo wrote:

> On Wed, 20 May 2015 03:07:03 +1000, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
[...]
>>But, really... if you're serious about dealing with huge arrays of data,
>>you want something like numpy, not Python lists.
> 
> You don't need huge. On any algorithm where slices are being used you
> will have to account for the linear complexity. You seem to be
> dismissive of this fact, but it can have tremendous performance
> implications, since it can turn a linear algorithm into a quadratic
> one just like that.

Sure. And for small enough N, everything is fast.

There's a sorting algorithm, usually called "Bozo sort", which shuffles the 
list, then checks whether it is sorted. If not, it shuffles it again, until 
it is sorted. Bozo sort is a *terrible* algorithm, with no upper limit to 
the worst case, and O(N!) for the average case. And yet, with small lists 
(say, five items) the performance is acceptable if your requirements are 
low.

Should you use Bozo sort in production? No, of course not. But the point I 
am making is that Big Oh analysis doesn't tell you how fast a particular 
implementation will run, only how it will scale for "sufficiently large" N. 
An O(N**2) algorithm with a small multiplier may be much faster than an O(N) 
algorithm with a large multiplier for all the data sets you care about.


> Certainly there are alternatives and iterating through the list is a
> much better method. There's no arguing against that. But if you are
> paying attention to how Python is being taught, [1:] is a little
> everywhere on the web announced as a cool trick showcasing Python
> strengths. Well, it turns out it is actually a bad practice
> performance-wise under many cases 

That has not been my experience, or many other people's.

If your experience is different from mine, then as I said, there is numpy, 
or you can write your own views. Just make sure that in trying to optimize 
your code, you don't end up actually making it *slower* by optimizing for 
more data than you ever will, or could, have to deal with. Big Oh 
theoretical analysis only goes so far, you need actual benchmarks and 
profiling to make good decisions about which algorithm you should use.



-- 
Steve

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.lang.python

csiph-web