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

Groups > comp.lang.python > #91000

Re: Slices time complexity

From Steven D'Aprano <steve+comp.lang.python@pearwood.info>
Date 2015-05-21 17:35 +1000
Subject Re: Slices time complexity
Newsgroups comp.lang.python
References <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com> <555b0621$0$2753$c3e8da3$76491128@news.astraweb.com> <mjff5g$met$1@dont-email.me> <555b6db8$0$12996$c3e8da3$5496439d@news.astraweb.com> <adoplatr4fq8nssa9s2pk3bbpmhtkdk775@4ax.com>
Followup-To comp.lang.python
Message-ID <555d8ae3$0$11095$c3e8da3@news.astraweb.com> (permalink)
Organization Unlimited download news at news.astraweb.com

Followups directed to: comp.lang.python

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web