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

Groups > comp.lang.python > #90810

Re: Slices time complexity

Path csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!border1.nntp.ams1.giganews.com!nntp.giganews.com!bcyclone02.am1.xlned.com!bcyclone02.am1.xlned.com!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <toddrjen@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.013
X-Spam-Evidence '*H*': 0.97; '*S*': 0.00; 'else:': 0.03; 'cpython': 0.05; 'items)': 0.09; 'linear': 0.09; 'pointers': 0.09; 'slices': 0.09; 'snippet': 0.09; 'python': 0.11; 'def': 0.12; '2.7': 0.14; 'changes': 0.15; 'matlab': 0.16; 'numpy': 0.16; 'operation,': 0.16; 'operation.': 0.16; 'values[0]': 0.16; 'wrote:': 0.18; '&lt;': 0.19; 'seems': 0.21; 'memory': 0.22; 'email addr:gmail.com&gt;': 0.22; 'instance,': 0.24; 'url:moin': 0.24; '(or': 0.24; '&gt;': 0.26; 'certain': 0.27; 'header:In-Reply- To:1': 0.27; '(this': 0.29; "doesn't": 0.30; 'involving': 0.30; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'code': 0.31; 'url:wiki': 0.31; 'constant': 0.31; 'operations.': 0.31; 'languages': 0.32; 'run': 0.32; 'url:python': 0.33; 'subject:time': 0.33; 'copying': 0.34; "i'd": 0.34; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'really': 0.36; 'possible': 0.36; 'url:org': 0.36; 'list': 0.37; 'list.': 0.37; 'being': 0.38; 'implement': 0.38; 'problems': 0.38; 'to:addr :python-list': 0.38; 'list,': 0.38; 'pm,': 0.38; 'rather': 0.38; 'does': 0.39; 'realize': 0.39; 'structure': 0.39; 'to:addr:python.org': 0.39; 'how': 0.40; 'impact': 0.61; 'new': 0.61; 'information': 0.63; 'more': 0.64; 'different': 0.65; 'surprise': 0.74; '2015': 0.84; '3.4': 0.84; 'avoids': 0.84; 'mirrors': 0.84; 'pertains': 0.84; 'works)': 0.84; 'faced': 0.91
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=FQ9d21QFHtf8DB3QFABOMCOar+mziy1VMTJtleDU6kg=; b=p7f/eaZKcFdfy7Syq61vTx/kJ87IVwYl6+6dH7A8DNnaFEw00gjxRDiMWEjmFekqnH kTE0LDuL1DvA2DEekNgKOuek9zrevH6ryeJmcqqZFnDo0gmSQ1c6hNHlf9Dwp3P2d9PS es6QqH2+OB8oz9mlonn8bqkTE6FteQ7C5S1tf+H9CEW2AMdYDGmFxBYW8Yzrjm7340y6 Nu2K9gTmk4QO9nqNbh38rQN3Y8VvS6OuOHl+F1qbX5wqfSDjVJQ/ytX1VDC6O+d3NHmm hHT+GCArZ9l4eh0/s1awtoCkD083YgLMNR37DMEnVHe0PhG1tnuhB4c86NANqpoiVrfg niSQ==
MIME-Version 1.0
X-Received by 10.180.76.37 with SMTP id h5mr7430515wiw.85.1431978131311; Mon, 18 May 2015 12:42:11 -0700 (PDT)
In-Reply-To <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
References <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
Date Mon, 18 May 2015 21:42:11 +0200
Subject Re: Slices time complexity
From Todd <toddrjen@gmail.com>
To python-list@python.org
Content-Type multipart/alternative; boundary=f46d04343942d7d28a0516606300
X-Mailman-Approved-At Mon, 18 May 2015 21:49:53 +0200
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.20+
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.113.1431978594.17265.python-list@python.org> (permalink)
Lines 103
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1431978594 news.xs4all.nl 2933 [2001:888:2000:d::a6]:60108
X-Complaints-To abuse@xs4all.nl
X-Received-Bytes 8336
X-Received-Body-CRC 133420653
Xref csiph.com comp.lang.python:90810

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

On May 18, 2015 9:26 PM, "Mario Figueiredo" <marfig@gmail.com> 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.
>
> From the above link it seems slices work in linear time on all cases.
> 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:
>
>     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.
>
> Is there any reason why Python 3.4 implementation of slices cannot be
> a near constant operation?

In this case you are copying the items (or rather pointers to the items)
from the list to a new list. This is inherently a O(k) operation.

There are other ways to implement it. I recall the was talk of a way to get
views of sequences, although this would involve keeping the original list
in memory and any changes to the new list would be passed to the original
(this is how numpy works) . It is also possible to do copy-on-write, which
avoids altering the original list but has the same memory problems while
still involving a O(k) copy operation if you want to change the list, and
it is more complex to implement (this is how MATLAB works) .

But to have a new list that can be edited independently requires coping
something, and that will be a O(k) operation, unless you use a radically
different data structure with its own limitations.

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