In message mailman.2446.1246491262.8015.python-l...@python.org, João
Valverde wrote:
Lawrence D'Oliveiro wrote:
In message mailman.2140.1245996088.8015.python-l...@python.org, João
Valverde wrote:
Simple example usage case: Insert string into data structure in sorted
order if it
Lawrence D'Oliveiro l...@geek-central.gen.new_zealand writes:
Want sorted order?
sorted(tuple(the_set))
What could be simpler?
Try putting that inside a loop with thousands of iterations and you'll
see what the problem is.
You could apply the same argument to anything. E.g. why
On Fri, 03 Jul 2009 20:08:20 +1200, Lawrence D'Oliveiro wrote:
In message mailman.2446.1246491262.8015.python-l...@python.org, João
Valverde wrote:
Lawrence D'Oliveiro wrote:
[...]
Want sorted order?
sorted(tuple(the_set))
What could be simpler?
Try putting that inside a loop
Try PyJudy:
http://www.dalkescientific.com/Python/PyJudy.html
--
http://mail.python.org/mailman/listinfo/python-list
In message mailman.2140.1245996088.8015.python-l...@python.org, João
Valverde wrote:
Simple example usage case: Insert string into data structure in sorted
order if it doesn't exist, else retrieve it.
the_set = set( ... )
if str in the_set :
... retrieval case ...
else :
In message mailman.2144.1245999295.8015.python-l...@python.org, Miles
Kaufmann wrote:
On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:
That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.
With O(n) insertions and removals, though. A
In message mailman.2146.1246002542.8015.python-l...@python.org, João Valverde
wrote:
But a dict can't be used to implement a (sorted) table ADT.
for key in sorted(the_dict.keys(), cmp = ... whatever ordering criteria you
like ...) :
... do something with the_dict[key] ...
#end for
--
Lawrence D'Oliveiro l...@geek-central.gen.new_zealand writes:
With O(n) insertions and removals, though. A decent self-balancing
binary tree will generally do those in O(log n).
For values of n below, say, a million, would you even notice the difference
on modern hardware?
Huh? Yes, of
On Wed, 01 Jul 2009 20:39:06 +1200, Lawrence D'Oliveiro wrote:
In message mailman.2140.1245996088.8015.python-l...@python.org, João
Valverde wrote:
Simple example usage case: Insert string into data structure in sorted
order if it doesn't exist, else retrieve it.
the_set = set( ... )
Lawrence D'Oliveiro wrote:
Want sorted order?
sorted(tuple(the_set))
Not sure why you want the tuple () there, but
you probably knew that...
TJG
--
http://mail.python.org/mailman/listinfo/python-list
Lawrence D'Oliveiro wrote:
In message mailman.2140.1245996088.8015.python-l...@python.org, João
Valverde wrote:
Simple example usage case: Insert string into data structure in sorted
order if it doesn't exist, else retrieve it.
the_set = set( ... )
if str in the_set :
...
Lawrence D'Oliveiro wrote:
In message mailman.2140.1245996088.8015.python-l...@python.org, João
Valverde wrote:
Simple example usage case: Insert string into data structure in sorted
order if it doesn't exist, else retrieve it.
the_set = set( ... )
if str in the_set :
On Sun, 28 Jun 2009 20:54:11 -0700, Paul Rubin wrote:
João Valverde backu...@netcabo.pt writes:
Could you clarify what you mean by immutable? As in... not mutable? As
in without supporting insertions and deletions?
Correct.
That's has the same performance as using binary search on a
On Sat, 2009-06-27 at 06:03 +0100, João Valverde wrote:
To answer the question of what I need the BSTs for, without getting
into too many boring details it is to merge and sort IP blocklists,
that is, large datasets of ranges in the form of (IP address, IP
address, string).
snip
As an
Paul Rubin wrote:
The idea is you can accomplish the equivalent of insertion or deletion
by allocating a new root, along with the path down to the place you
want to insert, i.e. O(log n) operations. So instead of mutating an
existing tree, you create a new tree that shares most of its
João Valverde wrote:
Paul Rubin wrote:
João Valverde backu...@netcabo.pt writes:
Interesting, thanks. The concept is not difficult to understand but
I'm not sure it would be preferable. A copy operation should have the
same cost as a snapshot,
You mean a deep-copy? That is
alex23 wrote:
João Valverde backu...@netcabo.pt wrote:
Currently I don't have a strong need for this.
And clearly neither has anyone else, hence the absence from the
stdlib. As others have pointed out, there are alternative approaches,
and plenty of recipes on ActiveState, which seem
João Valverde backu...@netcabo.pt writes:
Rereading this I got what you meant by wrapper with mutating slot.
But that is (like I think you implied) functionally equivalent to a
mutating data structure, with worse performance because of additional
memory allocation and such. Is it faster to
João Valverde wrote:
alex23 wrote:
João Valverde backu...@netcabo.pt wrote:
Currently I don't have a strong need for this.
And clearly neither has anyone else, hence the absence from the
stdlib. As others have pointed out, there are alternative approaches,
and plenty of recipes on
Paul Rubin wrote:
a...@pythoncraft.com (Aahz) writes:
(In particular, WRT the bisect module, although insertion and deletion
are O(N), the constant factor for doing a simple memory move at C speed
swamps bytecode until N gets very large -- and we already have
collections.deque() for some
João Valverde backu...@netcabo.pt writes:
Could you clarify what you mean by immutable? As in... not mutable? As
in without supporting insertions and deletions?
Correct.
That's has the same performance as using binary search on a sorted
list. What's the point of using a tree for that?
Paul Rubin wrote:
João Valverde backu...@netcabo.pt writes:
Could you clarify what you mean by immutable? As in... not mutable? As
in without supporting insertions and deletions?
Correct.
That's has the same performance as using binary search on a sorted
list. What's the
João Valverde wrote:
Paul Rubin wrote:
João Valverde backu...@netcabo.pt writes:
Could you clarify what you mean by immutable? As in... not mutable? As
in without supporting insertions and deletions?
Correct.
That's has the same performance as using binary search on a sorted
João Valverde backu...@netcabo.pt writes:
Interesting, thanks. The concept is not difficult to understand but
I'm not sure it would be preferable. A copy operation should have the
same cost as a snapshot,
You mean a deep-copy? That is unnecessarily expensive; with a
functional structure you
João Valverde backu...@netcabo.pt writes:
bst[key] = object
is even dicier for immutable structures no?
bst = bst.insert(key, object)
--
http://mail.python.org/mailman/listinfo/python-list
João Valverde wrote:
I wouldn't consider anything other than C for such a module on
efficiency alone, unless it was a prototype of course. But I have little
knowledge about the Python C API.
Cython is your true friend, if only for rapid prototyping.
http://cython.org/
Stefan
--
João Valverde wrote:
Aahz wrote:
In article mailman.2170.1246042676.8015.python-l...@python.org,
=?ISO-8859-1?Q?Jo=E3o_Valverde?= backu...@netcabo.pt wrote:
Anyway, I'm *not* trying to discourage you, just explain some of the
roadblocks to acceptance that likely are why it hasn't already
João Valverde wrote:
To answer the question of what I need the BSTs for, without getting
into too many boring details it is to merge and sort IP blocklists,
that is, large datasets of ranges in the form of (IP address, IP
address, string). Originally I was also serializing them in a binary
Miles Kaufmann wrote:
João Valverde wrote:
To answer the question of what I need the BSTs for, without getting
into too many boring details it is to merge and sort IP blocklists,
that is, large datasets of ranges in the form of (IP address, IP
address, string). Originally I was also
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a relevant discussion. Seems like a
glaring omission considering the
João Valverde wrote:
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I
searched the archive but couldn't find a relevant discussion. Seems
like a glaring omission
João Valverde wrote:
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I
searched the archive but couldn't find a relevant discussion. Seems
like a glaring omission
On Thu, Jun 25, 2009 at 10:55 PM, João Valverdebacku...@netcabo.pt wrote:
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a
João Valverde wrote:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return value.
Although practicality
On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:
On Thu, Jun 25, 2009 at 10:55 PM, João Valverdebacku...@netcabo.pt
wrote:
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a
João Valverde wrote:
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I
searched the archive but couldn't find a relevant discussion. Seems
like a glaring omission
On Jun 25, 10:32 pm, a...@pythoncraft.com (Aahz) wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a relevant discussion. Seems like
Jason Scheirer wrote:
On Jun 25, 10:32 pm, a...@pythoncraft.com (Aahz) wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a
Stefan Behnel wrote:
João Valverde wrote:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return
João Valverde wrote:
Stefan Behnel wrote:
João Valverde wrote:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object
are
not (side-effect free) functions, so it's just purity if they
On Fri, Jun 26, 2009 at 12:09 AM, João Valverdebacku...@netcabo.pt wrote:
João Valverde wrote:
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I searched
the
João Valverde wrote:
João Valverde wrote:
Aahz wrote:
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I
searched the archive but couldn't find a relevant discussion. Seems
like
On Fri, 26 Jun 2009 00:09:06 -0700, Jason Scheirer wrote:
I once wrote a binary sorted tree data structure for Python in C. It
performed anywhere from 15-40% worse than dicts. I think with
optimization it will only perform 10% worse than dicts at best.
Oh hey maybe that is why trees aren't
Stefan Behnel stefan...@behnel.de writes:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return
Chris Rebert c...@rebertia.com writes:
Simple example usage case: Insert string into data structure in
sorted order if it doesn't exist, else retrieve it.
That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.
That lets you find an existing
Paul Rubin wrote:
Stefan Behnel writes:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return value.
Stefan Behnel writes:
João Valverde wrote:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return value.
Hallvard B Furuseth wrote:
Stefan Behnel writes:
João Valverde wrote:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they
Stefan Behnel stefan...@behnel.de writes:
But deletes in an AVL tree should not cause mutation. They should
just allocate a new root and path up to where the deleted node was.
I doubt that there are many AVL implementations that do that. Plus, if
deletion doesn't delete, I'd happily
In article 006078f0$0$9721$c3e8...@news.astraweb.com,
Steven D'Aprano st...@remove-this-cybersource.com.au wrote:
Hash tables (dicts) are useful for many of the same things that trees are
useful for, but they are different data structures with different
strengths and weaknesses, and different
a...@pythoncraft.com (Aahz) writes:
(In particular, WRT the bisect module, although insertion and deletion
are O(N), the constant factor for doing a simple memory move at C speed
swamps bytecode until N gets very large -- and we already have
collections.deque() for some other common use
On Fri, Jun 26, 2009 at 1:54 AM, Miles Kaufmann mile...@umich.edu wrote:
On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:
That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.
With O(n) insertions and removals, though. A decent
Aahz wrote:
In article 006078f0$0$9721$c3e8...@news.astraweb.com,
Steven D'Aprano st...@remove-this-cybersource.com.au wrote:
Hash tables (dicts) are useful for many of the same things that trees are
useful for, but they are different data structures with different
strengths and
João Valverde wrote:
What's lacking is an associative array that preserves ordering, doesn't
require a hash function and has fast insertions and deletions in
O(log(n)).
[...]
I'm genuinely surprised to know
there are no data structures that efficiently support such a common need
in Python.
In article mailman.2170.1246042676.8015.python-l...@python.org,
=?ISO-8859-1?Q?Jo=E3o_Valverde?= backu...@netcabo.pt wrote:
What's lacking is an associative array that preserves ordering, doesn't
require a hash function and has fast insertions and deletions in
O(log(n)). The particular
On Jun 26, 7:35 am, Hallvard B Furuseth h.b.furus...@usit.uio.no
wrote:
Stefan Behnel writes:
João Valverde wrote:
Besides some interface glitches, like returning None
on delete if I recall correctly.
That's actually not /that/ uncommon. Operations that change an object are
not
[Tom Reed]
Why no trees in the standard library, if not as a built in?
The sqlite3 module is built on a binary-tree structure.
It can be used with persistent data or kept in-memory.
The gdbm module has similar flexibility (see the F mode).
FWIW, there are some ASPN implementing various types of
[João Valverde]
What's lacking is an associative array that preserves ordering, doesn't
require a hash function and has fast insertions and deletions in
O(log(n)).
FWIW, Py3.1 has an OrderedDict() that preserves insertion order.
It has O(1) lookup, deletion, insertion, and popping; and O(n)
João Valverde wrote:
What's lacking is an associative array that preserves ordering, doesn't
require a hash function and has fast insertions and deletions in
O(log(n)).
Careful here -- you can't get away from the need for
hashability just by using a tree. Even if you don't
need to actually
greg wrote:
João Valverde wrote:
What's lacking is an associative array that preserves ordering,
doesn't require a hash function and has fast insertions and deletions
in O(log(n)).
Careful here -- you can't get away from the need for
hashability just by using a tree. Even if you don't
need
João Valverde wrote:
greg wrote:
João Valverde wrote:
What's lacking is an associative array that preserves ordering,
doesn't require a hash function and has fast insertions and
deletions in O(log(n)).
Careful here -- you can't get away from the need for
hashability just by using a tree.
On Jun 26, 1:29 am, Tom Reed tomree...@gmail.com wrote:
Whynotrees in the standard library, if not as a built in? I searched
the archive but couldn't find a relevant discussion. Seems like a
glaring omission considering the batteries included philosophy,
particularly balanced binary search
Aahz wrote:
In article mailman.2170.1246042676.8015.python-l...@python.org,
=?ISO-8859-1?Q?Jo=E3o_Valverde?= backu...@netcabo.pt wrote:
What's lacking is an associative array that preserves ordering, doesn't
require a hash function and has fast insertions and deletions in
O(log(n)). The
Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a relevant discussion. Seems like a
glaring omission considering the batteries included philosophy,
particularly balanced binary search trees. No interest, no good
implementations, something
In article mailman.2139.1245994218.8015.python-l...@python.org,
Tom Reed tomree...@gmail.com wrote:
Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a relevant discussion. Seems like a
glaring omission considering the batteries included
65 matches
Mail list logo
