Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!feeder1.cambriumusenet.nl!feed.tweaknews.nl!194.109.133.83.MISMATCH!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'python,': 0.02; 'from:addr:yahoo.co.uk': 0.04; 'cpython': 0.05; 'modified': 0.07; 'arrays': 0.09; 'chunk': 0.09; 'lawrence': 0.09; 'linear': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'slices': 0.09; 'snippet': 0.09; 'python': 0.11; 'language.': 0.14; 'constructs': 0.16; 'ian.': 0.16; 'it),': 0.16; 'otoh,': 0.16; 'pypy.': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'semantics': 0.16; 'shared.': 0.16; 'slice.': 0.16; 'underlying': 0.16; 'url:peps': 0.16; 'url:whatsnew': 0.16; 'language': 0.16; 'wrote:': 0.18; 'code.': 0.18; 'looked': 0.18; 'basically': 0.19; 'work,': 0.20; '>>>': 0.22; 'header:User-Agent:1': 0.23; 'basis,': 0.24; 'url:dev': 0.24; 'mon,': 0.24; '(or': 0.24; 'header:X -Complaints-To:1': 0.27; 'header:In-Reply-To:1': 0.27; 'idea': 0.28; 'array': 0.29; 'besides': 0.30; "i'm": 0.30; 'code': 0.31; 'that.': 0.31; 'constant': 0.31; 'piece': 0.31; 'reflected': 0.31; 'though.': 0.31; 'lists': 0.32; 'languages': 0.32; 'run': 0.32; 'url:python': 0.33; 'subject:time': 0.33; 'sense': 0.34; 'could': 0.34; 'something': 0.35; 'anybody': 0.35; 'point.': 0.35; 'but': 0.35; 'there': 0.35; 'possible': 0.36; 'url:org': 0.36; 'should': 0.36; 'changing': 0.37; 'list': 0.37; 'list.': 0.37; 'being': 0.38; 'implement': 0.38; 'thank': 0.38; 'url:library': 0.38; 'to:addr:python-list': 0.38; 'expect': 0.39; 'does': 0.39; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'even': 0.60; 'skip:u 10': 0.60; 'ian': 0.60; 'new': 0.61; 'url:3': 0.61; 'our': 0.64; 'more': 0.64; 'specialized': 0.65; 'charset:windows-1252': 0.65; '2015': 0.84; '3.4': 0.84; 'different.': 0.84; 'mirrors': 0.84; 'received:2': 0.84; 'faced': 0.91 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Mark Lawrence Subject: Re: Slices time complexity Date: Mon, 18 May 2015 22:38:26 +0100 References: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com> <19kkla9krk0auuivanhh39lfc8i1csf2ja@4ax.com> Mime-Version: 1.0 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: host-2-98-199-132.as13285.net User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0 In-Reply-To: <19kkla9krk0auuivanhh39lfc8i1csf2ja@4ax.com> X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 49 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1431985132 news.xs4all.nl 2938 [2001:888:2000:d::a6]:34886 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:90817 On 18/05/2015 22:04, Mario Figueiredo wrote: > On Mon, 18 May 2015 13:49:45 -0600, Ian Kelly > wrote: > >>> 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. > > This is what I was after. Thank you Ian. > > So we basically don't have a view of a list. Makes sense now, since > slice does create a new list. I should have seen that. Thank you once > again. > > It would a good addition though. Even if only on specialized > implementations like pypy. Inspecting and not changing lists is a good > chunk of our code. But that's besides the point. I was more interested > in understanding the behavior. Thank you once again. > Not directly affecting slices but the idea of views has come into Python 3, please see:- https://www.python.org/dev/peps/pep-3118/ https://docs.python.org/3/whatsnew/3.3.html#pep-3118-new-memoryview-implementation-and-buffer-protocol-documentation https://docs.python.org/3/library/stdtypes.html#typememoryview -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence