performance - Could I use a faster data structure than a tree for this? -


i have binary decision tree. takes inputs array of floats, , each branch node splits on input index , value taking me leaf.

i'm performing massive number of lookups on tree (about 17% of execution time according performance analysis (edit: having optimised other areas it's @ 40%)), , wondering if could/should using different data structure improve lookup speed.

some kind of hash table can't used, inputs not map directly leaf node, wondering had suggesting methods , data-structures use in place of tree (or as?) improve lookup speeds.

memory concern, less of concern speed.

code written in c#, method applied.

edit: there's bit code post, i'll give more detail tree.

the tree generated using information gain calculations, it's not 50/50 split, split value float value. single input split multiple times increasing resolution on input.

i posted question performance of iterator here:

micro optimisations iterating through tree in c#

but think might need @ data structure improve performance further.

i'm aiming performance possible here. i'm working on new method of machine learning, , tree grows using feedback loop. process i'm working on, estimate it'll running several months, few % saving here , there massive. ultimate goal speed without using memory.

if understand correctly, have floating point ranges have mapped decision. this:

       x <= 0.0      : decision  0.0 < x <= 0.5      : decision b  0.5 < x <= 0.6      : decision c  0.6 < x             : decision d

a binary tree pretty way handle that. long tree balanced , input values evenly distributed across ranges, can expect o(log2 n) comparisons, n number of possible decisions.

if tree not balanced, doing far more comparisons necessary. in worst case: o(n). @ trees , see how deep are. if same tree used again , again, cost spent rebalancing once may amortized on many lookups.

if input values not evenly distributed (and know ahead of time), might want special-case order of comparisons common cases detected early. can manipulating tree or adding special cases in code before checking tree.

if you've exhausted algorithmic improvements , still need optimize, might data structure better locality general binary tree. example, put partition boundaries contiguous array , perform binary search on it. (and, if array isn't long, might try linear search on array may friendlier cache , branch prediction.)

lastly, i'd consider building coarse index gives headstart tree (or array). example, use few of significant bits of input value index , see if can cut off first few layers of tree. may more might imagine, skipped comparisons have low chance of getting correct branch predictions.


Comments

Post a Comment

Popular posts from this blog

php - cannot display multiple markers in google maps v3 from traceroute result -

i'm newbie in php mysql , google maps v3. have problems in google maps v3. made traceroute web based , map traceroute's result in google maps v3 final project of college education. have try many tutorials didn't work. have tried tutorials in forum nothing worked. problem cannot display multiple markers got location data database. maybe because i'm newbie , not know how do. confuse looping show markers. here code <?php error_reporting(e_all ^ (e_notice)); ini_set('max_execution_time', 360); $enable_log_user = false; global $ip, $host_name, $host_ip; $host = @$_post['host']; $trace = @$_post['trace']; $self = $_server['php_self']; include("phpsqlajax_dbinfo.php"); $connection = mysql_connect ('127.0.0.1', $username, $password); if (!$connection) { die('not connected : ' . mysql_error());} $db_selected = mysql_select_db($database, $connection); if (!$db_selected) { die ('can\'t use db : ...
Read more

c# - DetailsView in ASP.Net - How to add another column on the side/add a control in each row? -

i have detailsview control on page used edit various fields of record, works in respect. i looking way add 1 column (and if works, why not more) right, absolutely read-only, show same fields of record comparison purposes. i aware there no obvious way such thing out of box detailsview . have looked other controls (transposed gridview , recommended formview , listview ), nothing satisfies. have special data binding setup using detailsview , can't out of without losing features. anyone on how "hack in" additional columns (for display only) on detailsview ? the solution have now, use second detailsview , visible set false in aspx. in code, make sure databind hidden detailsview hosts data third column first, initial detailsview named itemdetails . and in item created event, pass third column html rendering of hidden controls (in last code block) : protected void itemdetails_itemcreated(object sender, eventargs e) { if (dataite...
Read more

javascript - firefox memory leak -

i have following script (i use raphaeljs also) draws circle, waits 1 second, draws circle again, etc (you can copy paste - functional, need include raphael raphaeljs.com): <div id="holder"> </div> <script src="raphael.js" type="text/javascript"></script> <script> var paper = raphael(10, 50, 320, 200); var rad = math.pi / 180; var finangle = 0; function sector(cx, cy, r, startangle, endangle, params) { var x1 = cx + r * math.cos(-startangle * rad), x2 = cx + r * math.cos(-endangle * rad), y1 = cy + r * math.sin(-startangle * rad), y2 = cy + r * math.sin(-endangle * rad); return ["m", cx, cy, "l", x1, y1, "a", r, r, 0, +(endangle - startangle > 180), 0, x2, y2]; } var path = sector(100,100,50,0,180); var arc = paper.path(path); function draw() { path = sector(100,100,50,0,finangle); ...
Read more