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

Groups > comp.lang.python > #90811

Re: Slices time complexity

Path csiph.com!usenet.pasdenom.info!gegeweb.org!newsfeed0.kamp.net!newsfeed.kamp.net!feeder1.cambriumusenet.nl!feed.tweaknews.nl!194.109.133.83.MISMATCH!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path <ian.g.kelly@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.001
X-Spam-Evidence '*H*': 1.00; '*S*': 0.00; 'python,': 0.02; 'cpython': 0.05; 'modified': 0.07; '[0,': 0.09; 'arrays': 0.09; 'linear': 0.09; 'slices': 0.09; 'snippet': 0.09; 'python': 0.11; '2.7': 0.14; 'constructs': 0.16; 'deleted,': 0.16; 'it),': 0.16; 'otoh,': 0.16; 'replaced.': 0.16; 'semantics': 0.16; 'shared.': 0.16; 'slice.': 0.16; 'underlying': 0.16; 'wrote:': 0.18; 'looked': 0.18; 'work,': 0.20; '>>>': 0.22; 'basis,': 0.24; 'url:moin': 0.24; 'mon,': 0.24; '(or': 0.24; 'header:In-Reply-To:1': 0.27; 'array': 0.29; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'code': 0.31; 'url:wiki': 0.31; 'constant': 0.31; 'piece': 0.31; 'reflected': 0.31; 'lists': 0.32; 'languages': 0.32; 'run': 0.32; 'url:python': 0.33; 'subject:time': 0.33; "i'd": 0.34; 'could': 0.34; 'something': 0.35; 'anybody': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'possible': 0.36; 'url:org': 0.36; 'list': 0.37; 'list.': 0.37; 'being': 0.38; 'implement': 0.38; 'to:addr :python-list': 0.38; 'pm,': 0.38; 'expect': 0.39; 'does': 0.39; 'to:addr:python.org': 0.39; 'information': 0.63; '2015': 0.84; '3.4': 0.84; 'different.': 0.84; 'mirrors': 0.84; 'pertains': 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:from:date:message-id:subject:to :content-type; bh=4TSDJOF6v5ITThiAPIT+CBV5vM4CrbiUZIYn8hCY4X8=; b=eDodq+Tgx/PIUCHzuUp2FzVPcd6poAYx7nqJ9PNk8xluiP2F15kA5N0b+1rZjFf1WV a2KcptzPgCNW3z51FsHfNnxFW7G/SiB62++MGHNX3oV/7tr9bO3DiqTClJpiWxQn3UQY S8aZIrFMzuHFTTQOAUR4zWbuDoRvfGFMgK71vNxTHu7LUXQynLmBC1ltek1Zocq4j61N KTuRR3AAPc/OA6tckQliPmkWBE05hvq5GJQ7zYwXPwJmJxR6c/LLPvaa/BE7lhmQVHfj nPgrpm7tDrats4QBKVRQhIGmVJgElSFCOgpG8hM5xwzmMux+KcwinON7fOh7g7A3258H Jj9w==
X-Received by 10.107.136.89 with SMTP id k86mr29933631iod.63.1431978625518; Mon, 18 May 2015 12:50:25 -0700 (PDT)
MIME-Version 1.0
In-Reply-To <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
References <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
From Ian Kelly <ian.g.kelly@gmail.com>
Date Mon, 18 May 2015 13:49:45 -0600
Subject Re: Slices time complexity
To Python <python-list@python.org>
Content-Type text/plain; charset=UTF-8
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.114.1431978628.17265.python-list@python.org> (permalink)
Lines 36
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1431978628 news.xs4all.nl 2825 [2001:888:2000:d::a6]:32926
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:90811

Show key headers only | View raw

On Mon, May 18, 2015 at 1:23 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.

"Del Slice" is the operation where a slice of a list is deleted, and
"Set Slice" is the operation where a slice is replaced. E.g.:

>>> x = list(range(100))
>>> del x[2:98]
>>> x
[0, 1, 98, 99]
>>> x[1:3] = [7, 6, 5, 4, 3]
>>> x
[0, 7, 6, 5, 4, 3, 99]


> 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?

The semantics are different. IIRC, a slice in Go is just a view of
some underlying array; if you change the array (or some other slice of
it), the change will be reflected in the slice. A slice of a list in
Python, OTOH, constructs a completely independent list.

It may be possible that lists in CPython could be made to share their
internal arrays with other lists on a copy-on-write basis, which could
allow slicing to be O(1) as long as neither list is modified while the
array is being shared. I expect this would be a substantial piece of
work, and I don't know if it's something that anybody has looked into.

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