Re: Trees
On Thursday, January 22, 2015 at 12:46:22 PM UTC+5:30, Paul Rubin wrote: > Ian Kelly writes: > > How do you create a tree containing an even number of elements under > > this constraint? > > That's a good point, I've usually seen different definitions of trees, > e.g. > >data Tree a = Leaf | Branch a (Tree a) (Tree a) > > so a Leaf node doesn't have a value associated with it. Maybe you should call 'Leaf' instead as EmptyTree Then does it answer Ian's question? Or Nil Null or some such then it is most obviously isomorphic to the typical way of doing it in C. The point is that these are frameworks for structural induction. So choosing base-cases carefully is important. This may seem harmless but is probably not a good idea data Tree a = Empty | Leaf a | Branch a (Tree a) (Tree a) OTOH the classic S-exp of lisp would be modelled as data Sexp b = Cons (Sexp b) (Sexp b) | Leaf b which captures the fact that the elements (b) are only at the leaves and the conses provide pure branching without content ie its not ... Cons b (Sexp b) (Sexp b)... -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Ian Kelly writes: > How do you create a tree containing an even number of elements under > this constraint? That's a good point, I've usually seen different definitions of trees, e.g. data Tree a = Leaf | Branch a (Tree a) (Tree a) so a Leaf node doesn't have a value associated with it. https://en.wikipedia.org/wiki/File:Red-black_tree_example.svg has a picture of such a tree--don't worry about the node coloring for this purpose. Or the multi-way tree with arbitrary branching width: data RoseTree a = RoseTree a [RoseTree a] Each node has a value and a list of zero or more subtrees. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 10:20 PM, Rustom Mody wrote: > On Thursday, January 22, 2015 at 4:25:03 AM UTC+5:30, Ian wrote: >> On Tue, Jan 20, 2015 at 6:23 PM, Rustom Mody wrote: >> > The Haskell is bullseye¹ in capturing the essense of a tree because >> > conceptually a tree of type t is recursive in the sense that it can contain >> > 2 subtrees -- (B x lst rst) -- or its a base case -- L x. >> >> How do you create a tree containing an even number of elements under >> this constraint? > > Not sure what you are asking... > > [And a text only group makes discussing pictur-esque things hard] > What do you mean by 'element'? > Leaf? Internal? Either? By "element" I mean an individual datum contained in the tree. Likewise the elements of a list are its contents. Since each element is associated with a node, the question could equally be phrased as "How do you create a tree containing an even number of elements under this constraint?" The point I was driving at is that the definition is incomplete -- in addition to being an internal node or a leaf, a tree can also be empty. In fact I would suggest that an empty tree should be the real base case, since what is a leaf node but a node where both of its children are empty trees? -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 11:56 PM, Ian Kelly wrote: > Since each element is associated with a node, the question could > equally be phrased as "How do you create a tree containing an even > number of elements under this constraint?" Of course I meant to write "nodes" there, not "elements". -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Thursday, January 22, 2015 at 4:25:03 AM UTC+5:30, Ian wrote: > On Tue, Jan 20, 2015 at 6:23 PM, Rustom Mody wrote: > > The Haskell is bullseye¹ in capturing the essense of a tree because > > conceptually a tree of type t is recursive in the sense that it can contain > > 2 subtrees -- (B x lst rst) -- or its a base case -- L x. > > How do you create a tree containing an even number of elements under > this constraint? Not sure what you are asking... [And a text only group makes discussing pictur-esque things hard] What do you mean by 'element'? Leaf? Internal? Either? -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Thursday, January 22, 2015 at 3:57:50 AM UTC+5:30, Paul Rubin wrote: > Rustom Mody writes: > > Thats not bfs. That's inorder traversal > > Oops, you're right. How's this: > > bfs x = go [x] where > go [] = [] > go (L x:ts) = x:go ts > go (B x lst rst:ts) = x : go (ts ++ [lst, rst]) > > *Main> bfs t > [6,2,8,1,4,7,9,3,5] Yeah thats right. And now you can get the duality between dfs and bfs you were earlier after by replacing the ts ++ [lst,rst] with [lst,rst] ++ ts BTW this is just converting queue to stack; And its neat; and out of reach of those who think only imperatively PS 1. Ive not tried it 2. For n-ary trees its neater 3. In my imaginary language with first-class sets, bags, lists it would be neater still -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 6:23 PM, Rustom Mody wrote: > The Haskell is bullseye¹ in capturing the essense of a tree because > conceptually a tree of type t is recursive in the sense that it can contain > 2 subtrees -- (B x lst rst) -- or its a base case -- L x. How do you create a tree containing an even number of elements under this constraint? -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Rustom Mody writes: > Thats not bfs. That's inorder traversal Oops, you're right. How's this: bfs x = go [x] where go [] = [] go (L x:ts) = x:go ts go (B x lst rst:ts) = x : go (ts ++ [lst, rst]) *Main> bfs t [6,2,8,1,4,7,9,3,5] -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 9:15 AM, Ian Kelly wrote: > class MultiSet(MutableSet): In retrospect this probably shouldn't derive from MutableSet, since that carries the expectation that all elements are unique (much like how bool shouldn't be subclassed). For instance, collections.Set includes some operators that aren't compatible with the second operand being a multiset. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 7:47 AM, Steven D'Aprano
wrote:
>> More irksome that for the second we've to preface with
>>
>> from collections import Counter
>>
>> And still more a PITA that a straightforward standard name like bag (or
>> multiset) is called by such an ungoogleable misleading name as counter.
>
> It is not misleading. collections.Counter is a class for counting (i.e. a
> counter), not a bag. It is merely *similar* to a bag, but the API is not
> the same as the usual bag API because the motivating design is not the same
> as for bags.
To expand on this, Counter does provide a few multiset operations like
union and intersection. But there are a number of cases where it falls
short or does not perform as expected. To name a few:
* There are no subset or superset comparison operations provided.
* len(counter) returns the number of keys, not the number of elements.
* Unlike a multiset, Counters can have negative or zero counts; one
curious consequence of this is that an "empty" Counter can have a
non-zero length and evaluate as true in boolean contexts.
A while back I fiddled around with creating a true MultiSet class
using a Counter as the underlying implementation. Here's what I came
up with:
from collections import Counter
from collections.abc import MutableSet, Set
__all__ = ['MultiSet']
class MultiSet(MutableSet):
"""Multiset class containing hashable items."""
# Class invariants:
# * self._counter is a Counter s/t all values are positive ints denoting
# multiplicity.
# * set(self) == self._counter.keys()
def __init__(self, iterable_or_mapping=()):
"""Create a new, empty MultiSet. If passed an iterable argument, initialize
the MultiSet with items from the iterable. If passed a mapping argument,
initialize the MultiSet with the keys of the mapping, each repeated a number
of times equal to the associated value.
"""
self._counter = +Counter(iterable_or_mapping)
@classmethod
def _from_counter(cls, counter):
self = cls.__new__(cls)
self._counter = counter
return self
def __contains__(self, item):
return item in self._counter
def __hash__(self):
raise TypeError('unhashable type: %s' % type(self))
def __iter__(self):
return self._counter.elements()
def __len__(self):
# TODO: consider caching the length.
return sum(self._counter.values())
def __repr__(self):
if self:
return 'MultiSet(%r)' % list(self)
return 'MultiSet()'
def add(self, item):
"""Add an element to the MultiSet."""
self._counter[item] += 1
def clear(self):
"""Remove all elements from the MultiSet, leaving it empty."""
self._counter.clear()
def count(self, item):
"""Return the number of occurrences of the element."""
return self._counter[item]
def discard(self, item):
"""Remove an element from the MultiSet.
If there are multiple occurrences, remove only one such occurrence. If the
element is not a member, do nothing.
"""
if item not in self._counter:
return
if self._counter[item] == 1:
del self._counter[item]
else:
self._counter[item] -= 1
def __or__(self, other):
"""Return the union of the MultiSet and another set."""
if not isinstance(other, Set):
return NotImplemented
return self._from_counter(self._counter | _get_counter(other))
__ror__ = __or__
def __ior__(self, other):
"""Perform the in-place union of the MultiSet and another set."""
if not isinstance(other, Set):
return NotImplemented
self._counter |= _get_counter(other)
return self
def __and__(self, other):
"""Return the intersection of the MultiSet and another set."""
if not isinstance(other, Set):
return NotImplemented
return self._from_counter(self._counter & _get_counter(other))
__rand__ = __and__
def __iand__(self, other):
"""Perform the in-place intersection of the MultiSet and another set."""
if not isinstance(other, Set):
return NotImplemented
self._counter &= _get_counter(other)
return self
def __sub__(self, other):
"""Return the difference of the MultiSet and another set."""
if not isinstance(other, Set):
return NotImplemented
return self._from_counter(self._counter - _get_counter(other))
def __rsub__(self, other):
"""Return the difference of another set and the MultiSet."""
if not isinstance(other, Set):
return NotImplemented
return self._from_counter(_get_counter(other) - self._counter)
def __isub__(self, other):
"""Perform the in-place set difference of the MultiSet and another set."""
if not isinstance(other, Set):
return NotImplemented
self._counter -= _get_counter(other)
return self
def __xor__(self, other):
"""Return the symmetric difference of the MultiSet and another set."""
if not isinstance(other, Set):
return NotImplemented
# X ^ Y == (X - Y) | (Y - X)
other_counter = _get
Re: Trees
On Wednesday, January 21, 2015 at 6:06:06 PM UTC+5:30, Chris Angelico wrote:
> On Wed, Jan 21, 2015 at 11:09 PM, Rustom Mody wrote:
> > I would like a set to be {1,2,3} or at worst ⦃1,2,3⦄
> > and a bag to be ⟅1,2,3⟆
> >
> > Apart from the unicode niceness that Ive described here
> > http://blog.languager.org/2014/04/unicoded-python.html
> >
> > Its a bit of a nuisance that we have to write set([1,2,3]) for the first
>
> Wait, what?
>
> rosuav@sikorsky:~$ python
> Python 2.7.3 (default, Mar 13 2014, 11:03:55)
> [GCC 4.7.2] on linux2
> Type "help", "copyright", "credits" or "license" for more information.
> >>> type({1,2,3})
>
> >>>
> rosuav@sikorsky:~$ python3
> Python 3.5.0a0 (default:4709290253e3, Jan 20 2015, 21:48:07)
> [GCC 4.7.2] on linux
> Type "help", "copyright", "credits" or "license" for more information.
> >>> type({1,2,3})
>
> >>>
>
> Looks like {1,2,3} works for me.
>
> ChrisA
Ah thank you -- forgot -- mea culpa.
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Rustom Mody wrote:
> On Wednesday, January 21, 2015 at 1:27:39 PM UTC+5:30, Stephen Hansen
> wrote:
[...]
> Among my teachers of CS, there were two – both brilliant — one taught me
> Numerical Analysis, the other taught me programming.
I wonder just how brilliant the Numerical Analysis guy really was.
> The point is that the two of them disagreed strongly on what programming
> was about.
>
> The numerical analyst could see no earthly reason to use anything other
> than Fortran.
Would you consider a cook who boiled everything "brilliant"? Somebody who
insisted that there was no earthly reason to have an oven, a frying pan, a
wok, or a steamer?
Or somebody who insisted that the *one and only* use for chemistry was to
set fire to wood and boil water?
Computers are used for vastly more than just numerical analysis.
> The programmer had horror stories to tell about how Fortran damages the
> brain: eg programs that inherently need a while-loop (eg binary search)
> seem to be
> distinctly out of the reach of the Fortran programmer. Recursion...
> And much else.
>
> The numerical analyst of course had no use for this philosophizing.
And how did this brilliant numerical analyst perform fast, efficient
searches of sorted data?
> The view that strings and floats are more fundamental than containers and
> maps reminds me of this view.
A strange comment to make.
I can insert a string or a float inside a container or map, but I cannot
insert a container or map inside a string or float.
Consider the computer hardware we use. Certain data structures are
fundamental to the architecture we use: bytes, pointers, ints, arrays are
very low-level. Floats are a little more complex -- they have a more
complex internal structure than ints. Hash tables are more complex still.
> For me python is neat because I can write: [1,2,3]
> when I want a list.
> But it does not go nearly far enough.
>
> I would like a set to be {1,2,3} or at worst ⦃1,2,3⦄
> and a bag to be ⟅1,2,3⟆
In Python, you can write sets {1, 2, 3}.
Out of curiosity, what input method did you use to get those Unicode
characters? How many keystrokes or mouse clicks did it take to get this?
\N{LEFT S-SHAPED BAG DELIMITER} 1, 2, 3 \N{RIGHT S-SHAPED BAG DELIMITER}
"bag([1, 2, 3])" requires only 16 keypresses, and it is visible on virtually
every computer, while ⟅ ⟆ look like small boxes to me and probably most
people.
[...]
> More irksome that for the second we've to preface with
>
> from collections import Counter
>
> And still more a PITA that a straightforward standard name like bag (or
> multiset) is called by such an ungoogleable misleading name as counter.
It is not misleading. collections.Counter is a class for counting (i.e. a
counter), not a bag. It is merely *similar* to a bag, but the API is not
the same as the usual bag API because the motivating design is not the same
as for bags.
As for being "ungoogleable", that is just simply false. Perhaps you forgot
to push the enter key after typing in your search terms?
https://www.google.com.au/search?q=python+counter
The top three links are:
https://docs.python.org/2/library/collections.html
https://docs.python.org/3.3/library/collections.html
http://pymotw.com/2/collections/counter.html
and seven out of the ten links on the first page of results are about
Counter.
Your results may differ from mine, since Google bubbles your searches. But
Duck Duck Go doesn't:
https://duckduckgo.com/?q=python%20counter
Its results are not quite as good as Google's, but it finds the backported
Counter class on PyPI (which Google didn't) and it too links to the Python
Module Of The Week page. Adding "collections" to the search terms brings
the results up to Google quality.
So as you can see, it simply is not true that "Counter" is ungoogleable.
--
Steven
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Thu, Jan 22, 2015 at 1:26 AM, Tim Chase
wrote:
> While 2.0 is certainly antiquated, Red Hat Enterprise Linux (RHEL) is
> often considered the best definition of what's considered "oldest
> supported production environment". RHEL v4 ships with Py2.3 and one
> can still obtain extended support for this environment. RHEL v5 is
> actively supported (i.e., without the need for an extended-support
> contract) and ships with Py2.4 so I generally try to at least support
> 2.4 when I'm writing code that could possibly end deploy on a server
> such as RHEL5. Some of us are stuck supporting code in such
> antediluvian environments. :-/ Then again, if you're like me and
> working in such environments, you already know to use set() instead
> of {...} and to avoid the "with" statement, and the like. :)
I'm aware that there are reasons for wanting to support older versions
of things. I do it myself in several places (though not specifically
with Python pre-2.7). But there's still a difference between "Moan
moan, we have to use set([1,2,3]) when {1,2,3} would make *so* much
more sense" and "Sadly, I have to ensure that my code works on Python
2.4, so I can't take advantage of all the newer features". One is a
complaint about the language; the other is an acknowledgement of the
personal pain of having to support multiple versions (and is going to
get easier; as years go by, the oldest Python on a supported RHEL will
become newer).
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 2015-01-22 00:01, Chris Angelico wrote:
> On Wed, Jan 21, 2015 at 11:55 PM, Tim Chase
>>> Looks like {1,2,3} works for me.
>>
>> That hasn't always worked:
>
> the argument's still fairly weak when it's alongside a pipe-dream
> desire to use specific mathematical Unicode characters in source
> code, because that's clearly a 3.x-only feature (where source code
> is Unicode text rather than ASCII).
I'm 100% in agreement that Unicode characters are a pipe-dream. If I
wanted that, I'd use APL ;-)
> Nobody's going to moan "It's silly that we have to use 1 and 0
> instead of nice keywords True and False" on the basis that True and
> False didn't exist in Python 2.0. At very least, use 2.7 before you
> complain; preferably, use 3.4 (or 3.5).
While 2.0 is certainly antiquated, Red Hat Enterprise Linux (RHEL) is
often considered the best definition of what's considered "oldest
supported production environment". RHEL v4 ships with Py2.3 and one
can still obtain extended support for this environment. RHEL v5 is
actively supported (i.e., without the need for an extended-support
contract) and ships with Py2.4 so I generally try to at least support
2.4 when I'm writing code that could possibly end deploy on a server
such as RHEL5. Some of us are stuck supporting code in such
antediluvian environments. :-/ Then again, if you're like me and
working in such environments, you already know to use set() instead
of {...} and to avoid the "with" statement, and the like. :)
Sources:
http://en.wikipedia.org/wiki/Red_Hat_Enterprise_Linux#Version_history
http://turbogears.org/1.0/docs/Install/Nix.html#centos-rhel RHEL=2.3
https://wiki.archlinux.org/index.php/python#Old_versions RHEL5=2.4
-tkc
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Hello Terry, It is not play with words. A tree is a recursive - nested - hierachical data structure with the restriction of no cycles or alternate pathways. Python collections whose members are general objects, including collections, can be nested. The resulting structures *are* tree structures, if not more general directed graphs. They are quite commonly used in Python. Let's get somethig clear. Tree data structures have an associated logic that justifies their name as a de facto Tree Data Structure. If your low level description was how you described a tree to someone new to the concept, they would be none the wiser about what a Tree represents or what uses they could have for them. This logic is no different from the internal logic that diferentiates a dictionary from a list and helps carry their distinct operations. Despite a dictionary being nothing more than a glorified list. Just as well, tree data structures only make sense along with their logic. Storage, traversal, insertion, random searches, retrieval, etc, all these algorithms are what in the end define a Tree data structure and what will help categorize it. Python standard library doesn't have any tree data structure implementation. It has lists, dictionaries, and other base structures that in the end will help define storage patterns for tree data structures. And that's it. A simple binary tree needs to be implemented in Python as a binary tree, if it wants to be recognized as such. All your code examples illustrate exactly that. And if you care about code reuse, you will want to define a number of associated algorithms to take advantage of your storage model and answer your performance or memory requirements. Along with your list pattern for storage, you will probably also want to implement an insertion/search/update/traversal algorithms. That's when you have a tree. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 11:55 PM, Tim Chase
wrote:
> On 2015-01-21 23:35, Chris Angelico wrote:
>> On Wed, Jan 21, 2015 at 11:09 PM, Rustom Mody wrote
>> > Its a bit of a nuisance that we have to write set([1,2,3]) for
>> > the first
>>
>> Looks like {1,2,3} works for me.
>
> That hasn't always worked:
Sure, but "we have to write" implies current status; Python 2.7 was
released in 2010, so I would expect that anyone who's complaining
about set notation should have access to it. Even if it didn't work in
2.7 and you had to use 3.x, the argument's still fairly weak when it's
alongside a pipe-dream desire to use specific mathematical Unicode
characters in source code, because that's clearly a 3.x-only feature
(where source code is Unicode text rather than ASCII).
Nobody's going to moan "It's silly that we have to use 1 and 0 instead
of nice keywords True and False" on the basis that True and False
didn't exist in Python 2.0. At very least, use 2.7 before you
complain; preferably, use 3.4 (or 3.5).
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 2015-01-21 23:35, Chris Angelico wrote:
> On Wed, Jan 21, 2015 at 11:09 PM, Rustom Mody wrote
> > Its a bit of a nuisance that we have to write set([1,2,3]) for
> > the first
>
> Wait, what?
>
> rosuav@sikorsky:~$ python
> Python 2.7.3 (default, Mar 13 2014, 11:03:55)
> [GCC 4.7.2] on linux2
> Type "help", "copyright", "credits" or "license" for more
> information.
> >>> type({1,2,3})
>
> >>>
> rosuav@sikorsky:~$ python3
> Python 3.5.0a0 (default:4709290253e3, Jan 20 2015, 21:48:07)
> [GCC 4.7.2] on linux
> Type "help", "copyright", "credits" or "license" for more
> information.
> >>> type({1,2,3})
>
> >>>
>
> Looks like {1,2,3} works for me.
That hasn't always worked:
tim@bigbox:~$ python2.5
Python 2.5.5 (r255:77872, Nov 28 2010, 16:43:48)
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> type({1,2,3})
File "", line 1
type({1,2,3})
^
SyntaxError: invalid syntax
tim@bigbox:~$ python2.6
Python 2.6.8 (unknown, Jan 26 2013, 14:35:25)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> type({1,2,3})
File "", line 1
type({1,2,3})
^
SyntaxError: invalid syntax
And, prior to 2.4, you had to write
from sets import Set as set
to even get sets.
https://docs.python.org/2/whatsnew/2.4.html#pep-218-built-in-set-objects
-tkc
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 11:09 PM, Rustom Mody wrote:
> I would like a set to be {1,2,3} or at worst ⦃1,2,3⦄
> and a bag to be ⟅1,2,3⟆
>
> Apart from the unicode niceness that Ive described here
> http://blog.languager.org/2014/04/unicoded-python.html
>
> Its a bit of a nuisance that we have to write set([1,2,3]) for the first
Wait, what?
rosuav@sikorsky:~$ python
Python 2.7.3 (default, Mar 13 2014, 11:03:55)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> type({1,2,3})
>>>
rosuav@sikorsky:~$ python3
Python 3.5.0a0 (default:4709290253e3, Jan 20 2015, 21:48:07)
[GCC 4.7.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> type({1,2,3})
>>>
Looks like {1,2,3} works for me.
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wednesday, January 21, 2015 at 1:27:39 PM UTC+5:30, Stephen Hansen wrote:
> On Tue, Jan 20, 2015 at 1:45 AM, Marko Rauhamaa wrote:
> Terry Reedy :
>
>
>
> > Others have answered as to why other special-purpose
>
> > constrained-structure trees have not been added to the stdlib.
>
>
>
> Ordered O(log n) mappings are not special-purpose data structures. I'd
>
> say strings and floats are much more special-purpose than ordered
>
> mappings, and yet Python has direct support for those.
>
>
>
> Your anecdote is strong, sir.
>
>
> However, I use strings thousands of times, floats maybe a hundred of times,
> and order mappings a few times.
>
>
> My anecdote counters yours.
>
>
> A tree structure is special purpose because there is a lot of options with
> different characteristics that make certain implementations ideal in some
> cases and not in others.
>
>
> A float is a float, there's a standard (IEEE 754?), its not special at all.
>
>
> A string, I suppose, could be special, but that's a pretty nonsense view of
> the world since what most people use strings commonly.
>
>
> I'm not arguing against including a tree, but I have no advice on which one,
> and the one-- one!-- time I've needed a tree I got one off pypi. Not
> everything needs to be in the stdlib.
>
>
> But to call strings and floats special purpose is really a silly argument to
> make.
Since we are trading anecdotes…
Among my teachers of CS, there were two – both brilliant — one taught me
Numerical Analysis, the other taught me programming.
[As it happens my initial practical programming was the numerical kind
because the Fortran compiler was more serviceable than the Pascal one.
But thats a different point]
The point is that the two of them disagreed strongly on what programming was
about.
The numerical analyst could see no earthly reason to use anything other than
Fortran.
The programmer had horror stories to tell about how Fortran damages the brain:
eg programs that inherently need a while-loop (eg binary search) seem to be
distinctly out of the reach of the Fortran programmer. Recursion...
And much else.
The numerical analyst of course had no use for this philosophizing.
The view that strings and floats are more fundamental than containers and maps
reminds me of this view.
For me python is neat because I can write: [1,2,3]
when I want a list.
But it does not go nearly far enough.
I would like a set to be {1,2,3} or at worst ⦃1,2,3⦄
and a bag to be ⟅1,2,3⟆
Apart from the unicode niceness that Ive described here
http://blog.languager.org/2014/04/unicoded-python.html
Its a bit of a nuisance that we have to write set([1,2,3]) for the first
More irksome that for the second we've to preface with
from collections import Counter
And still more a PITA that a straightforward standard name like bag (or
multiset)
is called by such an ungoogleable misleading name as counter.
--
https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Stephen Hansen : > On Tue, Jan 20, 2015 at 1:45 AM, Marko Rauhamaa wrote: >> Terry Reedy : >> > Others have answered as to why other special-purpose >> > constrained-structure trees have not been added to the stdlib. >> >> Ordered O(log n) mappings are not special-purpose data structures. I'd >> say strings and floats are much more special-purpose than ordered >> mappings, and yet Python has direct support for those. > > [...] > > A string, I suppose, could be special, but that's a pretty nonsense view of > the world since what most people use strings commonly. I was reacting to the specific argument that has been made often in Python circles: ordered mappings are special-purpose. That argument has nothing to do with how often you need the data structure. It has to do with how wide an abtract niche the data structure takes in the idea space. Now, you could make an argument that there's barely ever a practical need for ordered mappings (whether right or wrong), and that would elicit a different kind of response from me. These and other arguments factor into whether the Python standard library should contain a feature, ultimately it's GvR's arbitrary call. He said you should first let it ripen in pypi and gain widespread traction. Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Hash Table, Christiania (a table with many kinds of hash) On 1/20/2015 12:19 PM, Devin Jeanpierre wrote: There are similarly many kinds of hash tables. For a given use case (e.g. a sorted dict, or a list with efficient removal, etc.), there's a few data structures that make sense, and a library (even the standard library) doesn't have to expose which one was picked as long as the performance is good. -- Devin On Tue, Jan 20, 2015 at 12:15 PM, Ken Seehart wrote: Exactly. There are over 23,000 different kinds of trees. There's no way you could get all of them to fit in a library, especially a standard one. Instead, we prefer to provide people with the tools they need to grow their own trees. http://caseytrees.org/programs/planting/ctp/ http://www.ncsu.edu/project/treesofstrength/treefact.htm http://en.wikipedia.org/wiki/Tree On 1/19/2015 3:01 PM, Mark Lawrence wrote: On 19/01/2015 22:06, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Probably because you'd never get agreement as to which specific tree and which specific implementation was the most suitable for inclusion. -- https://mail.python.org/mailman/listinfo/python-list -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 1:45 AM, Marko Rauhamaa wrote: > Terry Reedy : > > > Others have answered as to why other special-purpose > > constrained-structure trees have not been added to the stdlib. > > Ordered O(log n) mappings are not special-purpose data structures. I'd > say strings and floats are much more special-purpose than ordered > mappings, and yet Python has direct support for those. > Your anecdote is strong, sir. However, I use strings thousands of times, floats maybe a hundred of times, and order mappings a few times. My anecdote counters yours. A tree structure is special purpose because there is a lot of options with different characteristics that make certain implementations ideal in some cases and not in others. A float is a float, there's a standard (IEEE 754?), its not special at all. A string, I suppose, could be special, but that's a pretty nonsense view of the world since what most people use strings commonly. I'm not arguing against including a tree, but I have no advice on which one, and the one-- one!-- time I've needed a tree I got one off pypi. Not everything needs to be in the stdlib. But to call strings and floats special purpose is really a silly argument to make. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 5:22 PM, Joshua Landau wrote: > On 20 January 2015 at 04:21, Dan Stromberg wrote: >> On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence >> wrote: >>> >>> I don't know if you've seen this http://kmike.ru/python-data-structures/ but >>> maybe of interest. >> >> I've seen it. It's a nice page. >> >> I attempted to get my treap port in there since it has a Cython >> version, but it didn't seem to take. >> >> I've mostly focused on pure python that runs on CPython 2.x, CPython >> 3.x, Pypy, Pypy3 and Jython. > > http://www.grantjenks.com/docs/sortedcontainers/ > > SortedContainers is seriously great stuff; faster and lower memory > than the Cython variants yet pure Python and more featureful. It has an interesting comparison. I find myself wishing the graphs were higher resolution (the lines are frequently overlapping to the point that I cannot read the graphs), and that the maximum number of elements was greater than 10**6. Some of the timings end up taking less than a second even at the larger sizes. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 21/01/2015 01:22, Joshua Landau wrote: On 20 January 2015 at 04:21, Dan Stromberg wrote: On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence wrote: I don't know if you've seen this http://kmike.ru/python-data-structures/ but maybe of interest. I've seen it. It's a nice page. I attempted to get my treap port in there since it has a Cython version, but it didn't seem to take. I've mostly focused on pure python that runs on CPython 2.x, CPython 3.x, Pypy, Pypy3 and Jython. http://www.grantjenks.com/docs/sortedcontainers/ SortedContainers is seriously great stuff; faster and lower memory than the Cython variants yet pure Python and more featureful. Assuming the above and the testimonials are correct how the hell on earth did the author manage it? This is the one thing that *REALLY* annoys me about Python, my mind just doesn't stretch far enough to harness all of the power that's available in it. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 1/20/2015 4:47 PM, Mario wrote: In article , rustompm...@gmail.com says... Yeah python has trees alright. Heres' some simple tree-code Didn't you just demonstrate that Python has no trees and instead you have to implement them yourself (or use a third-party implementation)? I don't know what's the point of all this vain and misleading play with words. It is not play with words. A tree is a recursive - nested - hierachical data structure with the restriction of no cycles or alternate pathways. Python collections whose members are general objects, including collections, can be nested. The resulting structures *are* tree structures, if not more general directed graphs. They are quite commonly used in Python. The common question -- "How do I flatten a list" -- is asking "How to I turn a list from a tree (or DAG, but not a cyclic graph*) into a sequence of leaf objects". The question illustrates what is missing - builtin functions or methods for nested collections. I already suggested that there *might* be a useful addition in this direction. * A Python interpreter needs to take special measures to even display an infinitely recursive list without raising or even segfaulting. Most posted 'flatten' functions do not account for this possibility. >>> l = [1] >>> l.append(l) >>> l [1, [...]] > Not only most languages don't implement trees in their standard libraries Typically, built-in collection type C has members of type M that does not include type C. Therefore a C instance cannot (directly) contain a C instance. The result is that people write a 'design pattern' to overcome the limitation and enable a C to indirectly include a C. Since this limitations does not exist in Python's generalized collections of objects, the pattern is unneeded in Python. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wednesday, January 21, 2015 at 7:19:39 AM UTC+5:30, Paul Rubin wrote: > Rustom Mody writes: > > ## The depth first algorithm > > dfs (L x) = [x] > > dfs (B x lst rst) = [x] ++ dfs lst ++ dfs rst > > Cute. I can't resist posting the similar breadth first algorithm: > > bfs (L x) = [x] > bfs (B x lst rst) = bfs lst ++ [x] ++ bfs rst > > > *Main> dfs t > > [6,2,1,4,3,5,8,7,9] > > *Main> bfs t > [1,2,3,4,5,6,7,8,9] Eh?? Thats not bfs. That's inorder traversal The bfs of http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html is [6,2,8, 1,4,7,9, 3,5] -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Rustom Mody writes: > ## The depth first algorithm > dfs (L x) = [x] > dfs (B x lst rst) = [x] ++ dfs lst ++ dfs rst Cute. I can't resist posting the similar breadth first algorithm: bfs (L x) = [x] bfs (B x lst rst) = bfs lst ++ [x] ++ bfs rst > *Main> dfs t > [6,2,1,4,3,5,8,7,9] *Main> bfs t [1,2,3,4,5,6,7,8,9] > The Haskell is bullseye¹ in capturing the essense of a tree because > conceptually a tree of type t is recursive in the sense that it can contain > 2 subtrees -- (B x lst rst) -- or its a base case -- L x. You might like this discussion of a red-black tree implementation whose datatype makes sure the RB tree invariants are preserved. The data definition is kind of verbose, but with more recent GHC versions it can be made a lot crisper, with datakinds and type-level numeric literals. https://www.reddit.com/r/haskell/comments/ti5il/redblack_trees_in_haskell_using_gadts_existential/ -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wednesday, January 21, 2015 at 3:18:03 AM UTC+5:30, Mario wrote: > rustompmody says... > > > > Yeah python has trees alright. > > > > Heres' some simple tree-code > > Didn't you just demonstrate that Python has no trees and instead you > have to implement them yourself (or use a third-party implementation)? > > I don't know what's the point of all this vain and misleading play with > words. Point. You snipped off Terry's lines which I was replying (rather adding) to: > Sequences nested withing sequences can be regarded as trees, and Python > has these. I regard Lisp as a tree processing languages, as it must be > to manipulate, for example, code with nested structures. To those who are familiar with Lisp this is not new. To others it is likely too dense to be easily comprehensible. > Not only most languages don't implement trees in their standard > libraries (its no shame, it's no sin), but also it's quite evident that > there's a big difference between implementing a data structure yourself > through the application of language facilities and seeing that data > structure already implemented for you in the standard library. Its not a binary but a spectrum. Do the equivalent of "implement yourself with language facilities" in C or Java for the above code and you will see one end of the spectrum. Here's Haskell at the other end of the spectrum: [Renamed the (I)nternal tag to the (B)ranch tag because of I-1 visual clash] === ## The type data Tree t = L t | B t (Tree t) (Tree t) ## The depth first algorithm dfs (L x) = [x] dfs (B x lst rst) = [x] ++ dfs lst ++ dfs rst ## Example tree: t = (B 6 (B 2 (L 1) (B 4 (L 3) (L 5))) (B 8 (L 7) (L 9))) ## Example run *Main> dfs t [6,2,1,4,3,5,8,7,9] == The Haskell is bullseye¹ in capturing the essense of a tree because conceptually a tree of type t is recursive in the sense that it can contain 2 subtrees -- (B x lst rst) -- or its a base case -- L x. The same thing in C needs a mutually recursive data structure: One needs two types – a node *containing* pointers; a pointer *pointing* to node And then go from binary to n-ary trees and the shit hits the ceiling: 4-way mutual recursion: Tree-node, tree-node-pointer; list-node; list-pointer. Completely transparent in Haskell: data Nary t = Tr t [Nary t] Python's not as trivial to get right as Haskell [get one of the subtrees wrong and the error-messages are quite unhelpful] However its way better than C. So there's a spectrum C → Java → Python → Haskell → Tree-DSL² ¹ Well not quite bullseye because a mathematician would prefer a *set* of subtrees where we get at best a *list* ² eg UUAG http://www.andres-loeh.de/AGee.pdf -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 20 January 2015 at 04:21, Dan Stromberg wrote: > On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence > wrote: >> >> I don't know if you've seen this http://kmike.ru/python-data-structures/ but >> maybe of interest. > > I've seen it. It's a nice page. > > I attempted to get my treap port in there since it has a Cython > version, but it didn't seem to take. > > I've mostly focused on pure python that runs on CPython 2.x, CPython > 3.x, Pypy, Pypy3 and Jython. http://www.grantjenks.com/docs/sortedcontainers/ SortedContainers is seriously great stuff; faster and lower memory than the Cython variants yet pure Python and more featureful. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 20/01/15 01:49, Dan Stromberg wrote: I think probably the most common need for a tree is implementing a cache, That is probably true, at least if you're a squirrel. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
In article , rustompm...@gmail.com says... > > Yeah python has trees alright. > > Heres' some simple tree-code Didn't you just demonstrate that Python has no trees and instead you have to implement them yourself (or use a third-party implementation)? I don't know what's the point of all this vain and misleading play with words. Not only most languages don't implement trees in their standard libraries (its no shame, it's no sin), but also it's quite evident that there's a big difference between implementing a data structure yourself through the application of language facilities and seeing that data structure already implemented for you in the standard library. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Paul Rubin : > You could look up the "timer wheel" approach used by the Linux kernel > and by Erlang. It's less general than an ordered map, but probably > faster in practice. > > https://lkml.org/lkml/2005/10/19/46 > > Has some info. I think the kernel uses a different method now though. I haven't followed it closely, but I believe the realtime timers use a red-black tree. Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Paul Rubin : > Marko Rauhamaa writes: >> So in my Python software (both at work and at home) needs, I use a >> Python AVL tree implementation of my own. My use case is timers. (GvR >> uses heapq for the purpose.) > > Have you benchmarked your version against heapq or even the builtin > sorting functions? Yes, I did (as I mentioned in an earlier posting). For the use case I was interested in (timers in a busy server), heapq beefed with the "garbage collection" trick came out about the same as my AVL tree (native module). Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Wed, Jan 21, 2015 at 7:15 AM, Ken Seehart wrote: > Exactly. There are over 23,000 different kinds of trees. There's no way you > could get all of them to fit in a library, especially a standard one. > Instead, we prefer to provide people with the tools they need to grow their > own trees. I'm not sure whether you're talking about algorithmic or arboreal trees here... I'm fairly sure the State Library of Victoria contains 23,000 trees, albeit in a slightly modified form. But the State Library is not a standard one. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
There are similarly many kinds of hash tables. For a given use case (e.g. a sorted dict, or a list with efficient removal, etc.), there's a few data structures that make sense, and a library (even the standard library) doesn't have to expose which one was picked as long as the performance is good. -- Devin On Tue, Jan 20, 2015 at 12:15 PM, Ken Seehart wrote: > Exactly. There are over 23,000 different kinds of trees. There's no way you > could get all of them to fit in a library, especially a standard one. > Instead, we prefer to provide people with the tools they need to grow their > own trees. > > http://caseytrees.org/programs/planting/ctp/ > http://www.ncsu.edu/project/treesofstrength/treefact.htm > http://en.wikipedia.org/wiki/Tree > > On 1/19/2015 3:01 PM, Mark Lawrence wrote: >> >> On 19/01/2015 22:06, Zachary Gilmartin wrote: >>> >>> Why aren't there trees in the python standard library? >>> >> >> Probably because you'd never get agreement as to which specific tree and >> which specific implementation was the most suitable for inclusion. >> > > -- > https://mail.python.org/mailman/listinfo/python-list -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Exactly. There are over 23,000 different kinds of trees. There's no way you could get all of them to fit in a library, especially a standard one. Instead, we prefer to provide people with the tools they need to grow their own trees. http://caseytrees.org/programs/planting/ctp/ http://www.ncsu.edu/project/treesofstrength/treefact.htm http://en.wikipedia.org/wiki/Tree On 1/19/2015 3:01 PM, Mark Lawrence wrote: On 19/01/2015 22:06, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Probably because you'd never get agreement as to which specific tree and which specific implementation was the most suitable for inclusion. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 11:46:11 PM UTC+5:30, Rustom Mody wrote: > On Tuesday, January 20, 2015 at 10:51:13 PM UTC+5:30, Ian wrote: > > On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody wrote: > > > # Converting to generators is trivial > > > = > > > > :-) > > Less trivial than I thought... > Why does this not work? > > def dfsg(t): > if t[0] == L: > yield t[1] > else: > yield from dfsg(t[2]) > yield from dfsg(t[3]) Ok got it Forgot the «yield t[1]» before the two yield-from's -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Marko Rauhamaa writes: > As I said, I use ordered mappings to implement timers... The downside > of heapq is that canceled timers often flood the heapq structure..., > GvR mentioned a periodic "garbage collection" as a potentially > effective solution. You could look up the "timer wheel" approach used by the Linux kernel and by Erlang. It's less general than an ordered map, but probably faster in practice. https://lkml.org/lkml/2005/10/19/46 Has some info. I think the kernel uses a different method now though. Fwiw, I believe that the Haskell i/o manager uses an ordered map, and it gets monstrous performance: http://haskell.cs.yale.edu/wp-content/uploads/2013/08/hask035-voellmy.pdf Some comments: http://ezyang.tumblr.com/post/62152700458/haskell-mio-a-high-performance-multicore-io -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 10:51:13 PM UTC+5:30, Ian wrote: > On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody wrote: > > from enum import Enum > > class TreeTag(Enum): > > I = 0 # An internal node > > L = 1 # A leaf node > > def __repr__(self): return self.name > > > > I = TreeTag.I > > L = TreeTag.L > > Explicitly tagging nodes as internal or leaves is kind of ugly and > also prone to getting out of sync with the reality, which is that a > node is a leaf if it doesn't have any other nodes hanging off of it. Yeah... Just demoing a technique for more variegated trees eg an AST for some toy DSL or some such. Imagine you have 10 types of nodes and one defaults to tagless > > > def dfs(t): > > if t[0] == L: > > return [t[1]] > > else: > > return [t[1]] + dfs(t[2]) + dfs(t[3]) > > Over the entire tree, this will do O(n) list additions which implies > O(n) list *copies*, which is rather inefficient. This would probably > be better implemented as a recursive generator. Yeah > > def dfs(t): > yield t[0] > yield from chain.from_iterable(map(dfs, islice(t, 1, None))) > > > # Converting to generators is trivial > > = > > :-) Less trivial than I thought... Why does this not work? def dfsg(t): if t[0] == L: yield t[1] else: yield from dfsg(t[2]) yield from dfsg(t[3]) -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Steven D'Aprano writes: > Possibly because they aren't needed? Under what circumstances would > you use a tree instead of a list or a dict or combination of both? I've sometimes wanted a functional tree in the sense of functional programming. That means the tree structure is immutable and you insert or delete nodes in O(log n) operations, by creating new trees that share almost all their data with the old tree. Once you release the old root, garbage collection frees any nodes that were in the old tree but not the new one. Use case inspired by Haskell's Happstack-store (formerly called MACID): you want a Prevayler-style in-memory key-value database. First idea: all read queries are served by pure in-memory lookups in a Python dict. Write queries update the dict and also append the command to a serial log on disk (one disk write, no seeks). If the system crashes, restart it empty, and play back the log from the beginning to restore the in-memory data. Problem with first idea: the database might be a few thousand entries but take millions of updates, if entries are modified frequently. You don't want to reload the million updates from the beginning. Next idea: dump a snapshot of the dictionary now and then, and then just reload updates starting from the last snapshot. Trouble here is that the dictionary is big enough that writing out the snapshot takes time, and you don't want to lock the whole dict against more updates while the snapshot is writing. If you do this the Java way, welcome to concurrency hell as you make finer and finer grained locks and deal with resulting deadlocks, race conditions, etc. And the dictionary still has to be synchronized to avoid reads simultaneous with updates. MACID solution: use a functional red-black tree instead of a dict. To add or update an entry, make a new tree that replaces the old tree by updating a single pointer. That allows unlimited read concurrency (reading means getting the current tree pointer and navigating the tree that you get: since that tree is immutable you can keep using it while other threads make new trees). Updates are managed by a single thread that can take its time making the new tree and writing the log, and then atomically updating the in-memory root pointer that's shared with other threads. Finally, to take a snapshot, you can just get the current root and write out its contents: since it's immutable you can do that concurrently with anything else (including updates) that might be happening. You just have a small interaction with the update thread to remember where in the log to start reading from in case of a crash and reload. Finding out about this was one of the "wow" moments that made me realize I had to learn Haskell. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Marko Rauhamaa writes: > So in my Python software (both at work and at home) needs, I use a > Python AVL tree implementation of my own. My use case is timers. (GvR > uses heapq for the purpose.) Have you benchmarked your version against heapq or even the builtin sorting functions? -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody wrote: > from enum import Enum > class TreeTag(Enum): > I = 0 # An internal node > L = 1 # A leaf node > def __repr__(self): return self.name > > I = TreeTag.I > L = TreeTag.L Explicitly tagging nodes as internal or leaves is kind of ugly and also prone to getting out of sync with the reality, which is that a node is a leaf if it doesn't have any other nodes hanging off of it. > def dfs(t): > if t[0] == L: > return [t[1]] > else: > return [t[1]] + dfs(t[2]) + dfs(t[3]) Over the entire tree, this will do O(n) list additions which implies O(n) list *copies*, which is rather inefficient. This would probably be better implemented as a recursive generator. def dfs(t): yield t[0] yield from chain.from_iterable(map(dfs, islice(t, 1, None))) > # Converting to generators is trivial > = :-) -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 7:46:02 PM UTC+5:30, Marko Rauhamaa wrote: > Rustom Mody : > > > Yeah python has trees alright. > > Does Python balance them for you? No Does python support a menagerie of lists like C - singly linked, doubly linked, with header, without header etc? Or access to machine registers like assembly? And are these differences from C/Assembly in favor or against python? -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 20/01/2015 05:19, Marko Rauhamaa wrote: Mark Lawrence : On 19/01/2015 22:06, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Probably because you'd never get agreement as to which specific tree and which specific implementation was the most suitable for inclusion. Most programming languages provide one standard sorted mapping implementation. I'd have thought it would be the standard library and not the language that provided a sorted mapping. Are you also saying that this has to be implemented as a tree, such that this has to be provided by cPython, Jython, IronPython, Pypy and so on and so forth? -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Rustom Mody : > Yeah python has trees alright. Does Python balance them for you? Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence wrote: > I don't know if you've seen this http://kmike.ru/python-data-structures/ > but maybe of interest. > I haven't read but also possibly of interest: Data Structures and Algorithms in Python by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser (Wiley, 2013) [1] Python Algorithms: Mastering Basic Algorithms in the Python Language, 2nd Edition by Magnus Lie Hetland (Apress, 2014) [2] [1] http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP002510.html [2] http://www.apress.com/9781484200568 -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 7:03:56 PM UTC+5:30, Rustom Mody wrote: > On Tuesday, January 20, 2015 at 11:38:27 AM UTC+5:30, Terry Reedy wrote: > > On 1/19/2015 5:06 PM, Zachary Gilmartin wrote: > > > Why aren't there trees in the python standard library? > > > > Sequences nested withing sequences can be regarded as trees, and Python > > has these. I regard Lisp as a tree processing languages, as it must be > > to manipulate, for example, code with nested structures. > > Yeah python has trees alright. It may be best to read my example above in this order: 1. See the picture at http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html 2. Take the python representation of that >>> t [I, 6, [I, 2, [L, 1], [I, 4, [L, 3], [L, 5]]], [I, 8, [L, 7], [L, 9]]] Indent that a bit: [I, 6, [I, 2, [L, 1], [I, 4, [L, 3], [L, 5]]], [I, 8, [L, 7], [L, 9]]] Now compare with the picture above Only catch is you must see it 'lying down' Shouldn't be too hard given that we've all got used to seeing :-) as a smiley :-) -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tuesday, January 20, 2015 at 11:38:27 AM UTC+5:30, Terry Reedy wrote: > On 1/19/2015 5:06 PM, Zachary Gilmartin wrote: > > Why aren't there trees in the python standard library? > > Sequences nested withing sequences can be regarded as trees, and Python > has these. I regard Lisp as a tree processing languages, as it must be > to manipulate, for example, code with nested structures. Yeah python has trees alright. Heres' some simple tree-code from enum import Enum class TreeTag(Enum): I = 0 # An internal node L = 1 # A leaf node def __repr__(self): return self.name I = TreeTag.I L = TreeTag.L def dfs(t): if t[0] == L: return [t[1]] else: return [t[1]] + dfs(t[2]) + dfs(t[3]) # Converting to generators is trivial = # Example tree # From http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html t1 = [L, 1] t4 = [I, 4, [L, 3],[L,5]] t2 = [I, 2, t1, t4] t8 = [I, 8, [L, 7], [L, 9]] # Top level tree t = [I, 6, t2, t8] == An REPL session >>> t [I, 6, [I, 2, [L, 1], [I, 4, [L, 3], [L, 5]]], [I, 8, [L, 7], [L, 9]]] >>> dfs(t) [6, 2, 1, 4, 3, 5, 8, 7, 9] >>> t8 [I, 8, [L, 7], [L, 9]] >>> dfs(t8) [8, 7, 9] >>> -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Terry Reedy : > Others have answered as to why other special-purpose > constrained-structure trees have not been added to the stdlib. Ordered O(log n) mappings are not special-purpose data structures. I'd say strings and floats are much more special-purpose than ordered mappings, and yet Python has direct support for those. As I said, I use ordered mappings to implement timers. GvR uses the heapq module for the purpose. The downside of heapq is that canceled timers often flood the heapq structure; in networking you can easily start a thousand timers a second but virtually no timer ever expires. Python's asyncio ignores the problem, but GvR mentioned a periodic "garbage collection" as a potentially effective solution. I tested the garbage collection trick and it did seem very effective. Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Mon, Jan 19, 2015 at 11:52 PM, Devin Jeanpierre wrote: > On Mon, Jan 19, 2015 at 3:08 PM, Steven D'Aprano > wrote: >> Zachary Gilmartin wrote: >> >>> Why aren't there trees in the python standard library? >> >> Possibly because they aren't needed? Under what circumstances would you use >> a tree instead of a list or a dict or combination of both? >> >> That's not a rhetorical question. I am genuinely curious, what task do you >> have that you think must be solved by a tree? > > In general, any time you want to maintain a sorted list or mapping, > balanced search tree structures come in handy. > > Here's an example task: suppose you want to represent a calendar, > where timeslots can be reserved for something. Calendar events are not > allowed to intersect. Maybe because I'm not a computer scientist, I can't immediately see why this is a "Tree" problem and not a "Database" problem. Genuinely interested. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 1/19/2015 5:06 PM, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Sequences nested withing sequences can be regarded as trees, and Python has these. I regard Lisp as a tree processing languages, as it must be to manipulate, for example, code with nested structures. Nested structures in general represent trees or more general graph forms. The ast module uses Nodes with lists of subnodes to represent Abstract Syntax Trees. Priority queues are specialized trees implemented on top of lists. The heapq module is imported into 6 other modules. Others have answered as to why other special-purpose constrained-structure trees have not been added to the stdlib. It might possibly be useful to add a general Tree base class with pre-, in-, and post-order generators, and maybe interior and leaf node counters and max depth method. Finding uses for such a thing in the stdlib (ast?) would be a plus in favor. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Mark Lawrence : > On 19/01/2015 22:06, Zachary Gilmartin wrote: >> Why aren't there trees in the python standard library? > > Probably because you'd never get agreement as to which specific tree > and which specific implementation was the most suitable for inclusion. Most programming languages provide one standard sorted mapping implementation. GvR is highly suspicious of the utility of trees and wouldn't like to take the burden of maintaining them in the stdlib. So in my Python software (both at work and at home) needs, I use a Python AVL tree implementation of my own. My use case is timers. (GvR uses heapq for the purpose.) Marko -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Mon, Jan 19, 2015 at 11:21 PM, Dan Stromberg wrote: > On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence > wrote: > > On 20/01/2015 00:49, Dan Stromberg wrote: > >> > apropos of nothing, I went to stonybrook too. beee 1978 > >> On Mon, Jan 19, 2015 at 2:06 PM, Zachary Gilmartin > >> wrote: > >>> > >>> Why aren't there trees in the python standard library? > >> > >> > >> Trees are kind of specialized datastructures; no one type of tree > >> solves all tree-related problems suitably well. > >> > >> I think probably the most common need for a tree is implementing a > >> cache, but most times you're tempted to sort inside a loop you're > >> better off with a tree. > >> > >> I've put some time into python trees; most of them are on pypi and at: > >> http://stromberg.dnsalias.org/~dstromberg/datastructures/ > >> and: > >> > http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/ > >> > >> HTH > >> > > > > I don't know if you've seen this http://kmike.ru/python-data-structures/ > but > > maybe of interest. > > I've seen it. It's a nice page. > > I attempted to get my treap port in there since it has a Cython > version, but it didn't seem to take. > > I've mostly focused on pure python that runs on CPython 2.x, CPython > 3.x, Pypy, Pypy3 and Jython. > -- > https://mail.python.org/mailman/listinfo/python-list > -- Joel Goldstick http://joelgoldstick.com -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Mon, Jan 19, 2015 at 6:46 PM, Mark Lawrence wrote: > On 20/01/2015 00:49, Dan Stromberg wrote: >> >> On Mon, Jan 19, 2015 at 2:06 PM, Zachary Gilmartin >> wrote: >>> >>> Why aren't there trees in the python standard library? >> >> >> Trees are kind of specialized datastructures; no one type of tree >> solves all tree-related problems suitably well. >> >> I think probably the most common need for a tree is implementing a >> cache, but most times you're tempted to sort inside a loop you're >> better off with a tree. >> >> I've put some time into python trees; most of them are on pypi and at: >> http://stromberg.dnsalias.org/~dstromberg/datastructures/ >> and: >> http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/ >> >> HTH >> > > I don't know if you've seen this http://kmike.ru/python-data-structures/ but > maybe of interest. I've seen it. It's a nice page. I attempted to get my treap port in there since it has a Cython version, but it didn't seem to take. I've mostly focused on pure python that runs on CPython 2.x, CPython 3.x, Pypy, Pypy3 and Jython. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 20/01/2015 00:49, Dan Stromberg wrote: On Mon, Jan 19, 2015 at 2:06 PM, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Trees are kind of specialized datastructures; no one type of tree solves all tree-related problems suitably well. I think probably the most common need for a tree is implementing a cache, but most times you're tempted to sort inside a loop you're better off with a tree. I've put some time into python trees; most of them are on pypi and at: http://stromberg.dnsalias.org/~dstromberg/datastructures/ and: http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/ HTH I don't know if you've seen this http://kmike.ru/python-data-structures/ but maybe of interest. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Mon, Jan 19, 2015 at 2:06 PM, Zachary Gilmartin wrote: > Why aren't there trees in the python standard library? Trees are kind of specialized datastructures; no one type of tree solves all tree-related problems suitably well. I think probably the most common need for a tree is implementing a cache, but most times you're tempted to sort inside a loop you're better off with a tree. I've put some time into python trees; most of them are on pypi and at: http://stromberg.dnsalias.org/~dstromberg/datastructures/ and: http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/ HTH -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
In article , zacharygilmar...@gmail.com says... > > Why aren't there trees in the python standard library? I don't know much about python development process and strategies, but I suspect it shouldn't be much different from any other language I know of. So here's my tentative answer: Once general purpose programming languages become established, the STL maintainers tend to greatly decrease additions to the standard library, except when this is required to support new language features. Most of development on the STL shifts to code maintenance in order to improve the quality of the code (usually to address memory usage and performance concerns) and solve any existing bugs on the STL. Instead the language maintainers start to rely on third-party libraries as a continuation of the effort to extend the programming language further. Any new additions to the STL are carefully pondered. The reason is twofold: 1) Just like with the matter of data structures, many additions are implementation-contentious. Trees, for instance, can be implemented in any number of ways, some with an emphasis on performance, others on memory usage. The decision of which implementation to choose isn't easy. And if users can already choose different types of implementations from the external libraries, then this is is probably motivation enough to delay the decision for another day. 2) A standard library should focus first and foremost on support of the language features. If for some reason this takes time away from adding new entries into the STL, that's fine. There's also the problem of how one should look at a standard library. Some maintainers don't look very well at the idea of a monolithic approach, while others, like Guido, like to think of a "batteries- included" programming language, indicating a desire to build a large STL. And this is why perhaps your question arises. But "batteries included" doesn't mean build a "Total Library". That would be a vain attempt for any general purpose language. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 2015-01-19 16:19, Michael Torrie wrote: > On 01/19/2015 04:08 PM, Steven D'Aprano wrote: > > Zachary Gilmartin wrote: > >> Why aren't there trees in the python standard library? > > > > Possibly because they aren't needed? Under what circumstances > > would you use a tree instead of a list or a dict or combination > > of both? While not an abundance of times, I've had a plurality of occasions when I've wanted characteristics of a red/black tree where I wanted O(log n) insertion/deletion/initial-access and O(1) access to neighbors. > > Also, what sort of tree? Binary tree? Binary search tree? > > Red/black tree? AVL tree? Splay tree? B-tree? T-tree? Scapegoat > > tree? General n-ary tree? Every possible type of tree yet > > invented? > > Don't forget left-child,right-sibling trees. > > As I go through your list of trees, I can't find any tree type that > cannot be easily and efficiently constructed with lists, possibly > with dicts. While the data-structures can easily be composed out of lists/dicts, the algorithms that go along with them (such as red/black trees with their insertion/deletion gymnastics) would be nice to have in the stdlib so they wouldn't have to be reimplemented (or sought out and downloaded, and added to the configuration/distribution) every time someone wanted that particular tree's characteristics. Much of that could be addressed with a library of algorithms much like heapq operates on a list. -tkc -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Mon, Jan 19, 2015 at 3:08 PM, Steven D'Aprano wrote: > Zachary Gilmartin wrote: > >> Why aren't there trees in the python standard library? > > Possibly because they aren't needed? Under what circumstances would you use > a tree instead of a list or a dict or combination of both? > > That's not a rhetorical question. I am genuinely curious, what task do you > have that you think must be solved by a tree? In general, any time you want to maintain a sorted list or mapping, balanced search tree structures come in handy. Here's an example task: suppose you want to represent a calendar, where timeslots can be reserved for something. Calendar events are not allowed to intersect. The most important query is: What events are there that intersect with the timespan between datetimes d1 and d2? (To draw a daily agenda, figure out if you should display an alert to the user that an event is ongoing or imminent, etc.) You also want to be able to add a new event to the calendar, that takes place between d1 and d2, and to remove a event. I leave it to the reader to implement this using a sorted map. (hint: sort by start.) This maybe seems contrived, but I've used this exact datatype, or a remarkably similar one, in a few different circumstances: sequenced actions of characters in a strategy game, animation, motion planning... There are a few possible implementations using Python data structures. You can do it using a linear scan, which gets a little slow pretty quickly. You can make insertion slow (usually OK) by sorting on insertion, but if you ever forget to resort your list you will get a subtle bug you might not notice for a while. And so on. It's better in every way to use the third-party blist module, so why bother? -- Devin -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 01/19/2015 04:08 PM, Steven D'Aprano wrote: > Zachary Gilmartin wrote: > >> Why aren't there trees in the python standard library? > > Possibly because they aren't needed? Under what circumstances would you use > a tree instead of a list or a dict or combination of both? > > That's not a rhetorical question. I am genuinely curious, what task do you > have that you think must be solved by a tree? > > Also, what sort of tree? Binary tree? Binary search tree? Red/black tree? > AVL tree? Splay tree? B-tree? T-tree? Scapegoat tree? General n-ary tree? > Every possible type of tree yet invented? Don't forget left-child,right-sibling trees. As I go through your list of trees, I can't find any tree type that cannot be easily and efficiently constructed with lists, possibly with dicts. -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Zachary Gilmartin wrote: > Why aren't there trees in the python standard library? Possibly because they aren't needed? Under what circumstances would you use a tree instead of a list or a dict or combination of both? That's not a rhetorical question. I am genuinely curious, what task do you have that you think must be solved by a tree? Also, what sort of tree? Binary tree? Binary search tree? Red/black tree? AVL tree? Splay tree? B-tree? T-tree? Scapegoat tree? General n-ary tree? Every possible type of tree yet invented? -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On 19/01/2015 22:06, Zachary Gilmartin wrote: Why aren't there trees in the python standard library? Probably because you'd never get agreement as to which specific tree and which specific implementation was the most suitable for inclusion. -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
On Tue, Jan 20, 2015 at 9:16 AM, Ben Finney wrote: > If you're asking because you think all data structures magically appear > in the standard library by wishing it so, I think you over-estimate the > powers of the standard library maintainers. Oh come on Ben. Guido has a time machine; TimSort is pure magic coalesced into code form; and there's an army of buildbots standing by for every change that gets made. How can anyone over-estimate the powers of python-dev?! ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: Trees
Zachary Gilmartin writes: > Why aren't there trees in the python standard library? What sort of answer are you looking for? There are many ways that question could be intended. If you're asking about what could be keeping a particular tree implementation out of the standard library: that depends on what particular implementations you have in mind. Are there any which exist that you think belong in the standard library? If you're asking about some policy that prevents any such inclusion, I'm not aware of such a policy. If you're asking because you think all data structures magically appear in the standard library by wishing it so, I think you over-estimate the powers of the standard library maintainers. If you're asking something else, you'll need to be more explicit. -- \“Every sentence I utter must be understood not as an | `\ affirmation, but as a question.” —Niels Bohr | _o__) | Ben Finney -- https://mail.python.org/mailman/listinfo/python-list
Re: trees, iterations and adding leaves
At Sunday 31/12/2006 14:25, vertigo wrote:
I use nltk package - but it should not matter here.
Yes, it does. The framework should provide some form of tree traversal.
So i wanted to 'travel thru my tree' to last node which should be changed:
>>> tree6 = Tree('main', ['sub1', 'sub2'])
>>> subtree = tree6[0]
>>> subtree
'sub1'
>>> subtree = Tree('newsub',[])
>>> subtree
('newsub': )
>>> tree6
('main': 'sub1' 'sub2')
The problem is that subtree is some kind of a new variable (not pointer)
so changing it i will not alter tree6.
This, yes, is a general Python question. When you bind something to
the name "subtree", it doesn't matter what were "subtree" pointing to
before. Read http://effbot.org/zone/python-objects.htm
How to alter tree6 while
'travelling along it's nodes',
without messy referencing as tree6[0][1][0][1][1][1][0].. ?
Without any further knowledge of the Tree objects, you could do
something like this:
def traverse_tree(tree, *ids):
result = tree
while ids:
key = ids.pop(0)
tree = tree[key]
return tree
and say: traverse_tree(tree6, 0, 1, 0, 1, 1, 1, 0) or
traverse_tree(tree6, *[0,1,0,1,1,1,0]) or traverse_tree(tree6,
*[0,1,0,1,1])[0] = another_object
--
Gabriel Genellina
Softlab SRL
__
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas
--
http://mail.python.org/mailman/listinfo/python-list
Re: trees
John Nagle wrote: >SpeedTree, of course. > > http://www.speedtree.com > >They have great downloadable demos. And how do you distribute the code in a python program? Is there a wrapper for an available static library or do I have to compile the speedtree source when running the python program? :) M -- >From the homepage: What parts of SpeedTree can I distribute with my game? Before any sort of distribution, a full license of SpeedTree must be purchased. Following this, the SpeedTreeRT library must be fully integrated with your game before distribution. This means that either a static library is used or the source code must be built in (no DLLs may be distributed). No source code from the SDK can be distributed, with some exceptions for modified wrapper classes from the samples (contact [EMAIL PROTECTED] for verification). -- http://mail.python.org/mailman/listinfo/python-list
Re: trees
Raymond Hettinger a écrit : > vertigo wrote: > >>What library/functions/classes could i use to create trees ? > > > Start with random.seed, login as root, use svn to download the trunk > and branches, when Spring arrives, the leaves will fill-in ;-) keyboard !-) -- http://mail.python.org/mailman/listinfo/python-list
Re: trees
vertigo wrote: > What library/functions/classes could i use to create trees ? Start with random.seed, login as root, use svn to download the trunk and branches, when Spring arrives, the leaves will fill-in ;-) Or just use lists as Fredrik suggested. Or look at an example in the cookbook: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/201423 Raymond -- http://mail.python.org/mailman/listinfo/python-list
Re: trees
You could use ElementTree for XML. Or just use nested dictionaries. -T John Nagle wrote: > Delaney, Timothy (Tim) wrote: > > vertigo wrote: > > > > > >>Hello > >> > >>What library/functions/classes could i use to create trees ? > > SpeedTree, of course. > > http://www.speedtree.com > > They have great downloadable demos. > > John Nagle -- http://mail.python.org/mailman/listinfo/python-list
Re: trees
Delaney, Timothy (Tim) wrote: > vertigo wrote: > > >>Hello >> >>What library/functions/classes could i use to create trees ? SpeedTree, of course. http://www.speedtree.com They have great downloadable demos. John Nagle -- http://mail.python.org/mailman/listinfo/python-list
RE: trees
vertigo wrote: > Hello > > What library/functions/classes could i use to create trees ? I would suggest either a horticultural or religious class. I'm sure that any library will contain functional texts on both. Or you could just read the following: http://www.catb.org/~esr/faqs/smart-questions.html Tim Delaney -- http://mail.python.org/mailman/listinfo/python-list
Re: trees
vertigo wrote: > What library/functions/classes could i use to create trees ? what kind of trees? using lists, tuples, or a class with child pointers is so extremely simple so it has to be something else you're after... -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
> Writing a *simple* node class is easy, but a full-featured one that > supports things like comparison and easy iteration is a bit more work. So > various people write partial implementations with only the features they > need, and they all end up being incompatible. So beyond being able to use > it, the other thing is that having an implementation in the standard > library acts as a de facto interface standard, making it easier to write > common code to operate on tree structures. Hm. I disagree on that. Some things make only sense for binary trees, others need explicit uplinking to the parent node and so on. Some want accessor methods, others have certain operator overloadings used for a specific functionality. So in the end, it either becomes a monstrosity or is again not usable. But that's only my HO. > All it would take to make it happen is a PEP, an implementation and a > champion with some persuasive ability :) Go wild :) -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
Alex Le Dain <[EMAIL PROTECTED]> writes: >Is there a generic "tree" module that can enable me to sort and use >trees (and nodes). Basically having methods such as .AddNode(), >.GetAllChildren(), .FindNode() etc. http://newcenturycomputers.net/projects/rbtree.html might do most of what you want. Eddie -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
Alex Le Dain said unto the world upon 2005-02-27 19:54: > Would this be for a GUI toolkit or maybe using a standard > class scheme? Sorry, yes I should have been more specific. I meant a non-GUI, standard class scheme. I want to use the scheme to hold a structure in memory and retrieve/add information to it. I've had a couple of goes myself but get a bit confuesd about whether I should use recursion to be able to get the children (and all "sub"-children) of a/the parent. cheers, Alex. Hi Alex, I've been working on a set of tools for dealing with a tree structure. I am no python expert -- in fact, the program I am working on is my first serious us of classes. Anyway, though I've not been following your thread, I also think that perhaps you might find the code I have of some use. Use caution though; newbie code below :-) I am working with a data format from a shareware application that puts the tree in a flat text file, where each node has a header section, including a unique node id and a level indicator. (Level 0 for the root, level 1 for the roots children, etc.) My code is a work in progress and not heavily tested, but it seems to work :-) I've a class Tree_file with a .nodes attribute which is a list of Node objects (in top-down tree order). It has a method: .# leading periods to preserve indentation .def update_family(self): .'''Starting from node, updates each nodes .children and descendants set.''' .for node in self.nodes: .node.get_children(self) .for node in self.nodes: .node.get_descendants() My Node class has methods giving each node object a node.id and node.level (both ints). The other relevant attributes are node.children, and node.descendants (both sets). (I've got reasons to often process just a node's children, rather than all descendants; thus, it makes sense for my program to have the two attributes.) The two relevant methods are: .def get_children(self, parent_file): .'''Sets the node's .children set attribute. . .Scans the list of Node objects in parent_file.nodes until self .node is found (by comparison of node.id attributes). Then the .capture_children flag is set to True, and, for each node exactly .one node.level deeper, that deeper node is added to the .self.children set. This goes on until the first node not below .the self node is found. .''' .capture_children = False .children = set() . .for node in parent_file.nodes: .if capture_children and not node.level > self.level: .break .if capture_children and node.level == self.level + 1: .children.add(node) .if self.id == node.id: .capture_children = True . .self.children = children and .def get_descendants(self): .'''Updates each nodes .descendants set to current value. . .Recursive call of get_descendants on a node's children, adding .all to the .descendants set (of the target node). .''' .descendants = self.children.copy() .for node in self.children: .node.get_descendants() .for n in node.descendants: .descendants.add(n) .self.descendants = descendants Anyway, all caveats notwithstanding, I hope that is of some use to you. Best, Brian vdB -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
> Would this be for a GUI toolkit or maybe using a standard > class scheme? Sorry, yes I should have been more specific. I meant a non-GUI, standard class scheme. I want to use the scheme to hold a structure in memory and retrieve/add information to it. I've had a couple of goes myself but get a bit confuesd about whether I should use recursion to be able to get the children (and all "sub"-children) of a/the parent. cheers, Alex. -- Poseidon Scientific Instruments Pty Ltd 1/95 Queen Victoria St FREMANTLE WA, AUSTRALIA Ph: +61 8 9430 6639 Fx: +61 8 9335 4650 Website: www.psi.com.au PSI, an ISO-9001 Company CONFIDENTIALITY: The contents of this email (and any attachments) are confidential and may contain proprietary and/or copyright material of Poseidon Scientific Instruments Pty Ltd (PSI) or third parties. You may only reproduce or distribute the material if you are expressly authorised to do so. If you are not the intended recipient, any use, disclosure or copying of this email (and any attachments) is unauthorised. If you have received this email in error, please immediately delete it and any copies of it from your system and notify PSI by return email to sender or by telephone on +61 (08) 9430 6639. DISCLAIMER: You may only rely on electronically transmitted documents when: (a) those documents are confirmed by original documents signed by an authorised employee of PSI; and/or (b) the document has been confirmed and checked against a hard copy of that document provided by PSI. VIRUSES: PSI does not represent or warrant that files attached to this e-mail are free from computer viruses or other defects. Any attached files are provided, and may only be used, on the basis that the user assumes all responsibility for any loss or damage resulting directly or indirectly from such use. PSI's liability is limited in any event to either the re-supply of the attached files or the cost of having the attached files re-supplied. -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
Diez B. Roggisch wrote: Or writing a Node-class is also so straightforward that few care about them being part of the core: Writing a *simple* node class is easy, but a full-featured one that supports things like comparison and easy iteration is a bit more work. So various people write partial implementations with only the features they need, and they all end up being incompatible. So beyond being able to use it, the other thing is that having an implementation in the standard library acts as a de facto interface standard, making it easier to write common code to operate on tree structures. All it would take to make it happen is a PEP, an implementation and a champion with some persuasive ability :) Cheers, Nick. -- Nick Coghlan | [EMAIL PROTECTED] | Brisbane, Australia --- http://boredomandlaziness.skystorm.net -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
[Alex Le Dain] > Is there a generic "tree" module that can enable me to sort and use > trees (and nodes). Basically having methods such as .AddNode(), > .GetAllChildren(), .FindNode() etc. > Is this handled natively with any of the core modules? Using only standard Python, look at the suite of `xml...' modules. > cheers, Alex. P.S. - Your signature and company disclaimer use more than 30 lines. That's really a lot. I hope you can bring them down to reason! :-) -- François Pinard http://pinard.progiciels-bpi.ca -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
Alex Le Dain wrote:
> Is there a generic "tree" module that can enable me to sort and use
> trees (and nodes). Basically having methods such as .AddNode(),
> .GetAllChildren(), .FindNode() etc.
No. Usually, one uses the built-in python datastructures for this. E.g.
('root', [('child1', None), ('child2', None)])
Or writing a Node-class is also so straightforward that few care about them
being part of the core:
class Node(object):
def __init__(self, payload, childs=None):
self.payload = payload
self.childs = childs
def depth_first(self):
if self.childs:
for child in self.childs:
for node in child.depth_first():
yield node
yield self.payload
tree = Node('root', [Node('child1'), Node('child2')])
for n in tree.depth_first():
print n
--
Regards,
Diez B. Roggisch
--
http://mail.python.org/mailman/listinfo/python-list
Re: Trees
Alex Le Dain wrote: > Is there a generic "tree" module that can enable me to sort and use > trees (and nodes). Basically having methods such as .AddNode(), > .GetAllChildren(), .FindNode() etc. > > Is this handled natively with any of the core modules? > > cheers, Alex. > > -- > Poseidon Scientific Instruments Pty Ltd > 1/95 Queen Victoria St > FREMANTLE WA, AUSTRALIA > > Ph: +61 8 9430 6639 Fx: +61 8 9335 4650 > Website: www.psi.com.au > > PSI, an ISO-9001 Company > > CONFIDENTIALITY: The contents of this email (and any attachments) are > confidential and may contain proprietary and/or copyright material of > Poseidon Scientific Instruments Pty Ltd (PSI) or third parties. You may > only reproduce or distribute the material if you are expressly > authorised to do so. If you are not the intended recipient, any use, > disclosure or copying of this email (and any attachments) is > unauthorised. If you have received this email in error, please > immediately delete it and any copies of it from your system and notify > PSI by return email to sender or by telephone on +61 (08) 9430 6639. > > DISCLAIMER: You may only rely on electronically transmitted documents when: > (a) those documents are confirmed by original documents signed by an > authorised employee of PSI; and/or > (b) the document has been confirmed and checked against a hard copy > of that document provided by PSI. > > VIRUSES: PSI does not represent or warrant that files attached to this > e-mail are free from computer viruses or other defects. Any attached > files are provided, and may only be used, on the basis that the user > assumes all responsibility for any loss or damage resulting directly or > indirectly from such use. PSI's liability is limited in any event to > either the re-supply of the attached files or the cost of having the > attached files re-supplied. Long sig !! :-) Try elemtree by the F-bot Regards, Fuzzy http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Trees
Would this be for a GUI toolkit or maybe using a standard class scheme? -- http://mail.python.org/mailman/listinfo/python-list
