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...
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
