Hi,
I'm currently struggleing with trees built from arrays of arrays and their
performance. During tree traversal php spends a frightening amount of time in
there, which (I guess) is due to the way the tree is constructed.
What I have is an unbalanced binary tree, the inner nodes of which are
encoded as Array( [0] -> left subtree, [1] -> right subtree )
and a string as a leaf.
Where I need to go is encoded as a binary string, consisting of the 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) ).
Is there any way to speed this up? I've already tried constructing a
lookup-table from the tree, and going through the bitstring along the lines of
// Pseudocode
while( not_done ) {
for( $i = 1; $i < $max_tree_path; ++$i ) {
$examined = substr( $bitstring, 0, $i ); // lets look at the first $i bits
if( is_set( $lut[$examined ] ) ) {
$result = $lut[$examined];
$bitstring = substr( $bitstring, $i );
break;
}
}
but this actually fares worse in terms of runtime.
I'm using php 5.0.
Regs,
Sven
--
---------------------Trigital-
Sven Riedel
. Tel: +49 511 1236364
. Fax: +49 511 1690746
. email: [EMAIL PROTECTED]
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
