OK, my final conclusion:
<http://www.snafoo.org/tmp/flatten.swf>
Iterative *is* faster than recursion. Run the test and examine the
test class below. (Use an empty .fla, import it, call TestArray.main()
)
Also, we learn that whenever you have to get the item at the same
position of an array twice, store it in a local variable. Plus, and
this lead to significant improvements, don't use Array.push(), but
maintain the index in a local variable.
The fastest is the "new iterative", or "flatten4" as it is called in
the class below. We're talking 25% improvement over recursion. I've
changed the original one so it stores the index and parent on a stack
instead of a property so it can be used in Steven's Array class if he
likes.
It ain't pretty to look at, but it's pretty fast.
Mark
class TestArray extends Array {
public static var testarray : Array;
public static function main () : Void {
var ta = TestArray.testarray = TestArray.randomArray( 100000 );
var reference = ta.flatten().length;
_root.createTextField( "tf", 1, 0, 0, 1024, 768 );
_root.tf.text = "testing... will take a while, be patient.";
var cntr = 0;
var results = [ [], [], [], [] ];
var labels = [ "recursive", "new recursive", "iterative", "new
iterative" ];
_root.onEnterFrame = function () {
if( cntr++ > 30 ) {
var n = (cntr % 4);
var res;
var start;
switch( n ) {
case 0:
start = getTimer();
res = ta.flatten();
break;
case 1:
start = getTimer();
res = ta.flatten2();
break;
case 2:
start = getTimer();
res = ta.flatten3();
break;
case 3:
start = getTimer();
res = ta.flatten4();
break;
}
var dur = getTimer() - start;
results[ n ].push( dur );
if( res.length != reference ) {
_root.tf.text += "\ncheck " + labels[ n ] +
", gave result length
different from reference result.";
}
_root.tf.text = res.length + ", " + labels[ n ] + ":
" + dur;
}
if( cntr > 70 ) {
delete this.onEnterFrame;
var totals = [];
_root.tf.text = "The fastest results
were...\n\n";
for( var i in results ) {
var result = results[ i ];
var min = Number.MAX_VALUE;
for( var k in result ) {
min = Math.min( min, result[ k
] );
}
_root.tf.text += "\nfor " + labels[ i ] +
":\t" + min;
}
}
};
}
public static function randomArray(p) : Array {
var a = new TestArray;
for (var i = 0; i < p; i++) {
if (Math.random() * 2 < Math.random() * 5) {
a.push(i);
} else {
a.push(TestArray.randomArray(Math.ceil(
Math.random() * 3 ) ));
}
}
_root.tf.text += "length: " + a.length;
return a;
}
public function flatten (r) : Array {
if (!r) r = [];
var n = this.length;
for (var a = 0; a < n; a++) {
if ( !(this[a] instanceof Array) ) {
r.push(this[a]);
} else {
this[a].flatten(r);
}
}
return r;
};
public function flatten2 (r) : Array {
if (!r) r = [];
var n = this.length;
var foo;
for (var a = 0; a < n; a++) {
if ( !((foo = this[a]) instanceof Array) ) {
r.push(foo);
} else {
foo.flatten2(r);
}
}
return r;
};
public function flatten3 () : Array {
var outArray : Array = [];
var list = this;
list.index = 0;
var item : Object;
var index : Number;
var length : Number;
do {
index = list.index;
length = list.length;
while( index < length ) {
item = list[ index++ ];
if( item instanceof Array ) {
item.parent = list;
list.index = index;
list = item;
index = 0;
length = list.length;
} else {
outArray.push( item );
}
}
} while( list = list.parent );
return outArray;
}
public function flatten4 () : Array {
var outArray : Array = [];
var outIndex = 0;
var list = this;
list.index = 0;
var item : Object;
var index;
var length : Number;
var indices : Array = [ 0 ];
var indicesIndex = 1;
var lists : Array = [];
var listsIndex = 0;
do {
index = indices[ --indicesIndex ];
length = list.length;
while( index < length ) {
item = list[ index++ ];
if( item instanceof Array ) {
lists[ listsIndex++ ] = list;
indices[ indicesIndex++ ] = index;
list = item;
index = 0;
length = list.length;
} else {
outArray[ outIndex++ ] = item;
}
}
} while( list = lists[ --listsIndex ] );
return outArray;
}
}
<<<
_______________________________________________
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
