Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed3a.news.xs4all.nl!xs4all!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.004 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'cpython': 0.05; 'memory.': 0.07; 'modified': 0.07; 'string': 0.09; 'arrays': 0.09; 'sure,': 0.09; 'python': 0.11; 'thread': 0.14; '>>': 0.16; 'matlab': 0.16; 'numpy': 0.16; 'shared.': 0.16; 'wrote:': 0.18; '(not': 0.18; 'looked': 0.18; 'work,': 0.20; '>>>': 0.22; 'memory': 0.22; 'import': 0.22; 'email addr:gmail.com>': 0.22; '>>>': 0.24; 'basis,': 0.24; '>': 0.26; 'header:In-Reply-To:1': 0.27; 'array': 0.29; 'message-id:@mail.gmail.com': 0.30; 'piece': 0.31; 'lists': 0.32; 'subject:time': 0.33; 'could': 0.34; 'something': 0.35; 'anybody': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'doing': 0.36; 'possible': 0.36; 'list': 0.37; 'being': 0.38; 'skip:& 10': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'recent': 0.39; 'expect': 0.39; 'to:addr:python.org': 0.39; 'ian': 0.60; 'skip:n 10': 0.64; 'approaches': 0.68; '2015': 0.84; 'complexity': 0.84; 'penalty': 0.84 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=C1wk9d2rwquJsp4jtecwwNQ13yrSku5mhlDHK23Rvyk=; b=A0UhxNvreSA2llQw/mgO6zDWx1RIOlydWvHvcwDDCHOWZQke/fFY5f/JeznT9ky+Pm t6nmlOEX01D9W2T/AL+VyqCCi1tvQpwYA5c3p/Jr57OFbs3OPU4y/YnVHkImx30t5wnu EUVWc0JIhdCBmClSURukc3pWH4tnNAwkZIJQqkQQaTH+MF795fRGEaa9YxeNGyCn/s+W 6kxr1XvMkwyUBOy9cjKa67s6lCU0Aet3vThuqjIQZ/Sm5AO4PaiF+XYgjeWQsF5Xhu2U 2qFaYNIy4FMfBKItCuJwW+TpuriAYnFpnSsyYryiQmAtZfeHB1HNqxRSQYFAu8oHRmsm fYCA== MIME-Version: 1.0 X-Received: by 10.194.57.40 with SMTP id f8mr27257192wjq.86.1431980621182; Mon, 18 May 2015 13:23:41 -0700 (PDT) In-Reply-To: References: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com> Date: Mon, 18 May 2015 22:23:41 +0200 Subject: Re: Slices time complexity From: Todd To: python-list@python.org Content-Type: multipart/alternative; boundary=047d7ba97b9c40407c051660f8a8 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: 74 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1431980629 news.xs4all.nl 2920 [2001:888:2000:d::a6]:49368 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:90814 --047d7ba97b9c40407c051660f8a8 Content-Type: text/plain; charset=UTF-8 On May 18, 2015 9:56 PM, "Fabien" wrote: > > On 05/18/2015 09:49 PM, Ian Kelly wrote: >> >> 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. > > > Isn't Numpy doing this (not sure, not a python nor a numpy expert): > > >>> import numpy as np > >>> a = np.array([1,2,3,4]) > >>> b = a[1:] > >>> b[0] = 9 > >>> a > array([1, 9, 3, 4]) > > > Fabien Numpy arrays use views. Matlab arrays use copy-on-write. But as discussed in the recent thread about string views, these approaches have a memory penalty since they require keeping the original array in memory. And the copy-on-write approach still has a O(k) complexity if you try to make any changes. --047d7ba97b9c40407c051660f8a8 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable


On May 18, 2015 9:56 PM, "Fabien" <fabien.maussion@gmail.com> wrote:
>
> On 05/18/2015 09:49 PM, Ian Kelly wrote:
>>
>> It may be possible that lists in CPython could be made to share th= eir
>> internal arrays with other lists on a copy-on-write basis, which c= ould
>> 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.
>
>
> Isn't Numpy doing this (not sure, not a python nor a numpy expert)= :
>
> >>> import numpy as np
> >>> a =3D np.array([1,2,3,4])
> >>> b =3D a[1:]
> >>> b[0] =3D 9
> >>> a
> array([1, 9, 3, 4])
>
>
> Fabien

Numpy arrays use views. Matlab arrays use copy-on-write.=C2= =A0 But as discussed in the recent thread about string views, these approac= hes have a memory penalty since they require keeping the original array in = memory. And the copy-on-write approach still has a O(k) complexity if you t= ry to make any changes.

--047d7ba97b9c40407c051660f8a8--