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

Groups > comp.lang.python > #111524 > unrolled thread

PEP Request: Advanced Data Structures

Back to article view | Back to comp.lang.python

Contents

  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

#111524 — PEP Request: Advanced Data Structures

I have found it slightly frustrating that Python does not have built-in support for advanced data structures (Linked Lists, Stacks/Queues, BST) in its distribution. Many computer science students, developers, and software engineers rely on these data structures; having the data structures be a part of the distribution and be maintained by the Python community would be immensely useful. 

Currently, we are required to write our own modules that represent these data structures and rigorously test/refactor them before we can actually use them. This gets annoying because instead of spending time USING the "correct" version of the data structure, we have to spend time creating them in the first place.

Programming languages like Java have support for Linked Lists, for example, which makes it easy to just use it instead of trying to create it over again. As a computer science undergraduate student, I don't want to spend time writing the module but instead I want to work with it, play around with it, and do problems with it. 

I know Python currently has a Queue module, but this can definitely be expanded. There are other more advanced data structures out there, like AVL trees, splay trees, and tries, but I think that would be overkilll. Having these data structures above would be immensely useful.

I'm looking to create a PEP for this issue and some people that would be willing to 1) vouch for this idea and 2) co-author the draft. Eventually, we would be co-developers for the project as well.

Who's in? 

[toc] | [next] | [standalone]

#111526

On Sun, Jul 17, 2016 at 8:14 AM,  <shrey.desai@gmail.com> wrote:
> I have found it slightly frustrating that Python does not have built-in support for advanced data structures (Linked Lists, Stacks/Queues, BST) in its distribution. Many computer science students, developers, and software engineers rely on these data structures; having the data structures be a part of the distribution and be maintained by the Python community would be immensely useful.
>

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?

Also: You may find what you want on PyPI. There's no need for them to
be in the core language if they can be published as third-party
modules.

ChrisA

[toc] | [prev] | [next] | [standalone]

#111527

On Saturday, July 16, 2016 at 3:19:56 PM UTC-7, Chris Angelico wrote:
> On Sun, Jul 17, 2016 at 8:14 AM,  <shrey.desai@gmail.com> wrote:
> > I have found it slightly frustrating that Python does not have built-in support for advanced data structures (Linked Lists, Stacks/Queues, BST) in its distribution. Many computer science students, developers, and software engineers rely on these data structures; having the data structures be a part of the distribution and be maintained by the Python community would be immensely useful.
> >
> 
> 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?
> 
> Also: You may find what you want on PyPI. There's no need for them to
> be in the core language if they can be published as third-party
> modules.
> 
> ChrisA

Hi Chris, thanks for the reply. There's a couple of reasons why I would need a Linked List (and other data structures):
- Education: the Linked List is a core data structure that CS undergraduates (among others) use and study, so it is vital that they have hands on access to them. A list is basically a dynamic array; the only property it shares with a Linked List is that it's dynamic.
- Development: the use of correct data structures is important when developing applications, especially for issues like scaling and efficiency. For instance, when working with polynomials, Linked Lists provide a great interface to access and edit them.

Also, I have a couple of issues with them being published as third-party modules:
1. These data structures have to be rock solid. They should be clearly defined, rigorously tested, and they should simply work. Python would put more emphasis on its development rather than some external developer that might quit half way.
2. Some external packages might contain better data structures than others. For instance, there might be some "DataStructures" package that contains everything, but maybe some developer published a "LinkedList" package that has the best Linked List implementation and some other developer published a "BST" package that has the best BST implementation. Why mix and match when everything can be in one place?
3. Python, fundamentally, is an easy to use language and it should stay that way. Beginners shouldn't have to worry about installing external modules when the data structures package is in the distribution and all they need to do to use it is import it.

[toc] | [prev] | [next] | [standalone]

#111528

On Sun, Jul 17, 2016 at 8:33 AM, Shrey Desai <shrey.desai@gmail.com> wrote:
> Hi Chris, thanks for the reply. There's a couple of reasons why I would need a Linked List (and other data structures):
> - Education: the Linked List is a core data structure that CS undergraduates (among others) use and study, so it is vital that they have hands on access to them. A list is basically a dynamic array; the only property it shares with a Linked List is that it's dynamic.
> - Development: the use of correct data structures is important when developing applications, especially for issues like scaling and efficiency. For instance, when working with polynomials, Linked Lists provide a great interface to access and edit them.
>

For education, I wouldn't worry too much about performance or edge
cases, and just use something really simple:

class LinkedList:
    def __init__(self):
        self.head = self.tail = None
    def append(self, item):
        if self.tail: self.tail = self.tail.append(item)
        self.head = self.tail = _listitem(item)

class _listitem:
    def __init__(self, item):
        self.item = item
        self.next = None
    def append(self, item):
        self.next = type(self)(item)
        return self.next

Then add other methods as you teach them (iteration, item removal,
etc). Performance is probably terrible, but who cares? You won't
notice it in sample code.

For development, I'm pretty sure the native CPython list type is going
to out-perform anything you could implement as a linked list. Even
more so if you're using PyPy, where it knows how to optimize the list
(but won't necessarily be able to optimize your type). Instead of
messing around with data types, just implement your code using the
most simple and obvious style, and worry about
performance/scaling/efficiency only if and when you find out that
that's a bottleneck. I very much doubt that it will be.

ChrisA

[toc] | [prev] | [next] | [standalone]

#111532

On Sat, 16 Jul 2016 15:33:12 -0700 (PDT), Shrey Desai
<shrey.desai@gmail.com> declaimed the following:

>
>Hi Chris, thanks for the reply. There's a couple of reasons why I would need a Linked List (and other data structures):
>- Education: the Linked List is a core data structure that CS undergraduates (among others) use and study, so it is vital that they have hands on access to them. A list is basically a dynamic array; the only property it shares with a Linked List is that it's dynamic.

	My CS courses required us to implement our own linked lists (in FORTRAN
IV yet). Providing a built-in linked list just negates the educational
aspect.


>- Development: the use of correct data structures is important when developing applications, especially for issues like scaling and efficiency. For instance, when working with polynomials, Linked Lists provide a great interface to access and edit them.

	What does having links gain you that you don't get from a regular list
with slicing?
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#111530

On Saturday, July 16, 2016 at 11:15:04 PM UTC+1, Shrey Desai wrote:
> I have found it slightly frustrating that Python does not have built-in support for advanced data structures (Linked Lists, Stacks/Queues, BST) in its distribution. Many computer science students, developers, and software engineers rely on these data structures; having the data structures be a part of the distribution and be maintained by the Python community would be immensely useful. 
> 
> Currently, we are required to write our own modules that represent these data structures and rigorously test/refactor them before we can actually use them. This gets annoying because instead of spending time USING the "correct" version of the data structure, we have to spend time creating them in the first place.
> 
> Programming languages like Java have support for Linked Lists, for example, which makes it easy to just use it instead of trying to create it over again. As a computer science undergraduate student, I don't want to spend time writing the module but instead I want to work with it, play around with it, and do problems with it. 
> 
> I know Python currently has a Queue module, but this can definitely be expanded. There are other more advanced data structures out there, like AVL trees, splay trees, and tries, but I think that would be overkilll. Having these data structures above would be immensely useful.
> 
> I'm looking to create a PEP for this issue and some people that would be willing to 1) vouch for this idea and 2) co-author the draft. Eventually, we would be co-developers for the project as well.
> 
> Who's in?

Thanks but no thanks :)  I find the structures listed here http://kmike.ru/python-data-structures and here https://pypi.python.org/pypi/sortedcontainers more than adequate for my needs.

Cheers.

Mark Lawrence.

[toc] | [prev] | [next] | [standalone]

#111531

shrey.desai@gmail.com writes:
> As a computer science undergraduate student, I don't want to spend
> time writing the module but instead I want to work with it, play
> around with it, and do problems with it.

For educational purposes, I think writing the module yourself is part of
the idea.  Also, Python isn't really the right language for that.  Most
things in Python are done with Python lists (elastic vectors),
deques/queues, or dictionaries.  That's almost always sufficient in
practice.  I've occasionally wanted an AVL tree for shared dictionaries
but that's about it.

The C++ standard template library (STL) and Boost have most of what you
want, at a lower level than Python.  Or if you really want to be
hardcore, implement everything yourself in assembler.

[toc] | [prev] | [next] | [standalone]

#111533

On 7/16/2016 6:14 PM, shrey.desai@gmail.com wrote:
> I have found it slightly frustrating that Python does not have
> built-in support for advanced data structures (Linked Lists,

You and I have different ideas of 'advanced data structures' ;-).  To 
me, linked list are limited structures used in functional programming to 
make mutable structure from immutable-except-on-creation cells.  In any 
case, one can easily use tuples to create branching structures.  Tuples 
and lists containing tuples and lists are routine in python programming. 
Wrapping such usage in a LinkedList class is optional -- and unusual.

> Stacks/Queues,

Nearly two decades ago, I promoted the addition of the list.pop method 
as the inverse of list.append, in order to make lists easily usable as 
stacks.  This is routine in python code today.

collections.deque instances are advanced data structures that can be 
used as stacks, queues, or both, at either end.  The class has tests 
that I presume are rigorous.

> BST)

British Summer Time? (Suggestion from Google)

> Currently, we are required to write our own modules that represent
> these data structures and rigorously test/refactor them before we can
> actually use them.

If an instructor makes you wrap the structures that Python provides 
before you can use then, that is between you and the instructor, and not 
our doing.  The instructor could let you use Python as it is or hand you 
the wrapping he likes.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#111534

On 2016-07-17 01:10, Terry Reedy wrote:
> On 7/16/2016 6:14 PM, shrey.desai@gmail.com wrote:
>> I have found it slightly frustrating that Python does not have
>> built-in support for advanced data structures (Linked Lists,
>
> You and I have different ideas of 'advanced data structures' ;-).  To
> me, linked list are limited structures used in functional programming to
> make mutable structure from immutable-except-on-creation cells.  In any
> case, one can easily use tuples to create branching structures.  Tuples
> and lists containing tuples and lists are routine in python programming.
> Wrapping such usage in a LinkedList class is optional -- and unusual.
>
They're the kind of things I'd write when using C, but, then, C is 
missing a lot of stuff! :-)

>> Stacks/Queues,
>
> Nearly two decades ago, I promoted the addition of the list.pop method
> as the inverse of list.append, in order to make lists easily usable as
> stacks.  This is routine in python code today.
>
> collections.deque instances are advanced data structures that can be
> used as stacks, queues, or both, at either end.  The class has tests
> that I presume are rigorous.
>
>> BST)
>
> British Summer Time? (Suggestion from Google)
>
Binary search tree.

Given that Python has dict, there's not much need for a binary search tree.

[snip]

[toc] | [prev] | [next] | [standalone]

#111551

MRAB <python@mrabarnett.plus.com>:
> Given that Python has dict, there's not much need for a binary search tree.

Dicts don't have the concept of key order. I use my own AVL tree to
implement timers. A balanced tree data structure is the only major data
structure I've missed in Python. It is there in Java and C++, for
example. The Linux kernel makes use of it as well.


Marko

[toc] | [prev] | [next] | [standalone]

#111546

On Sun, 17 Jul 2016 08:14 am, shrey.desai@gmail.com wrote:

> I have found it slightly frustrating that Python does not have built-in
> support for advanced data structures (Linked Lists, Stacks/Queues, BST) in
> its distribution.

They are hardly "advanced" data structures. They are trivial data
structures. When I did an undergraduate course in computer science, we were
expected to write them ourselves, from scratch.

Linked lists are primitive data structures used by languages that don't have
Python's advanced list data structure. For nearly everything that you think
you want a linked list, you will be better off to use a built-in list.

For stacks and queues, use collections.deque.

For binary search trees, you will mostly use a dict. If there are
exceptions, they are unusual.


> Many computer science students, developers, and software 
> engineers rely on these data structures; having the data structures be a
> part of the distribution and be maintained by the Python community would
> be immensely useful.

They really wouldn't be. I cannot imagine when anyone would want to use a
linked list when lists are available. That would be a very big step
backwards in both performance and power: harder to use, and slower.


[...]
> I'm looking to create a PEP for this issue and some people that would be
> willing to 1) vouch for this idea and 2) co-author the draft. Eventually,
> we would be co-developers for the project as well.

Perhaps I'm wrong, but it sounds to me that you should spend more time
learning Python and less time trying to mechanically translate C algorithms
into Python code. Python doesn't have a linked list class because it is
unnecessary. Python doesn't need a dedicated stack or single-threaded queue
class, because it has deque. (As a comp sci undergrad, you have probably
heard of double-ended queues.) Python already has a thread-safe queue.
*Maybe* there's a use-case for a self-balancing tree structure in Python,
but which one? How often do you need to use keys that can't be hashed? 




-- 
Steven
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.

[toc] | [prev] | [next] | [standalone]

#111547

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

[toc] | [prev] | [next] | [standalone]

#111553

On Sunday, July 17, 2016 at 3:45:04 AM UTC+5:30, Shrey Desai wrote:
> I have found it slightly frustrating that Python does not have built-in support for advanced data structures (Linked Lists, Stacks/Queues, BST) in its distribution. Many computer science students, developers, and software engineers rely on these data structures; having the data structures be a part of the distribution and be maintained by the Python community would be immensely useful. 
> 
> Currently, we are required to write our own modules that represent these data structures and rigorously test/refactor them before we can actually use them. This gets annoying because instead of spending time USING the "correct" version of the data structure, we have to spend time creating them in the first place.
> 
> Programming languages like Java have support for Linked Lists, for example, which makes it easy to just use it instead of trying to create it over again. As a computer science undergraduate student, I don't want to spend time writing the module but instead I want to work with it, play around with it, and do problems with it. 
> 
> I know Python currently has a Queue module, but this can definitely be expanded. There are other more advanced data structures out there, like AVL trees, splay trees, and tries, but I think that would be overkilll. Having these data structures above would be immensely useful.
> 
> I'm looking to create a PEP for this issue and some people that would be willing to 1) vouch for this idea and 2) co-author the draft. Eventually, we would be co-developers for the project as well.
> 
> Who's in?

Hi Shrey
Your wish and direction is commendable
And looks at an important question
Do consider however that the boot may well be on the other foot: viz.

So
“Python does not have advanced data structures… fir students/edu-purposes”
may suggest that python should change

Or that education should!

Some examples of the nature the the fast-shifting ground under our feet:
It was important for programmers to know and use registers/instruction-formats
etc very effectively at one time.  At some time it stopped being relevant.

Or card-punches, Or large central ACs, Or tape drives, Or interrupts.

Some of these have just died; some remain in specialized places; some are ubiquitous
but with enough strong abstractions that vanilla programmers dont ever think of
these nowadays

The same holds for broad areas
Cryptography is where CS started in WWII; vanished thereafter; reappeared in
specialized quarters of late
Numerical computing was the hi-cathedral for the next few decades
By the time I was a student in the 80s it was there but somehow felt old and past-tense.
I expect recently instituted courses dont have it; or have it specialized.

These shifts are elaborated somewhat more 
https://mail.python.org/pipermail/python-list/2016-June/710678.html
and sequel

Coming to data structures (and algorithms)
yes it (they) are important courses… and widely misunderstood

Here is Bob Harper *quoting a developer*
everyone knows that algorithms as we learned  them  at  school  are  irrelevant  to  practice."
https://www.cs.cmu.edu/~rwh/papers/secp/secp.pdf (pg 2)
[Harper is a senior respected faculty at Carnegie Mellon]

I think the same applies to data structures with redoubled force:
Most of what is called data structures — linked lists etc — should really be 
called *storage structures*

ie How to survive and do useful work when your system/software is highly crippling.

Greenspun's 10th law:
Any sufficiently complicated C program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Lisp.

If you understand that python is in a sense closer to Lisp than to C,
maybe you see that there are broadly two choices

- Traditional CS-edu view... C, C++, Java, OO-gook, data-structures, algorithms
  etc where the basic philosophy is
  Crippling is a way of life; Be Brave! And hobble more vigorously!‘

- The alternative CS view as understood by Harper, MIT and other progressive
  places embracing the ‘functional’ style (stupid word if you ask me)
  The idea being to throw out 70-80 % of traditional CS from the curriculum
  and get students doing good stuff much faster by putting them on a *different*
  learning curve.

That this stuff is a bit bleeding edge can be seen in the fact that ACM curriculum
has started embracing “functional” only in 2013 — ie 50 years after Lisp:
http://blog.languager.org/2015/06/functional-programming-moving-target.html

Sorry for a ramble.
Summary: Yes the languages we use to teach need to be rethought
So does our teaching ;-)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web