Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Chris Angelico Newsgroups: comp.lang.python Subject: Re: PEP Request: Advanced Data Structures Date: Sun, 17 Jul 2016 11:30:25 +1000 Lines: 14 Message-ID: References: <20160717005426.GA50011@cskk.homeip.net> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: news.uni-berlin.de 7R/nBX4Z9rjMjhGTHFff8g7YRe91ap9wD5twl7wZcj8A== Return-Path: 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; 'context': 0.05; 'subject:PEP': 0.07; 'type,': 0.07; 'insertion': 0.09; 'tracing': 0.09; 'size,': 0.13; '10:54': 0.16; '2016': 0.16; 'fly': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'massively': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; "someone's": 0.16; 'structure.': 0.16; 'subject:Advanced': 0.16; 'too?': 0.16; 'wrote:': 0.16; "wouldn't": 0.16; 'element': 0.18; 'to:name:python-list@python.org': 0.20; 'level,': 0.22; 'am,': 0.23; 'elements': 0.23; 'insert': 0.23; 'header:In-Reply-To:1': 0.24; 'point.': 0.27; 'message-id:@mail.gmail.com': 0.27; 'occasional': 0.29; "i'm": 0.30; 'becomes': 0.30; "i'd": 0.31; 'operations': 0.31; 'core': 0.32; 'up.': 0.32; 'doubt': 0.33; 'list': 0.34; 'received:google.com': 0.35; 'list,': 0.36; 'faster': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'data': 0.39; 'sure': 0.39; 'to:addr:python.org': 0.40; 'your': 0.60; 'more': 0.63; 'subject:Data': 0.66; 'costs': 0.67; 'jul': 0.72; 'chrisa': 0.84; "that'll": 0.84 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; bh=CxWYnp1SlAkz0PnxS/3E2D63EH2mxykLq7q3p5ocXn8=; b=ZPeYIvz4O8/ELqv/rFmcDBExuEhb1PySPs+OgMqLN7ooJ4HugV1XYi+kYdx5iJ8Bjf e94uoIGTTG8xHSl2tkZPx3HPMJxabYVSMCplLM+piP32B7vUafl9vmqbyqwhofVJzfmX 9Q2FOWKe3zLfEf6PjHb08HNsP/oqCxtTTCsLXUxEezkL1yuPJNVvAX/MZHdhDPbxwVMz vViFY8YySv/DyDgMvWNi+7RF61Iz+ixaYfiPPkYpEQ7I4yCISHLXhR3nhneDB25UIBn5 0mFST1gd2gEBKvzgjLx2NCXKrjZW1VgNAP6ZZvTb1STOEfLpl+0cZ29jVrDWrZUqXTx9 Gjog== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=CxWYnp1SlAkz0PnxS/3E2D63EH2mxykLq7q3p5ocXn8=; b=eI6frd1/c7OB/CCabdYqqE9AOOzdyyh7lDN2X+hsyUgCsx2QfGJu5KMhPXYldYXPIo to4eyGWUsb7RseUdcLimq1oq5hbAAhZE6uvKJXl4/35KbjaZqGhvzgXF7E9yPGWX/p6N RS00xHeDwo06BDq4kNxR7XRxLuutdip+bD9UYdqXmAR4q5dQxxZ5eAl1d+9O7XPaH/qp +egmpEP+Sx9Or35R34RPZoK8KKILFoUbZgpsyD94ffV3xN33ynV2dOyoHNvu3kadY3tl 6M958muOUFfYMyvr/h754AoUCrAyOWhUVJT2mDS7yVChiN7u0MWcCJ0vGJyPYkKawZUt JCPA== X-Gm-Message-State: ALyK8tJ39XtVWMm+wXFyVZVQeBk69rdGk4X2EAaxjSYtppx3Lf4p7YDr5JzyTMeiHXuVPkj2n4TnChenBsdDmg== X-Received: by 10.28.50.199 with SMTP id y190mr40348738wmy.61.1468719026379; Sat, 16 Jul 2016 18:30:26 -0700 (PDT) In-Reply-To: <20160717005426.GA50011@cskk.homeip.net> X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Mailman-Original-Message-ID: X-Mailman-Original-References: <20160717005426.GA50011@cskk.homeip.net> Xref: csiph.com comp.lang.python:111536 On Sun, Jul 17, 2016 at 10:54 AM, wrote: > Well, in a larger context you can keep a reference to an element deep in the > list, and insert a new element in O(1) time at that point. > I'd like to know how many elements your list needs before that actually becomes faster than CPython's heavily-optimized C-implemented list structure. And if someone's proposing a new core data type, I very much doubt that'll fly - and at the C level, wouldn't tracing the links cost massively more than the occasional insertion too? I'm not sure O(1) is of value at any size, if the costs of all your other operations go up. ChrisA