Data structures for tree traversals?

[Carl]

Dear friends,

What are the best options for implementing fast and efficient trees in
Python?

The typical trees that I'm thinking of are those used by the finance
industry to price different kinds of derivatives (ie forward simulation of
prices/rates in binominal/trinominal trees and backward induction to price
final claims).

Intuitively, dictionaries seem to be ideal candidates for accessing objects
at nodes and traversing the tree. Am I right or are there better choices?
Are lists better? Has Numerical Python speed-efficient methods that are to
be preferred in comparison with lists ad dictionaries?

Carl

 

[Miki Tebeka]

Hello Carl,

What are the best options for implementing fast and efficient trees in
Python?

The answer varies depending on what will the trees be used for.

Intuitively, dictionaries seem to be ideal candidates for accessing objects
at nodes and traversing the tree. Am I right or are there better choices?
Are lists better? Has Numerical Python speed-efficient methods that are to
be preferred in comparison with lists ad dictionaries?

There's http://www.python.org/doc/essays/graphs.html by the BDFL.

I find that defining a little class:
class Tree:
def __init__(self, value, children=None):
self.value = value
if children is None:
self.children = []
else:
self.children = children

and subclassing each specific child.
Combined with a visitor pattern is usually the best way.

Go for the usual approach:
o Make it work
o Make it right
o Make it fast (only if you need)

HTH.

Bye.