Re: PEP Request: Advanced Data Structures

Path	csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From	MRAB <python@mrabarnett.plus.com>
Newsgroups	comp.lang.python
Subject	Re: PEP Request: Advanced Data Structures
Date	Sun, 17 Jul 2016 03:49:06 +0100
Lines	17
Message-ID	<mailman.51.1468723750.2307.python-list@python.org> (permalink)
References	<fphlobd109lvi2e4r4oe4qjpcf97chhe67@4ax.com> <20160717005426.GA50011@cskk.homeip.net> <CAPTjJmpfPBMwT5zSM43zonUht_AY2dpzqwSv53XZiX5OZMCoig@mail.gmail.com> <mailman.49.1468719034.2307.python-list@python.org> <871t2tdme3.fsf@jester.gateway.pace.com> <a5653860-f208-ac37-500e-659c677efdce@mrabarnett.plus.com>
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding	7bit
X-Trace	news.uni-berlin.de wtHjZZ+vk/zSdkaZa2sEYABA9pnfNRlpa+1DBtRCm73g==
Return-Path	<python@mrabarnett.plus.com>
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; 'linear': 0.07; 'subject:PEP': 0.07; 'ugly': 0.07; 'dict': 0.09; 'insertion': 0.09; 'lookup': 0.09; 'tracing': 0.09; 'python.': 0.11; 'language,': 0.11; 'size,': 0.13; 'appropriate': 0.14; 'from:addr:mrabarnett.plus.com': 0.16; 'from:addr:python': 0.16; 'from:name:mrab': 0.16; 'lookups': 0.16; 'massively': 0.16; 'message-id:@mrabarnett.plus.com': 0.16; 'node.': 0.16; 'received:192.168.1.4': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'subject:Advanced': 0.16; 'too?': 0.16; 'wrote:': 0.16; "wouldn't": 0.16; 'element': 0.18; '>>>': 0.20; 'level,': 0.22; 'decide': 0.23; 'insert': 0.23; 'header:In-Reply- To:1': 0.24; 'paul': 0.24; 'header:User-Agent:1': 0.26; 'example': 0.26; 'chris': 0.26; 'point.': 0.27; 'idea': 0.28; 'occasional': 0.29; "i'm": 0.30; 'operations': 0.31; 'up.': 0.32; 'table': 0.32; 'though,': 0.32; 'though.': 0.33; 'list': 0.34; 'something': 0.35; "isn't": 0.35; 'item': 0.35; 'list,': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'really': 0.37; 'list.': 0.37; 'doing': 0.38; 'front': 0.38; 'sure': 0.39; 'received:192': 0.39; 'to:addr:python.org': 0.40; 'where': 0.40; 'your': 0.60; 'bring': 0.62; 'more': 0.63; 'subject:Data': 0.66; 'costs': 0.67; 'search,': 0.72; 'surgery': 0.91
X-CM-Score	0.00
X-CNFS-Analysis	v=2.2 cv=dMLko6Rb c=1 sm=1 tr=0 a=0nF1XD0wxitMEM03M9B4ZQ==:117 a=0nF1XD0wxitMEM03M9B4ZQ==:17 a=IkcTkHD0fZMA:10 a=pGLkceISAAAA:8 a=be-B-5Ge8aLY_59ACLYA:9 a=6kGIvZw6iX1k4Y-7sg4_:22
X-AUTH	mrabarnett@:2500
User-Agent	Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0
In-Reply-To	<871t2tdme3.fsf@jester.gateway.pace.com>
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.22
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>
X-Mailman-Original-Message-ID	<a5653860-f208-ac37-500e-659c677efdce@mrabarnett.plus.com>
X-Mailman-Original-References	<fphlobd109lvi2e4r4oe4qjpcf97chhe67@4ax.com> <20160717005426.GA50011@cskk.homeip.net> <CAPTjJmpfPBMwT5zSM43zonUht_AY2dpzqwSv53XZiX5OZMCoig@mail.gmail.com> <mailman.49.1468719034.2307.python-list@python.org> <871t2tdme3.fsf@jester.gateway.pace.com>
Xref	csiph.com comp.lang.python:111540

Show key headers only | View raw

On 2016-07-17 03:33, Paul Rubin wrote:
> Chris Angelico <rosuav@gmail.com> writes:
>>> keep a reference to an element deep in the list, and insert a new
>>> element in O(1) time at that point.
>> 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.
>
> I think the idea is that you're already deep in the list when you decide
> to insert an element or do other surgery on the list.  An example might
> be a lookup table with linear search, where you want to bring the LRU
> item to the front of the list after finding it.  Really though, that's
> an ugly thing to be doing in any language, and it definitely isn't
> something that comes up much in Python.
>
I once sped up lookups on a doubly-linked list by adding a dict that 
would take me straight to the appropriate node. This was in C, though.

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Re: PEP Request: Advanced Data Structures Chris Angelico <rosuav@gmail.com> - 2016-07-17 11:30 +1000
  Re: PEP Request: Advanced Data Structures Paul Rubin <no.email@nospam.invalid> - 2016-07-16 19:33 -0700
    Re: PEP Request: Advanced Data Structures Chris Angelico <rosuav@gmail.com> - 2016-07-17 12:43 +1000
    Re: PEP Request: Advanced Data Structures MRAB <python@mrabarnett.plus.com> - 2016-07-17 03:49 +0100

csiph-web