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

Groups > comp.lang.python > #111547

Re: PEP Request: Advanced Data Structures

Show all headers | 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