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

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

Re: Tuples and immutability

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Tuples and immutability Duncan Booth <duncan.booth@invalid.invalid> - 2014-03-07 09:33 +0000
    Re: Tuples and immutability Ben Finney <ben+python@benfinney.id.au> - 2014-03-07 22:04 +1100
    Re: Tuples and immutability Chris Angelico <rosuav@gmail.com> - 2014-03-07 22:11 +1100
    Re: Tuples and immutability Peter Otten <__peter__@web.de> - 2014-03-07 12:38 +0100
    Re: Tuples and immutability Chris Angelico <rosuav@gmail.com> - 2014-03-07 22:45 +1100
    Re: Tuples and immutability Alister <alister.ware@ntlworld.com> - 2014-03-07 11:51 +0000
      Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-07 11:23 -0700
    Re: Tuples and immutability Roy Smith <roy@panix.com> - 2014-03-07 08:37 -0500
    Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-08 15:17 +1300
      Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-07 21:17 -0700
        Balanced trees (was: Re: Tuples and immutability) Marko Rauhamaa <marko@pacujo.net> - 2014-03-08 10:34 +0200
          Re: Balanced trees (was: Re: Tuples and immutability) Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-08 04:03 -0700
            Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-08 13:26 +0200
          Re: Balanced trees (was: Re: Tuples and immutability) Dan Stromberg <drsalists@gmail.com> - 2014-03-08 11:58 -0800
          Re: Balanced trees Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-03-08 20:37 +0000
            Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-08 23:21 +0200
              Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-08 17:22 -0500
                Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 11:17 +0200
              Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-08 17:31 -0800
                Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 11:27 +0200
                  Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-09 14:20 -0700
                    Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 23:32 +0200
                      Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-09 14:37 -0700
                        Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 23:43 +0200
                          Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-09 15:08 -0700
                            Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 00:24 +0200
                          Re: Balanced trees Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-09 18:04 -0600
                            Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 03:24 +0000
                      Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 03:24 +0000
                        Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 08:16 +0200
                          Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 08:53 +0000
                            Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 11:41 +0200
                              Re: Balanced trees Ned Batchelder <ned@nedbatchelder.com> - 2014-03-10 06:57 -0400
                                Re: Balanced trees Rustom Mody <rustompmody@gmail.com> - 2014-03-10 09:01 -0700
                                  Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-11 02:02 +0000
                                    Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 22:20 -0400
                                      Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 13:29 +1100
                            Re: Balanced trees Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-03-10 09:51 +0000
                          Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 09:59 -0400
                            Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 03:20 +1100
                            Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 03:24 +1100
                              Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 19:08 +0200
                                Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 04:17 +1100
                                  Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 19:34 +0200
                                    Re: Balanced trees Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-13 12:40 -0600
                                    Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-13 23:57 +0000
                                      Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-13 20:12 -0700
                                        Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-14 05:02 +0000
                                Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 19:24 -0400
                                  Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 10:27 +1100
                                  Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-11 01:26 +0000
                                    Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 12:45 +1100
                                    Re: Balanced trees Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-10 21:38 -0600
                                    Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 15:28 +1100
                                      Re: Balanced trees "Rhodri James" <rhodri@wildebst.org.uk> - 2014-03-12 00:57 +0000
                                    Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-11 12:12 +0200
                                      Re: Balanced trees alex23 <wuwei23@gmail.com> - 2014-03-12 10:13 +1000
                                  Re: Balanced trees Alister <alister.ware@ntlworld.com> - 2014-03-11 09:25 +0000
                                  Re: Balanced trees Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2014-03-12 10:08 +0100
                            Re: Balanced trees Tim Chase <python.list@tim.thechases.com> - 2014-03-10 11:33 -0500
                            Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 03:39 +1100
                            Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-10 18:05 -0700
                              Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 22:13 -0400
                        Re: Balanced trees Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2014-03-10 19:57 -0400
          Re: Balanced trees Joshua Landau <joshua@landau.ws> - 2014-03-15 01:13 +0000
            Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-18 00:05 +0200
              Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-18 12:26 -0700
                Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-18 22:55 +0200
                  Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-18 14:45 -0700
                    Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 00:03 +0200
                      Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-18 15:21 -0700
                        Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 01:11 +0200
                          Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-19 01:15 +0000
                            Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 10:49 +0200
                              Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-19 13:42 +0000
                                Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 15:54 +0200
                                Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-19 10:06 -0400
                        Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-19 01:15 +0000
                          Re: Balanced trees Ethan Furman <ethan@stoneleaf.us> - 2014-03-19 08:15 -0700
                    Re: Balanced trees "Rhodri James" <rhodri@wildebst.org.uk> - 2014-03-20 02:16 +0000
                      Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-19 19:34 -0700
                  Re: Balanced trees Chris Kaynor <ckaynor@zindagigames.com> - 2014-03-18 18:02 -0700
              Re: Balanced trees Daniel Stutzbach <stutzbach@google.com> - 2014-03-18 13:18 -0700
          blist in standard library  (was Re: Balanced trees) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-03-15 12:31 +0000
          Re: Balanced trees Daniel Stutzbach <stutzbach@google.com> - 2014-03-17 14:16 -0700
          Re: Balanced trees Joshua Landau <joshua@landau.ws> - 2014-03-18 00:08 +0000
          Re: Balanced trees Daniel Stutzbach <stutzbach@google.com> - 2014-03-17 18:01 -0700
          Re: Balanced trees Joshua Landau <joshua@landau.ws> - 2014-03-18 07:46 +0000
        Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-09 13:40 +1300
          Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-08 19:39 -0700
            Re: Tuples and immutability Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 11:35 +0200
            Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-10 11:03 +1300
              Re: Tuples and immutability Terry Reedy <tjreedy@udel.edu> - 2014-03-09 19:00 -0400
              Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-09 17:42 -0600
                Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 02:37 +0000
                  Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-10 02:35 -0600
                    Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 09:13 +0000
                    Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-11 18:15 +1300
                Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-11 18:03 +1300
                  Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-11 04:39 -0600
                    Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-11 16:46 +0000
                      Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-12 10:23 +1300
                      Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-11 17:06 -0600
                        Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-12 23:20 +0000
                          Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-12 19:35 -0600
                          Re: Tuples and immutability Terry Reedy <tjreedy@udel.edu> - 2014-03-12 22:09 -0400
        Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-09 13:45 +1300
          Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-08 19:55 -0700

Page 1 of 6  [1] 2 3 4 5 6  Next page →

#67985 — Re: Tuples and immutability

Chris Angelico <rosuav@gmail.com> wrote:

> On Sat, Mar 1, 2014 at 1:41 AM, Joshua Landau <joshua@landau.ws>
> wrote: 
>> Would it be better to add a check here, such that if this gets raised
>> to the top-level it includes a warning ("Addition was inplace;
>> variable probably mutated despite assignment failure")?
> 
> That'd require figuring out whether or not the variable was actually
> mutated, and that's pretty hard to work out. So there's a FAQ entry,
> which Zachary already posted:
> 
> http://docs.python.org/3/faq/programming.html#why-does-a-tuple-i-item-r
> aise-an-exception-when-the-addition-works 
> 
> Also, we just answer this question every now and then :) Presumably
> more often on -tutor than here.
> 
> ChrisA
Another take on this that I haven't seen discussed in this thread:

Is there any reason why tuples need to throw an exception on assigning to 
the element if the old value and new value are the same object?

If I say:

    a = ("spam", [10, 30], "eggs")

then

    a[0] = a[0]

won't actually mutate the object. So tuples could let that silently pass. 
Then you would be able to safely do:

    a[1] += [50]

but this would still throw an exception:

    a[0] += "x"

    

-- 
Duncan Booth http://kupuguy.blogspot.com

[toc] | [next] | [standalone]

#67988

Duncan Booth <duncan.booth@invalid.invalid> writes:

> Is there any reason why tuples need to throw an exception on assigning
> to the element if the old value and new value are the same object?

Special cases aren't special enough to break the rules.

-- 
 \           “I do not believe in forgiveness as it is preached by the |
  `\        church. We do not need the forgiveness of God, but of each |
_o__)                    other and of ourselves.” —Robert G. Ingersoll |
Ben Finney

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

#67989

On Fri, Mar 7, 2014 at 8:33 PM, Duncan Booth
<duncan.booth@invalid.invalid> wrote:
> Is there any reason why tuples need to throw an exception on assigning to
> the element if the old value and new value are the same object?

It'd be easy enough to implement your own tuple subclass that behaves
that way. Try it! See how many situations it actually helps.

ChrisA

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

#67992

Chris Angelico wrote:

> On Fri, Mar 7, 2014 at 8:33 PM, Duncan Booth
> <duncan.booth@invalid.invalid> wrote:
>> Is there any reason why tuples need to throw an exception on assigning to
>> the element if the old value and new value are the same object?
> 
> It'd be easy enough to implement your own tuple subclass that behaves
> that way. Try it! See how many situations it actually helps.

>>> class T(tuple):
...     def __setitem__(self, index, value):
...             if value is not self[index]:
...                     raise TypeError("{} is not {}".format(value, 
self[index]))
... 
>>> for i, k in zip(range(250, 260), range(250, 260)):
...     T([i])[0] = k
... 
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "<stdin>", line 4, in __setitem__
TypeError: 257 is not 257

I'm not sure "help" is the right word here ;)

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

#67993

On Fri, Mar 7, 2014 at 10:38 PM, Peter Otten <__peter__@web.de> wrote:
> TypeError: 257 is not 257
>
> I'm not sure "help" is the right word here ;)

It doesn't help with non-small integers, yes, but the original case
was a list. Personally, I don't think there are many situations that
would benefit from it, plus it'd be confusing ("I can use += with a
list but not a number, why not?!").

ChrisA

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

#67994

On Fri, 07 Mar 2014 09:33:49 +0000, Duncan Booth wrote:

> Chris Angelico <rosuav@gmail.com> wrote:
> 
>> On Sat, Mar 1, 2014 at 1:41 AM, Joshua Landau <joshua@landau.ws> wrote:
>>> Would it be better to add a check here, such that if this gets raised
>>> to the top-level it includes a warning ("Addition was inplace;
>>> variable probably mutated despite assignment failure")?
>> 
>> That'd require figuring out whether or not the variable was actually
>> mutated, and that's pretty hard to work out. So there's a FAQ entry,
>> which Zachary already posted:
>> 
>> http://docs.python.org/3/faq/programming.html#why-does-a-tuple-i-item-r
>> aise-an-exception-when-the-addition-works
>> 
>> Also, we just answer this question every now and then :) Presumably
>> more often on -tutor than here.
>> 
>> ChrisA
> Another take on this that I haven't seen discussed in this thread:
> 
> Is there any reason why tuples need to throw an exception on assigning
> to the element if the old value and new value are the same object?
> 
> If I say:
> 
>     a = ("spam", [10, 30], "eggs")
> 
> then
> 
>     a[0] = a[0]
> 
> won't actually mutate the object. So tuples could let that silently
> pass.
> Then you would be able to safely do:
> 
>     a[1] += [50]
> 
> but this would still throw an exception:
> 
>     a[0] += "x"

I would think it would be better if the exception was thrown before the 
assignment to the list took place
simply seeing that a modification action was being applied to a tupple 
should be enough.
this would alert the programmer to the fact that he was trying something 
that may have undesired consequences
 



-- 
Old age is the harbor of all ills.
		-- Bion

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

#68003

On Fri, Mar 7, 2014 at 4:51 AM, Alister <alister.ware@ntlworld.com> wrote:
> I would think it would be better if the exception was thrown before the
> assignment to the list took place
> simply seeing that a modification action was being applied to a tupple
> should be enough.
> this would alert the programmer to the fact that he was trying something
> that may have undesired consequences

Then the behavior of tuples would be inconsistent with other immutable
types.  This can't be applied generally, because the Python
interpreter doesn't generally know whether a given type is supposed to
be immutable or not.

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

#67998

In article <XnsA2E95FA1E1EB6duncanbooth@127.0.0.1>,
 Duncan Booth <duncan.booth@invalid.invalid> wrote:

> Is there any reason why tuples need to throw an exception on assigning to 
> the element if the old value and new value are the same object?
> 
> If I say:
> 
>     a = ("spam", [10, 30], "eggs")
> 
> then
> 
>     a[0] = a[0]
> 
> won't actually mutate the object. So tuples could let that silently pass. 

But, why would you want them to?  What a way to introduce bugs which are 
difficult to test for.

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

#68017

Duncan Booth wrote:
> Is there any reason why tuples need to throw an exception on assigning to 
> the element if the old value and new value are the same object?

It would make introspection misleading, because tuples
would have a __setitem__ method event though they don't
actually support item assignment.

Also, it would solve the problem for tuples in particular,
but not for any other immutable type -- they would all
have to implement the same behaviour independently to
enjoy the benefit.

Here's another idea: If the __iadd__ method returns the
same object, *and* the LHS doesn't have a __setitem__
method, then do nothing instead of raising an exception.

Peter Otten wrote:

 > Traceback (most recent call last):
 >   File "<stdin>", line 2, in <module>
 >   File "<stdin>", line 4, in __setitem__
 > TypeError: 257 is not 257
 >
 > I'm not sure "help" is the right word here ;)

I don't think that's a problem, because the use case
being addressed is where the object performs in-place
modification and always returns itself. Any object that
doesn't return itself is not modifying in-place, even
if the returned object happens to be equal to the
original one.

-- 
Greg

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

#68023

On Fri, Mar 7, 2014 at 7:17 PM, Gregory Ewing
<greg.ewing@canterbury.ac.nz> wrote:
> Here's another idea: If the __iadd__ method returns the
> same object, *and* the LHS doesn't have a __setitem__
> method, then do nothing instead of raising an exception.

Maybe it doesn't have a __setitem__ because the object that was
retrieved is computed rather than stored, and the result of the
__iadd__ will simply be discarded.  Somewhat contrived example:

class LessThanFilter:

    def __init__(self, the_list):
        self._the_list = the_list

    def __getitem__(self, bound):
        return [x for x in self._the_list if x < bound]


filter = LessThanFilter([10, 20, 30, 40, 50])
filter[25] += [15, 17, 23]

Should that last line not raise an exception?  The __iadd__ call will
return the same object, and the LHS doesn't have a __setitem__ method.

> I don't think that's a problem, because the use case
> being addressed is where the object performs in-place
> modification and always returns itself. Any object that
> doesn't return itself is not modifying in-place, even
> if the returned object happens to be equal to the
> original one.

I already mentioned this earlier in the thread, but a balanced binary
tree might implement += as node insertion and then return a different
object if the balancing causes the root node to change.

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

#68026 — Balanced trees (was: Re: Tuples and immutability)

Ian Kelly <ian.g.kelly@gmail.com>:

> I already mentioned this earlier in the thread, but a balanced binary
> tree might implement += as node insertion and then return a different
> object if the balancing causes the root node to change.

True.

Speaking of which, are there plans to add a balanced tree to the
"batteries" of Python? Timers, cache aging and the like need it. I'm
using my own AVL tree implementation, but I'm wondering why Python
still doesn't have one.

In fact, since asyncio has timers but Python doesn't have balanced
trees, I'm led to wonder how good the asyncio implementation can be.

Note that Java "batteries" include TreeMap.


Marko

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

#68027 — Re: Balanced trees (was: Re: Tuples and immutability)

On Sat, Mar 8, 2014 at 1:34 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Speaking of which, are there plans to add a balanced tree to the
> "batteries" of Python? Timers, cache aging and the like need it. I'm
> using my own AVL tree implementation, but I'm wondering why Python
> still doesn't have one.

None currently that I'm aware of.  If you want to propose adding one,
I suggest reading:

http://docs.python.org/devguide/stdlibchanges.html

> In fact, since asyncio has timers but Python doesn't have balanced
> trees, I'm led to wonder how good the asyncio implementation can be.

Peeking at the code, it appears to use a heapq-based priority queue.
Why would a balanced binary tree be better?

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

#68028 — Re: Balanced trees

Ian Kelly <ian.g.kelly@gmail.com>:

> Peeking at the code, it appears to use a heapq-based priority queue.
> Why would a balanced binary tree be better?

AFAIK, a heap queue doesn't allow for the deletion of a random element
forcing you to leave the canceled timers in the queue to be deleted
later.

In a very typical scenario, networking entities start timers very
frequently (depending on the load, maybe at 100..1000 Hz) but cancel
virtually every one of them, leading to some wakeup churn and extra
memory load. I don't know if the churn is better or worse than the tree
balancing overhead.

Imagine a web server that received HTTP connections. You might want to
specify a 10-minute idle timeout for the connections. In the heapq timer
implementation, your connection objects are kept in memory for 10
minutes even if they are closed gracefully because the canceled timer
maintains a reference to the object.

Of course, it may be that the heapq implementation sets the callback to
None leaving only the minimal timer object lingering and waiting to come
out of the digestive tract.


Marko

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

#68050 — Re: Balanced trees (was: Re: Tuples and immutability)

On Sat, Mar 8, 2014 at 12:34 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@gmail.com>:
>
>> I already mentioned this earlier in the thread, but a balanced binary
>> tree might implement += as node insertion and then return a different
>> object if the balancing causes the root node to change.
>
> True.
>
> Speaking of which, are there plans to add a balanced tree to the
> "batteries" of Python? Timers, cache aging and the like need it. I'm
> using my own AVL tree implementation, but I'm wondering why Python
> still doesn't have one.

I think it'd probably be a good idea to add one or more balanced
binary trees to the standard library.  But I suspect it's been tried
before, and didn't happen.  It might be good to add an _un_balanced
tree too, since they do quite well with random keys.

Here's a performance comparison I did of a bunch of tree types in Python:
http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014-01/

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

#68051 — Re: Balanced trees

On 08/03/2014 19:58, Dan Stromberg wrote:
> On Sat, Mar 8, 2014 at 12:34 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Ian Kelly <ian.g.kelly@gmail.com>:
>>
>>> I already mentioned this earlier in the thread, but a balanced binary
>>> tree might implement += as node insertion and then return a different
>>> object if the balancing causes the root node to change.
>>
>> True.
>>
>> Speaking of which, are there plans to add a balanced tree to the
>> "batteries" of Python? Timers, cache aging and the like need it. I'm
>> using my own AVL tree implementation, but I'm wondering why Python
>> still doesn't have one.
>
> I think it'd probably be a good idea to add one or more balanced
> binary trees to the standard library.  But I suspect it's been tried
> before, and didn't happen.  It might be good to add an _un_balanced
> tree too, since they do quite well with random keys.
>
> Here's a performance comparison I did of a bunch of tree types in Python:
> http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014-01/
>

I've found this link useful http://kmike.ru/python-data-structures/

I also don't want all sorts of data structures added to the Python 
library.  I believe that there are advantages to leaving specialist data 
structures on pypi or other sites, plus it means Python in a Nutshell 
can still fit in your pocket and not a 40 ton articulated lorry, unlike 
the Java equivalent.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask 
what you can do for our language.

Mark Lawrence

---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com

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

#68052 — Re: Balanced trees

Mark Lawrence <breamoreboy@yahoo.co.uk>:

> I believe that there are advantages to leaving specialist data
> structures on pypi or other sites, plus it means Python in a Nutshell
> can still fit in your pocket and not a 40 ton articulated lorry,
> unlike the Java equivalent.

An ordered map is a foundational data structure as opposed to, say, a
priority queue, let alone something like urllib2.

If I had to choose between a hash table and AVL (or RB) tree in the
standard library, it would definitely have to be the latter. It is more
generally usable, has fewer corner cases and probably has an equal
performance even in hash tables' sweet spot.


Marko

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

#68054 — Re: Balanced trees

In article <87eh2ctmht.fsf@elektro.pacujo.net>,
 Marko Rauhamaa <marko@pacujo.net> wrote:

> If I had to choose between a hash table and AVL (or RB) tree in the
> standard library, it would definitely have to be the latter. It is more
> generally usable, has fewer corner cases and probably has an equal
> performance even in hash tables' sweet spot.

The C++ folks made that decision, and people spent the next 10 years 
complaining, "Why is there no hash table in STL?"

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

#68075 — Re: Balanced trees

Roy Smith <roy@panix.com>:

>  Marko Rauhamaa <marko@pacujo.net> wrote:
>
>> If I had to choose between a hash table and AVL (or RB) tree in the
>> standard library, it would definitely have to be the latter. It is more
>> generally usable, has fewer corner cases and probably has an equal
>> performance even in hash tables' sweet spot.
>
> The C++ folks made that decision, and people spent the next 10 years
> complaining, "Why is there no hash table in STL?"

Well, luckily, nobody should need to choose. Even STL has an
unordered_map now.


Marko

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

#68057 — Re: Balanced trees

On Sat, Mar 8, 2014 at 1:21 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> If I had to choose between a hash table and AVL (or RB) tree in the
> standard library, it would definitely have to be the latter. It is more
> generally usable, has fewer corner cases and probably has an equal
> performance even in hash tables' sweet spot.

Actually, in the performance comparison I mentioned previously, I
compared Python dict's to a bunch of different balanced trees and one
unbalanced tree. The dictionary was much faster, though granted, it
was the only one in C.

That URL again:
http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014-01/

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

#68076 — Re: Balanced trees

Dan Stromberg <drsalists@gmail.com>:

> On Sat, Mar 8, 2014 at 1:21 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> If I had to choose between a hash table and AVL (or RB) tree in the
>> standard library, it would definitely have to be the latter. It is more
>> generally usable, has fewer corner cases and probably has an equal
>> performance even in hash tables' sweet spot.
>
> Actually, in the performance comparison I mentioned previously, I
> compared Python dict's to a bunch of different balanced trees and one
> unbalanced tree. The dictionary was much faster, though granted, it
> was the only one in C.

Yes, that is one major detail. There must be many more.


Marko

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

Page 1 of 6  [1] 2 3 4 5 6  Next page →

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

csiph-web