question of style

[Simon Forman]

On Jul 2, 9:30 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Simon Forman <sajmik... at gmail.com> writes:
> > This code is part of a delete() method for a binary tree
> > implementation. "None" is used to simulate a NULL pointer. In the case
> > where both children are non-None the code goes on to handle that.
>
> > None is a "unitary" or "singleton" value, so "is" is the right
> > comparison operator to use with it, at least in this "imitation
> > pointer" usage.
>
> Yes, but the concept of null pointers is considered kludgy these days.

Seriously? "kludgy"?  (I really AM getting old.)

Well I wouldn't know, I've been fortunate enough to program mostly in
python for over half a decade now and None and 0 are as close as I've
gotten to NULL in a long time.

> One alternative is to represent an empty node as an empty list [], and
> a node with value x as the 1-element list [x].  That incurs some
> storage overhead, but all the case by case checking in your comparison
> function goes away:
>
>    return (self.higher + self.lower)[:1]

Heh, program LISP much? :]

That sounds very interesting, but I'm only writing a BTree to then use
it to play with "persistent data structures" and the models I'm using
are based on pointer code.  I wouldn't want to try to re-implement
them on top of a different "architecture", at least not at first.

> > I've never used dis.dis() to check the bytecodes, but I wouldn't be
> > surprised to find that the compiler generated the same bytecode
> > whether you explicitly state the return or comment it out.)
>
> I really wouldn't worry about this.  Python is so slow no matter what
> you do, that 1 more no-op bytecode won't matter.

I'm not worried about it at all. In fact, I'm pretty sure the compiler
handles it for me as well as I could want or expect it to.

"A Computer's Perspective on Moore's Law: Humans are getting more
expensive at an exponential rate." - Mark Miller
http://www.caplet.com/adages.html

Python may be slow to execute but it's fast to write. (And write
well.)  ;]

> > Last but not least, the logic may seem backwards but it's actually
> > correct. If you check for non-None (NULL) -ness and return the thing
> > you checked, rather than checking for None-ness and returning the
> > other, the case where both are non-None is not handled correctly.
>
> The code you posted didn't return anything if both values were non-None.

Yep, it was just a snippet, just the part I wanted feedback on.

> As for checking for None-ness vs. non-None-ness, sure, the two are
> logically equivalent, but I think checking for non-None expresses the
> algorithm more clearly.

In this particular case it's somewhat more elegant (IMO) to check "is
None".

> > FWIW, here's the BinaryTree class, ...
> >     A Binary Tree implementation. Provides:
> >         get(key) - Return item for key or None.
>
> I'm sorry but I find that class rather ugly.  The code would be a lot
> smaller and have fewer corner cases with a different data
> representation.

Um, thanks?  Seriously though, care to put your money where your mouth
is? I'd be interested to see a BTree implemented as you indicated
above.

Pointer code in python is silly in general, since you're only
imitating real pointers with attributes (i.e. instance dicts) anyway.
As I said above, I'm faking it with python to explore persistent data
structures and the models I've found so far are pointer-based.  I'm
sure there are better (i.e. faster) ways to get the same (or
sufficiently similar) behavior in a more "pythonic" fashion. (for
example, to maintain a sorted sequence under insertion I'd use a list
and the bisect module, and so on.)

Reminds me, a few years back I implemented Knuth's "Dancing Links"
algorithm in python for a Sudoku solver.  It uses a kind of grid of
doubly-linked lists to store information about the search space and to
traverse that space to resolve an answer.  The algorithm takes
advantage of the fact that allocated nodes persisted in memory even
when completely unlinked from the "surrounding" lists.  You unlinked
and re-linked the nodes/lists in a certain pattern to search and
backtrack the search space.  It's more than I can explain here. Really
elegant algorithm.

The point is in python you had to put ALL the nodes into a storage
structure just to prevent them disappearing while unlinked from the
"head" of the grid.

Regards,
~Simon