Databases
StackOverflow2013
Postsdbo
POCould I use a faster data structure than a tree for this?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCould I use a faster data structure than a tree for this?
    primarykey
    data
    text
    <p>I have a binary decision tree. It takes inputs as an array of floats, and each branch node splits on an input index and value eventually taking me to a leaf.</p> <p>I'm performing a massive number of lookups on this tree (about 17% of execution time according to performance analysis (Edit: Having optimised other areas it's now at almost 40%)), and am wondering if I could/should be using a different data structure to improve lookup speed.</p> <p>Some kind of hash table can't be used, as inputs do not map directly to a leaf node, but I was wondering is anyone had any suggesting as to methods and data-structures I could use in place of the tree (or as well as?) to improve lookup speeds.</p> <p>Memory is a concern, but less of a concern than speed.</p> <p>Code is currently written in C#, but obviously any method could be applied.</p> <p>Edit: There's a bit too much code to post, but I'll give more detail about the tree.</p> <p>The tree is generated using information gain calculations, it's not always a 50/50 split, the split value could be any float value. A single input could also be split multiple times increasing the resolution on that input.</p> <p>I posted a question about performance of the iterator here:</p> <p><a href="https://stackoverflow.com/questions/16416084/micro-optimisations-iterating-through-a-tree-in-c-sharp">Micro optimisations iterating through a tree in C#</a></p> <p>But I think I might need to look at the data structure itself to improve performance further.</p> <p>I'm aiming for as much performance as possible here. I'm working on a new method of machine learning, and the tree grows itself using a feedback loop. For the process I'm working on, I estimate it'll be running for several months, so a few % saving here and there is massive. The ultimate goal is speed without using too much memory.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USWill Calderwood
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCould I use a faster data structure than a tree for this?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POCould I use a faster data structure than a tree for this?
      1. USRich
      1. VTFavorite
    3. VO
      singulars
      1. POCould I use a faster data structure than a tree for this?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COdictionary with ordering which can be a map
      singulars
      1. POCould I use a faster data structure than a tree for this?
      1. USRyan Fung
    2. COYou say you have a binary tree and the input at each node is a float - is your choice of child node based on `input < 0.5` or is there something more complex going on? Can you post some code? Also: 17% of execution time isn't very contextual - that could be very fast! Do you have a target you're aiming for, or more detail on the profiling that you can share?
      singulars
      1. POCould I use a faster data structure than a tree for this?
      1. USDan Puzey
    3. COThanks Dan, I've added some more detail about the tree and targets.
      singulars
      1. POCould I use a faster data structure than a tree for this?
      1. USWill Calderwood
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload