data structures module

[MetalOne]

I am fairly new to Python.
Today, I wanted a priority queue.
I notice that Python does not have any sorted lists.
I know that I can call list.sort(), but that seems rather inefficient
to call every time an element is added.
I am wondering why there is not a module or modules containing many
common data structures. Has such a thing been decided against? Is it
that just nobody has done it? Has nobody else suggested the need for
it? Maybe I should search, but I am too tired now, I need sleep.

 

[Albert Hofkamp]

I am fairly new to Python.
Today, I wanted a priority queue.
I notice that Python does not have any sorted lists.
I know that I can call list.sort(), but that seems rather inefficient
to call every time an element is added.

It is (probably).

Instead, sort the list once, then for each element you insert, find the
place using binary search, then insert the element with insert().

I am wondering why there is not a module or modules containing many
common data structures.

Probably because the native data structures of Python are rich enough to
solve most problems in an adhoc way.

Has such a thing been decided against? Is it

No, but what do you want added that isn't there, and is not easily
constructed by a few lines of Python?


Albert

 

[Christopher Koppler]

I am fairly new to Python.
Today, I wanted a priority queue.
I notice that Python does not have any sorted lists.

The standard library has modules Queue and bisect - go look them up in
the docs (online:
http://www.python.org/doc/current/lib/module-Queue.html and
http://www.python.org/doc/current/lib/module-bisect.html ). These
should be what you're looking for.

 

[Aahz]

Today, I wanted a priority queue.
I notice that Python does not have any sorted lists.
I know that I can call list.sort(), but that seems rather inefficient
to call every time an element is added.
I am wondering why there is not a module or modules containing many
common data structures. Has such a thing been decided against? Is it
that just nobody has done it? Has nobody else suggested the need for
it? Maybe I should search, but I am too tired now, I need sleep.

There's a current discussion on python-dev about a "collections" module
or package, and that's one of the structures under discussion.

 

[James Henderson]

Today, I wanted a priority queue.
I notice that Python does not have any sorted lists.
I know that I can call list.sort(), but that seems rather inefficient
to call every time an element is added.

You've already had several good suggestions. I'll just add:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/87369

In the paper version of the Python Cookbook Tim says he has a special fondness
for it, so it must be good!

I am wondering why there is not a module or modules containing many
common data structures. Has such a thing been decided against? Is it
that just nobody has done it? Has nobody else suggested the need for
it?

The python-dev list has been discussing the introduction of a data structures
package. Looking at the thread called "collections module" might give you an
insight to the thought processes involved.

James

 

[Oren Tirosh]

There's a current discussion on python-dev about a "collections" module
or package, and that's one of the structures under discussion.

The major thread of the discussion there is about enhancing the built in
list type to handle popping the first item more efficiently behavior) so
the append/pop() idiom of implementing a queue will work in amortized O(1)
time.

I like the general direction this is going - no new basic data types.
Lists and dicts are sufficient for 98% of all will we ever need. The
remaining 2% can mostly be implemented in Python because it's rarely
performance-critical. The remaining cases are probably better handled by
specialized extension modules anyway (e.g. jkbuckets)

Oren