RE: [PHP] Performance issues and trees

Sven Riedel wrote: > letters "0" and "1". My tree-traversal algorithm looks like this: > > $bit_array = str_split( $bitstring ); > $tree_climber = $tree; // assign tree-climber to the > tree root > > // main loop > while( !is_null( $bit = array_shift( $bit_array ) ) ) { > $tree_climber = $tree_climber[$bit]; // going down... > if( !is_array( $tree_climber ) ) { // we reached a node > process( $tree_climber ); > $tree_climber = $tree; // and back up to the root we go > } > } > > I'm seeing execution times in excess of 30 seconds for a few hundred > (~ 200 - 300 ) tree-runs (with the tree in question being of average > depth 5, translating to 1000 - 1500 assignments, which is way to slow > to be practical. And the main holdup _is_ the tree-traversal, the sum > of the process() functions is in the range of 0.3 seconds (measured > with microtime(true) ). Have you tried using a profiler on the code? APD might prove useful: http://pecl.php.net/package/apd This can show you exactly how much execution time is being spent in each function of your code, whether user-defined or built in, and can list average execution times per function, etc. Personally it's been several years since I've toyed with binary trees (my second semester of Pascal <grin>) and I can't tell for sure what's going on in what little code you posted. For example, I can't tell by what you posted if the array_shift() above is necessary. If you merely need to traverse $bit_array without actually modifying it then I suspect a simple foreach would be much faster, but I'm probably missing something... If you have the time and the inclination you may want to post a link to your actual working code...