Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Data structures for tree traversals?

Reply
Thread Tools

Data structures for tree traversals?

 
 
Carl
Guest
Posts: n/a
 
      11-14-2004
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

 
Reply With Quote
 
 
 
 
Miki Tebeka
Guest
Posts: n/a
 
      11-14-2004
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.
--
------------------------------------------------------------------------
Miki Tebeka <(E-Mail Removed)>
http://tebeka.spymac.net
The only difference between children and adults is the price of the toys
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 2 10-31-2007 02:58 AM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 4 10-30-2007 08:21 PM
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments