On 7/26/06, Mark Winterhalder <[EMAIL PROTECTED]> wrote:
I still don't understand why Danny got contrary results, but I like
recursion better so let's just leave it like that :)
OK, let's not -- I had another look, and found a ! was missing in the
recursive method. I've updated the test class below, test at
<http://www.snafoo.org/tmp/flatten.swf>, with the length of the result
now being traced as a simple check.
Iteration now is faster, confirming Danny's results.
As a note on the side, the recursion can be accelerated a bit by
storing the value of the array in a variable instead of looking it up
twice in each iteration. You can compare it here:
<http://www.snafoo.org/tmp/flatten2.swf>. Maybe I should have used
more descriptive names, but 'flatten' here means the original and
'flatten2' means it's like this:
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;
};
Anyway, iteration is still slightly faster -- this is just a general
hint. I found this after making the other test and am already late, I
might make one with iteration and both recursions later to make it
easier to compare.
Mark
class TestArray extends Array {
public static var testarray : Array;
public static function main () : Void {
var ta = TestArray.testarray = TestArray.randomArray( 100000 );
_root.createTextField( "tf", 1, 0, 0, 1024, 768 );
var cntr = 0;
_root.onEnterFrame = function () {
if( cntr++ > 30 ) {
var n = (cntr % 2);
var res;
var start = getTimer();
if( n ) {
res = ta.flatten2();
} else {
res = ta.flatten();
}
var dur = getTimer() - start;
_root.tf.text += "\n" + res.length + ", " + (n ?
"flatten2" :
"flatten") + ": " + dur;
}
if( cntr > 70 ) {
delete this.onEnterFrame;
}
};
}
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 () : 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;
}
}
<<<
_______________________________________________
[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
