A tree data structure for Python
Hello, I would love to see a tree data structure out of the box for python. I'm thinking of a n-ary or multiway tree. It's a useful data structure to model things that are difficult to model with lists, dicts, etc. Recursion can be avoided by using a stack for traversal.
On Feb 17, 2016, at 09:01, Stephan Foley <foley12723@gmail.com> wrote:
Do you want it to be fixed-n-ary or arbitrary branching? Values in all nodes, or only the leaves? Does it need O(1) size or depth? Single-linked, back-pointers, or threaded? Mutable or copying? Are trees and nodes separate types (and, if so, is a subtree a tree in its own right)? What algorithms do you need besides BFS and DFS (pre-, in-, and post-order) visits? All of these are really easy to build a class for--or to just represent with a list of lists (or a tuple of tuples)--but coming up with a class that can handle all of the different possibilities in a single type is a lot harder. What might be more useful is to write generic algorithms. Then you can implement very different kinds of trees, and even use existing tree types, with a single implementation of the algorithm: "for node in bfs(root, itemgetter(1)):" for a simple "(value, (child, ...))" recursive tuple, "for div in bfs(h.body, lambda node: node.find_children('div'))" for an HTML document, etc. (I'd bet this already exists on PyPI.)
Hello and thanks for the reply. On Wed, Feb 17, 2016 at 12:30 PM, Andrew Barnert <abarnert@yahoo.com> wrote:
Do you want it to be fixed-n-ary or arbitrary branching? Values in all nodes, or only the leaves? Does it need O(1) size or depth? Single-linked, back-pointers, or threaded? Mutable or copying? Are trees and nodes separate types (and, if so, is a subtree a tree in its own right)? What algorithms do you need besides BFS and DFS (pre-, in-, and post-order) visits?
Yes, I'm looking online and neither C++ nor Java have a tree class for the same reason. Rolling your own tree is very easy, but developing something useful for everyone can involve a lot of overhead. But, to answer your questions, a lightweight tree that could represent either a file system or configuration data. Arbitrary branching. Values in all nodes. Pointers to first child, next sibling and parent. Based on a node class. Pre-order, post-order and level-order traversal.
On Feb 17, 2016, at 09:52, Stephan Foley <foley12723@gmail.com> wrote:
It's not so much the overhead, as the design decisions. You need parent pointers; I not only don't need them, but need subtrees that don't keep their parents alive. I need threading, you don't want it, and don't want on do the log N work on each update to fix up the threads you're never going to use but the type demands them. You want first child and next sibling, I want all children. And so on. In most of there cases, there's no structure or API that's going to make us both happy. That's why a functional design works much better than an OO design for this particular problem. It's hard to explain in text, but easy to show in code, so check https://github.com/abarnert/treestuff
Hi Andrew, On Wed, Feb 17, 2016 at 2:51 PM, Andrew Barnert <abarnert@yahoo.com> wrote:
It's not so much the overhead, as the design decisions. You need parent pointers; I not only don't need them, but need subtrees that don't keep their parents alive. I need threading, you don't want it, and don't want on do the log N work on each update to fix up the threads you're never going to use but the type demands them. You want first child and next sibling, I want all children. And so on. In most of there cases, there's no structure or API that's going to make us both happy.
I get what you're saying, but something simple like the C++ Boost Property Tree might be general enough to be useful: http://www.boost.org/doc/libs/1_60_0/doc/html/property_tree.html#property_tr...
That's why a functional design works much better than an OO design for this particular problem. It's hard to explain in text, but easy to show in code, so check https://github.com/abarnert/treestuff
Ahhh....functional design....I'm going to hit my Scheme books :-) In general, I only use OO for data and try to make everything else functions. Classes work nicely to hold the pointers. Really, you can also program a tree in a memory buffer with integer pointers as offsets.
On Wed, Feb 17, 2016 at 9:01 AM, Stephan Foley <foley12723@gmail.com> wrote:
Hello, I would love to see a tree data structure out of the box for python. I'm thinking of a n-ary or multiway tree.
Reminds me of the "one-line tree in Python" hack: https://gist.github.com/hrldcpr/2012250 Here's the gist of it: from collections import defaultdict def tree(): return defaultdict(tree) It's almost too flexible but writing methods to traverse is relatively easy. Grant
On 17/02/2016 17:01, Stephan Foley wrote:
It won't happen as there are far too many conflicting options, see for example the list here http://kmike.ru/python-data-structures/ -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence
How about a toolbox of primitives to build the structure needed? With say the top-five most common high-level combinations included? Perhaps something as flexible as the logging module, with a modern design take. Sounds like a good package to add to PyPI until it matures, if something similar doesn't already exist. -Mike On 2016-02-17 12:48, Mark Lawrence wrote:
It won't happen as there are far too many conflicting options, see for example the list here http://kmike.ru/python-data-structures/
Hi Mark, On Wed, Feb 17, 2016 at 3:48 PM, Mark Lawrence <breamoreboy@yahoo.co.uk> wrote:
It won't happen as there are far too many conflicting options, see for example the list here http://kmike.ru/python-data-structures/
Cool site...I once programmed a trie in Python. As for the trees, my request is for a very specific tree...a n-ary or multiway tree. The other trees listed, like red-black and binary, are for sorting and searching efficiently. A Patricia-Tree is actually a trie. BTrees are for external storage.
Stephan, you can't just request a new stdlib module and expect someone to make one for you. Is there an existing PyPI package that you think is mature enough to add to the stdlib? Then say so. If you want to write one yourself, go right ahead. But this thread has run its course. On Thu, Feb 18, 2016 at 6:01 PM, Stephan Foley <foley12723@gmail.com> wrote:
-- --Guido van Rossum (python.org/~guido)
On Feb 17, 2016, at 09:01, Stephan Foley <foley12723@gmail.com> wrote:
Do you want it to be fixed-n-ary or arbitrary branching? Values in all nodes, or only the leaves? Does it need O(1) size or depth? Single-linked, back-pointers, or threaded? Mutable or copying? Are trees and nodes separate types (and, if so, is a subtree a tree in its own right)? What algorithms do you need besides BFS and DFS (pre-, in-, and post-order) visits? All of these are really easy to build a class for--or to just represent with a list of lists (or a tuple of tuples)--but coming up with a class that can handle all of the different possibilities in a single type is a lot harder. What might be more useful is to write generic algorithms. Then you can implement very different kinds of trees, and even use existing tree types, with a single implementation of the algorithm: "for node in bfs(root, itemgetter(1)):" for a simple "(value, (child, ...))" recursive tuple, "for div in bfs(h.body, lambda node: node.find_children('div'))" for an HTML document, etc. (I'd bet this already exists on PyPI.)
Hello and thanks for the reply. On Wed, Feb 17, 2016 at 12:30 PM, Andrew Barnert <abarnert@yahoo.com> wrote:
Do you want it to be fixed-n-ary or arbitrary branching? Values in all nodes, or only the leaves? Does it need O(1) size or depth? Single-linked, back-pointers, or threaded? Mutable or copying? Are trees and nodes separate types (and, if so, is a subtree a tree in its own right)? What algorithms do you need besides BFS and DFS (pre-, in-, and post-order) visits?
Yes, I'm looking online and neither C++ nor Java have a tree class for the same reason. Rolling your own tree is very easy, but developing something useful for everyone can involve a lot of overhead. But, to answer your questions, a lightweight tree that could represent either a file system or configuration data. Arbitrary branching. Values in all nodes. Pointers to first child, next sibling and parent. Based on a node class. Pre-order, post-order and level-order traversal.
On Feb 17, 2016, at 09:52, Stephan Foley <foley12723@gmail.com> wrote:
It's not so much the overhead, as the design decisions. You need parent pointers; I not only don't need them, but need subtrees that don't keep their parents alive. I need threading, you don't want it, and don't want on do the log N work on each update to fix up the threads you're never going to use but the type demands them. You want first child and next sibling, I want all children. And so on. In most of there cases, there's no structure or API that's going to make us both happy. That's why a functional design works much better than an OO design for this particular problem. It's hard to explain in text, but easy to show in code, so check https://github.com/abarnert/treestuff
Hi Andrew, On Wed, Feb 17, 2016 at 2:51 PM, Andrew Barnert <abarnert@yahoo.com> wrote:
It's not so much the overhead, as the design decisions. You need parent pointers; I not only don't need them, but need subtrees that don't keep their parents alive. I need threading, you don't want it, and don't want on do the log N work on each update to fix up the threads you're never going to use but the type demands them. You want first child and next sibling, I want all children. And so on. In most of there cases, there's no structure or API that's going to make us both happy.
I get what you're saying, but something simple like the C++ Boost Property Tree might be general enough to be useful: http://www.boost.org/doc/libs/1_60_0/doc/html/property_tree.html#property_tr...
That's why a functional design works much better than an OO design for this particular problem. It's hard to explain in text, but easy to show in code, so check https://github.com/abarnert/treestuff
Ahhh....functional design....I'm going to hit my Scheme books :-) In general, I only use OO for data and try to make everything else functions. Classes work nicely to hold the pointers. Really, you can also program a tree in a memory buffer with integer pointers as offsets.
On Wed, Feb 17, 2016 at 9:01 AM, Stephan Foley <foley12723@gmail.com> wrote:
Hello, I would love to see a tree data structure out of the box for python. I'm thinking of a n-ary or multiway tree.
Reminds me of the "one-line tree in Python" hack: https://gist.github.com/hrldcpr/2012250 Here's the gist of it: from collections import defaultdict def tree(): return defaultdict(tree) It's almost too flexible but writing methods to traverse is relatively easy. Grant
On 17/02/2016 17:01, Stephan Foley wrote:
It won't happen as there are far too many conflicting options, see for example the list here http://kmike.ru/python-data-structures/ -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence
How about a toolbox of primitives to build the structure needed? With say the top-five most common high-level combinations included? Perhaps something as flexible as the logging module, with a modern design take. Sounds like a good package to add to PyPI until it matures, if something similar doesn't already exist. -Mike On 2016-02-17 12:48, Mark Lawrence wrote:
It won't happen as there are far too many conflicting options, see for example the list here http://kmike.ru/python-data-structures/
Hi Mark, On Wed, Feb 17, 2016 at 3:48 PM, Mark Lawrence <breamoreboy@yahoo.co.uk> wrote:
It won't happen as there are far too many conflicting options, see for example the list here http://kmike.ru/python-data-structures/
Cool site...I once programmed a trie in Python. As for the trees, my request is for a very specific tree...a n-ary or multiway tree. The other trees listed, like red-black and binary, are for sorting and searching efficiently. A Patricia-Tree is actually a trie. BTrees are for external storage.
Stephan, you can't just request a new stdlib module and expect someone to make one for you. Is there an existing PyPI package that you think is mature enough to add to the stdlib? Then say so. If you want to write one yourself, go right ahead. But this thread has run its course. On Thu, Feb 18, 2016 at 6:01 PM, Stephan Foley <foley12723@gmail.com> wrote:
-- --Guido van Rossum (python.org/~guido)
participants (6)
-
Andrew Barnert -
Grant Jenks -
Guido van Rossum -
Mark Lawrence -
Mike Miller -
Stephan Foley