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

Groups > comp.lang.python > #111547

Re: PEP Request: Advanced Data Structures

Path csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From Tim Chase <python.list@tim.thechases.com>
Newsgroups comp.lang.python
Subject Re: PEP Request: Advanced Data Structures
Date Sat, 16 Jul 2016 19:45:10 -0500
Lines 34
Message-ID <mailman.56.1468732603.2307.python-list@python.org> (permalink)
References <21fcec53-cf5b-4529-9790-63a1c46f534b@googlegroups.com> <CAPTjJmpQk9SwLRct-WpZMywFFLhX3A459eNzB5eHGVFyhBiDoA@mail.gmail.com> <20160716194510.6283c8f4@bigbox.christie.dr>
Mime-Version 1.0
Content-Type text/plain; charset=US-ASCII
Content-Transfer-Encoding 7bit
X-Trace news.uni-berlin.de b72ntorBwq6eil0S7SyJ5gQ9DszI5g9Z5oyWmHV7K8UA==
Return-Path <python.list@tim.thechases.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.003
X-Spam-Evidence '*H*': 0.99; '*S*': 0.00; 'list?': 0.07; 'subject:PEP': 0.07; 'alternatives': 0.09; '-tkc': 0.16; 'bisect': 0.16; 'deque': 0.16; 'from:addr:python.list': 0.16; 'from:addr:tim.thechases.com': 0.16; 'from:name:tim chase': 0.16; 'heapq': 0.16; 'n),': 0.16; 'pypi.': 0.16; 'received:10.21': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'skip:{ 30': 0.16; 'subject:Advanced': 0.16; 'time"': 0.16; 'wrote:': 0.16; 'nested': 0.18; 'algorithm': 0.20; 'handles': 0.20; 'fairly': 0.22; 'for?': 0.23; 'header:In-Reply-To:1': 0.24; 'rest': 0.26; 'chris': 0.26; 'specifically': 0.28; 'actual': 0.28; 'regular': 0.29; "i'm": 0.30; 'usually': 0.33; 'lists': 0.34; 'something': 0.35; 'instead': 0.36; 'there': 0.36; 'serve': 0.36; 'basic': 0.36; 'modules': 0.36; 'structures': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'beyond': 0.37; 'charset :us-ascii': 0.37; 'anything': 0.38; 'log': 0.38; 'why': 0.39; 'to:addr:python.org': 0.40; 'where': 0.40; 'some': 0.40; 'linked': 0.63; 'times': 0.63; 'subject:Data': 0.66; 'wanting': 0.66; 'received:23': 0.84
X-Sender-Id wwwh|x-authuser|tim@thechases.com
X-Sender-Id wwwh|x-authuser|tim@thechases.com
X-MC-Relay Neutral
X-MailChannels-SenderId wwwh|x-authuser|tim@thechases.com
X-MailChannels-Auth-Id wwwh
X-MC-Loop-Signature 1468716312250:853861079
X-MC-Ingress-Time 1468716312249
In-Reply-To <CAPTjJmpQk9SwLRct-WpZMywFFLhX3A459eNzB5eHGVFyhBiDoA@mail.gmail.com>
X-Mailer Claws Mail 3.11.1 (GTK+ 2.24.25; x86_64-pc-linux-gnu)
X-AuthUser tim@thechases.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 <20160716194510.6283c8f4@bigbox.christie.dr>
X-Mailman-Original-References <21fcec53-cf5b-4529-9790-63a1c46f534b@googlegroups.com> <CAPTjJmpQk9SwLRct-WpZMywFFLhX3A459eNzB5eHGVFyhBiDoA@mail.gmail.com>
Xref csiph.com comp.lang.python:111547

Show key headers only | View raw

On 2016-07-17 08:19, Chris Angelico wrote:
> Why do you need a linked list? That's an implementation detail; why
> not simply use a regular list?
> 
> Not trolling, genuinely asking. Is there something that you
> specifically need those exact structures for?

I know there have been times I want known performance
characteristics.

My main reason for wanting linked lists is usually for stacks/queues
with O(1) push/pop, and I understand that a deque handles most of
that fairly efficiently ("approximately the same O(1) performance in
either direction").

The bisect and heapq modules also help with some of my usual
use-cases for BSTs (presuming "BST" unpacks as "binary search tree"),
while nested arrays/dicts usually serve for most of the rest of my
other tree/trie needs.

So usually I'm less concerned with the actual algorithm name than I
am with the "I want to {push,pop,search,insert,delete} in O(f) time"
where O(f) is usually either O(1) or O(N log N), instead of the
alternatives which might use O(N), O(N**k), or worse, O(k**N).

For anything beyond those basic CS data-structures, there's usually
something conveniently in PyPI.

-tkc

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

Thread

PEP Request: Advanced Data Structures shrey.desai@gmail.com - 2016-07-16 15:14 -0700
  Re: PEP Request: Advanced Data Structures Chris Angelico <rosuav@gmail.com> - 2016-07-17 08:19 +1000
    Re: PEP Request: Advanced Data Structures Shrey Desai <shrey.desai@gmail.com> - 2016-07-16 15:33 -0700
      Re: PEP Request: Advanced Data Structures Chris Angelico <rosuav@gmail.com> - 2016-07-17 08:45 +1000
      Re: PEP Request: Advanced Data Structures Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2016-07-16 19:49 -0400
  Re: PEP Request: Advanced Data Structures breamoreboy@gmail.com - 2016-07-16 16:21 -0700
  Re: PEP Request: Advanced Data Structures Paul Rubin <no.email@nospam.invalid> - 2016-07-16 16:36 -0700
  Re: PEP Request: Advanced Data Structures Terry Reedy <tjreedy@udel.edu> - 2016-07-16 20:10 -0400
  Re: PEP Request: Advanced Data Structures MRAB <python@mrabarnett.plus.com> - 2016-07-17 01:38 +0100
    Re: PEP Request: Advanced Data Structures Marko Rauhamaa <marko@pacujo.net> - 2016-07-17 10:26 +0300
  Re: PEP Request: Advanced Data Structures Steven D'Aprano <steve@pearwood.info> - 2016-07-17 14:21 +1000
  Re: PEP Request: Advanced Data Structures Tim Chase <python.list@tim.thechases.com> - 2016-07-16 19:45 -0500
  Re: PEP Request: Advanced Data Structures Rustom Mody <rustompmody@gmail.com> - 2016-07-17 00:33 -0700

csiph-web