Data structures for tree traversals?

Discussion in 'Python' started by Carl, Nov 14, 2004.

  1. Carl

    Carl Guest

    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
     
    Carl, Nov 14, 2004
    #1
    1. Advertising

  2. Carl

    Miki Tebeka Guest

    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 <>
    http://tebeka.spymac.net
    The only difference between children and adults is the price of the toys
     
    Miki Tebeka, Nov 14, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,129
  2. tweak
    Replies:
    14
    Views:
    2,786
    Eric Sosman
    Jun 11, 2004
  3. Alfonso Morra
    Replies:
    11
    Views:
    719
    Emmanuel Delahaye
    Sep 24, 2005
  4. sharan
    Replies:
    4
    Views:
    691
    CBFalconer
    Oct 30, 2007
  5. Santosh
    Replies:
    2
    Views:
    2,832
    Santosh
    Jan 16, 2009
Loading...

Share This Page