Re: [Flashcoders] Find item in array
OO languages are similar in many respects. Apparently, (Tip 213, Anthony Porter, The best C++ Tips Ever, McGraw Hill) when you increment 'a' and access it with ++a, you increment 'a', and use a reference to it. but with a++, you make a temporary copy of 'a' increment the original and return a copy of the temporary, not a reference it, because the temporary object is destroyed. That's the overhead. Even passing objects back from functions involve the creation of temporary objects. I am right in thinking that p code is pseudo-code and therefore does not indicate code bytes? John - Original Message - From: Steven Sacks | BLITZ [EMAIL PROTECTED] To: Flashcoders mailing list flashcoders@chattyfig.figleaf.com Sent: Wednesday, September 20, 2006 12:07 AM Subject: RE: [Flashcoders] Find item in array using a for..i..in loop will always be faster It's been proven before here on flashcoders that for in is not faster than --a -(-1) because it compiles to more lines of pcode. I guess it's time to use Flasm to bust out some pcode and post it here on the list instead of making claims based on hunches and past posts in the archives. ___ Flashcoders@chattyfig.figleaf.com 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 ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
He's right, and declaring the variable i inside of the loop rather than before actually (weirdly) runs faster. I don't know what pcode it produces, but I know CPU doesn't care about pcode. I think the only way to test speed is timing the thing. It's all very interesting, but I doubt even 10 ms of difference over 10,000 iterations could ever be noticable to the user. It certainly won't be the difference between a script timeout or not. I like the for..in for its simplicity ... also it helps avoid endless looping and other unexpected behavior if you're adding to or taking away from the array while the loop is running. I agree, AS3 rocks! I'm done with 275 ms if I can have 7 ms. Thats 39 times faster! geesh Tyler On 9/19/06, JOR [EMAIL PROTECTED] wrote: Actually, Tyler's tests proved that var a in is faster with today's player. I tried his test out myself and my results were even wider than his. I published for AS2 and ran in Flash Player 9. I was averaging roughly 265ms for var a in and 275ms for (--a -(-1)). Then I compiled for AS3 and it ran too fast for testing at 7ms for both AS3/Player 9 rocks!!! So, I added another 9 to the loop counter making it 9 iterations. Then var a in ran at 70ms, (--a -(-1)) and (a--) ran the same at 77ms. Then I added another 9 making the loops 99. var a in ran at 740ms, (--a -(-1)) ran 765ms and (a--) at 770ms. I'm satisfied that for (var a in array) is faster than while (--a -(-1)). Perhaps in the past that wasn't always the case, but with player 9 it is the case and that's what I'll be basing my decisions on. James O'Reilly http://www.jamesor.com Steven Sacks | BLITZ wrote: using a for..i..in loop will always be faster It's been proven before here on flashcoders that for in is not faster than --a -(-1) because it compiles to more lines of pcode. I guess it's time to use Flasm to bust out some pcode and post it here on the list instead of making claims based on hunches and past posts in the archives. ___ Flashcoders@chattyfig.figleaf.com 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 ___ Flashcoders@chattyfig.figleaf.com 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 ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
My original question to Jason was clarification on *why* (--i -(-1))
would run faster than (i--) as it seemed to me that two calculations per
loop would run slower than 1. Since he used an expression I've never
seen before I figured he might might know the reasoning behind the
optimization. It does in fact surprise me that this method is faster.
You mentioned the reason it ran faster was because it compiled down to
less lines of code. But we see this isn't the case. I need to find
good documentation/reference on p-code to better understand what is
going on under the hood. So far my google searches turn up nothing good
so any additional links would be appreciated.
My tests so far...
By itself, (i--) runs faster than (--i -(-1)). However, when used as
the condition for a while loop (i--) is slower. That's the part I don't
get. Why is it slower? What's different about being the condition of a
loop?
Here's my two tests. I alternated comments so that each of the four
tests ran by themselves:
//--
// (i--) vs. (--i -(-1))
// Test 1: (i--) is 448 millis faster as standalone
// Test 2: (i--) is 140 millis slower as loop conditional
//
var i,begin,end;
i = 100;
begin = getTimer();
//---
// Test 1 A
while (i) { (i--); }
end = getTimer();
trace(1A: + (end-begin));// avg 1676
//---
// Test 1 B
//while (i) { (--i -(-1)); }
//end = getTimer();
//trace(1B: + (end-begin)); // avg 2124
//---
// Test 2 A
//while (i--) {}
//end = getTimer();
//trace(2A: + (end-begin)); // avg 1620
//---
// Test 2 B
//while (--i -(-1)) {}
//end = getTimer();
//trace(2B: + (end-begin)); // avg 1480
Any thoughts or comments appreciated. Claus, Darron, you guys
reading?... I'd bet you guys could shed some light on p-code.
Yes, I definately agree with you that people should learn to write
different ways so that it's all readable code. I'm sure with time (--i
-(-i)) could look pretty natural to me though it looks a bit odd at the
moment. I'm always looking to learn something new and not afraid to ask
questions when I see something I don't understand.
James O'Reilly
www.jamesor.com
Steven Sacks | BLITZ wrote:
There has been extensive testing on this (search the archives) and it's
been proven to my satisfaction that pre-decrementated loops are
consistently faster than post-decremented loops, and specifically that
while (--i -(-1)) is faster than while (i--), less p-code or not.
To the point that it's more readable, that's like saying that you prefer
quarter notes instead of sixteenth notes when reading music. Once you
write while (--i -(-1)) a bunch, you have no trouble reading it. It's a
hell of a lot easier to read than the fastest for loop syntax.
for (var i = myArray.length; --i -(-1); ) {}
I mean, if you find inline conditionals or non-braced if statements hard
to read, does that mean you shouldn't write them or that you should
learn to write them so you can learn to read them.
I didn't like mustard when I was younger. Does that mean I shouldn't
ever like mustard? ;)
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
As to why exactly --i -(-1) runs faster in a while loop than i--, well, it can't be the same exact pcode or it wouldn't be faster so it must be less pcode. I didn't bother to verify it myself because at the time, somebody did for me. It's explained somewhere in the archives. If you dig, you'll find it, and you'll find my name somewhere in there along with it since I was part of the discussion on most occasions that it came up. I do like mustard, now, by the way. :) ___ Flashcoders@chattyfig.figleaf.com 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
RE: [Flashcoders] Find item in array
My original question to Jason was clarification on *why* (--i -(-1)) would run faster than (i--) as it seemed to me that two calculations per loop would run slower than 1. Since he used an expression I've never seen before I figured he might might know the reasoning behind the optimization. It does in fact surprise me that this method is faster. My only reason in suggesting that form of looping it is because it had been discussed extensively in the past that loops of this form are faster than other methods, so I borrowed that code from the likes of Steve and others. I have put that loop structure into applications and it does seem to be slightly faster to me, but maybe that's only my perception. I used it to loop through some large XML and it worked great. It may not be better, I don't have anything scientific to back it up. Steve is more capable to argue the point. I didn't develop the form, I was only using it based on suggestions of others. If you're not doing much looping and/or calculating, it doesn't really matter what you use. Jason Merrill Bank of America Learning Organization Effectiveness - Technology Solutions ___ Flashcoders@chattyfig.figleaf.com 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
RE: [Flashcoders] Find item in array
It's a hell of a lot easier to
read than the fastest for loop syntax.
for (var i = myArray.length; --i -(-1); ) {}
Actually that would be:
var l = myArray.length;
for (var i = l; --i -(-1); ) {}
Then you're not looking up the length on every iteration..
:p
M
___
Flashcoders@chattyfig.figleaf.com
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
Re: [Flashcoders] Find item in array
Unlike to evaluation of a condition, the initial value should be
evaluated only once anyway.
for (var i = initialValue(); icondition(); i++) {}
function initialValue() {
trace(initial value is evaluated);
return 0;
}
function condition() {
trace(condition is evaluated);
return 3;
}
// [Output]:
initial value is evaluated
condition is evaluated
condition is evaluated
condition is evaluated
condition is evaluated
_
Mike Mountain wrote:
var l = myArray.length;
for (var i = l; --i -(-1); ) {}
Then you're not looking up the length on every iteration..
--
Fumio Nonaka
mailto:[EMAIL PROTECTED]
http://www.FumioNonaka.com/
My bookshttp://www.FumioNonaka.com/Books/index.html
Flash communityhttp://F-site.org/
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
you live and learn.
M
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf
Of Fumio Nonaka
Sent: 19 September 2006 14:38
To: Flashcoders mailing list
Subject: Re: [Flashcoders] Find item in array
Unlike to evaluation of a condition, the initial value should
be evaluated only once anyway.
for (var i = initialValue(); icondition(); i++) {} function
initialValue() {
trace(initial value is evaluated);
return 0;
}
function condition() {
trace(condition is evaluated);
return 3;
}
// [Output]:
initial value is evaluated
condition is evaluated
condition is evaluated
condition is evaluated
condition is evaluated
_
Mike Mountain wrote:
var l = myArray.length;
for (var i = l; --i -(-1); ) {}
Then you're not looking up the length on every iteration..
--
Fumio Nonaka
mailto:[EMAIL PROTECTED]
http://www.FumioNonaka.com/
My bookshttp://www.FumioNonaka.com/Books/index.html
Flash communityhttp://F-site.org/
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
Re: RE: [Flashcoders] Find item in array
Unless the loop is a proven bottleneck, please don't use that while loop. I see
enough mystical journeys going through other people's code, I'd hate to start
seeing that floating around all over the place. Premature
optimization...evil...etc Pity the Java programmers who wander over into
AS2 and 3 land and have to squint at oddball loops.
From: Steven Sacks | BLITZ [EMAIL PROTECTED]
Date: 2006/09/18 Mon PM 11:27:33 CDT
To: Flashcoders mailing list flashcoders@chattyfig.figleaf.com
Subject: RE: [Flashcoders] Find item in array
There has been extensive testing on this (search the archives) and it's
been proven to my satisfaction that pre-decrementated loops are
consistently faster than post-decremented loops, and specifically that
while (--i -(-1)) is faster than while (i--), less p-code or not.
To the point that it's more readable, that's like saying that you prefer
quarter notes instead of sixteenth notes when reading music. Once you
write while (--i -(-1)) a bunch, you have no trouble reading it. It's a
hell of a lot easier to read than the fastest for loop syntax.
for (var i = myArray.length; --i -(-1); ) {}
I mean, if you find inline conditionals or non-braced if statements hard
to read, does that mean you shouldn't write them or that you should
learn to write them so you can learn to read them.
I didn't like mustard when I was younger. Does that mean I shouldn't
ever like mustard? ;)
___
Flashcoders@chattyfig.figleaf.com
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
--
John Mark Hawley
The Nilbog Group
773.968.4980 (cell)
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
My guess would be that postincrement it takes longer because it needs to store and return the original value, while preincrement only needs to return the result after performing the operation. But that's only a guess. ― Mike Keesey -Original Message- From: [EMAIL PROTECTED] [mailto:flashcoders- [EMAIL PROTECTED] On Behalf Of Steven Sacks | BLITZ Sent: Tuesday, September 19, 2006 1:45 AM To: Flashcoders mailing list Subject: RE: [Flashcoders] Find item in array As to why exactly --i -(-1) runs faster in a while loop than i--, well, it can't be the same exact pcode or it wouldn't be faster so it must be less pcode. I didn't bother to verify it myself because at the time, somebody did for me. It's explained somewhere in the archives. If you dig, you'll find it, and you'll find my name somewhere in there along with it since I was part of the discussion on most occasions that it came up. I do like mustard, now, by the way. :) ___ Flashcoders@chattyfig.figleaf.com 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 ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
Mike, that sounds very reasonable to me. What I've been able to ascertain is reading and writing to the register (in the case of (--i -(-1)) is significantly faster than reading and writing to a variable (in the case of (i--)) that the first case's additional instruction to subtract doesn't outweigh the gain. I guess it's kind of like a Porsce 911 is so much faster than a Ford Festiva that adding baggage to a luggage rack to make up for the lack of storage won't slow it down enough to lose in a race. Likewise, just because the extra instruction of subtraction adds another line of code, it doesn't mean it will run slower if the other lines can make up for it. I wonder if there is a reference online that shows how many relative cycles each instruction takes compared to one another. Aside from the one link for Flasm that Steven posted I haven't found much. I guess I can compile a bunch of different tests using various statements like push and setVariable and see the performance of each. I'm sure this has been done to death so I'd rather just read the findings. I guess this is my punishment for getting art degrees. Now whether I would use (--i -(-i)) over (i--) in practice is a different issue. My guess is I would use the former if FPS was a real concern and the later if readability was more of a priority. James O'Reilly www.jamesor.com Mike Keesey wrote: My guess would be that postincrement it takes longer because it needs to store and return the original value, while preincrement only needs to return the result after performing the operation. But that's only a guess. ― Mike Keesey ___ Flashcoders@chattyfig.figleaf.com 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
RE: [Flashcoders] Find item in array
I guess what it depends on is what you're doing with that for loop. If you're using it to attach or create or animate movieclips, or parse through xml or a recordset, or anything that would make Flash unresponsive during the loop, then the benefits of while (--a -(-1)) outweigh the readability compared to while (a--). As a result, I use it pretty often. ;) So, now I just end up using it for everything since it's become a habit. The flipside is that sometimes I need to do forward loops for reiterating to maintain proper order. However, I would have to do that anyway regardless of which backwards looping method I used. ___ Flashcoders@chattyfig.figleaf.com 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
RE: [Flashcoders] Find item in array
So, now I just end up using it for everything since it's become a habit. The flipside is that sometimes I need to do forward loops for reiterating to maintain proper order. However, I would have to do that anyway regardless of which backwards looping method I used. To clarify, I don't mean I do two for loops one after the other that do the same thing. That would be much slower than just one forward loop. I mean later on somewhere else in the app I might need that data in reverse order for some specific purpose. ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
for (var i:String in myArray)
{
if (myArray[i] == value)
return Number(i);
}
using a for..i..in loop will always be faster. Even more then --a -(-1)
iteration. Unless you can guarentee that your element will always be near
the beginning of a large array, as the for..i..in starts from the back. I
recommend using this loop anywhere you need the most speed and order doesn't
matter, as in this case.
Tyler
On 9/19/06, Steven Sacks | BLITZ [EMAIL PROTECTED] wrote:
I guess what it depends on is what you're doing with that for loop.
If you're using it to attach or create or animate movieclips, or parse
through xml or a recordset, or anything that would make Flash
unresponsive during the loop, then the benefits of while (--a -(-1))
outweigh the readability compared to while (a--).
As a result, I use it pretty often. ;)
So, now I just end up using it for everything since it's become a habit.
The flipside is that sometimes I need to do forward loops for
reiterating to maintain proper order. However, I would have to do that
anyway regardless of which backwards looping method I used.
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
using a for..i..in loop will always be faster. Even more then --a -(-1) I'm ducking and running for cover. Jason Merrill Bank of America Learning Organization Effectiveness - Technology Solutions ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
:)
So, for the sake of another one of those big arguments over what's better
where no one ever test, I wrote some code to find out exact results:
The following code executes one particular test on my Windows XP machine.
For results I got an averate of 347 miliseconds executeing the --i -(-1) and
343 ms with the for..in loop. I was surprised at how close they were. Now
that being the difference over 10,000 iterations, I can't really say for..in
is much faster, if at all. Perhaps the results are different on someone
else's machine, or perhaps different results from a different type of array.
Now iterating through the entire array the for..in did seem to be faster,
but for the test I chose a value directly in the middle so each method had
the same amount of value's to cover. anyway, I conclude nothing. ;)
except that we should always test our results.
Tyler
var myArray:Array = [a, b, c, d, e, f, g, h, i, j, k,
l, m, n, o, p];
var time:Number = getTimer();
var loop:Number = ;
while (loop--)
{
/*/
var j:Number = myArray.length
while (--j -(-1)) {
if(myArray[j] == h){
break;
}
}
/*/
for (var j in myArray)
{
if (myArray[j] == h)
break;
}
//*/
}
trace(getTimer() - time);
// 347
// 343
On 9/19/06, Merrill, Jason [EMAIL PROTECTED] wrote:
using a for..i..in loop will always be faster. Even more then --a
-(-1)
I'm ducking and running for cover.
Jason Merrill
Bank of America
Learning Organization Effectiveness - Technology Solutions
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
Wow, good thread.
Here's my 2 cents. Perhaps one other thing to factor is if the array is
sorted:
If the array is not sorted the best you can do is iterate through all of
the items in the array, checking each element, until you either find the
matching string or reach the end of the array. This approach is said to run
in linear time since the amount of time required for the algorithm to run is
linearly proportional to the length of the array. That is, if the array
contains 1,000 elements, you will have to check at most 1,000 elements
(assuming the element is in the last position of the array, or is not found
at all in the array); if the array contains 1,000,000 elements, you will
have to check at most 1,000,000 elements. Hence, there is a linear
proportionality between the amount of work that needs to be done to search
the array and the size of the array (namely, a proportion of 1).
However, if your array is sorted there is a much faster algorithm you can
employ to determine whether or not a particular element exists within the
array, known as the binary search algorithm. In this article we will examine
how this algorithm works, its running time, and how to use the
Array.BinarySearch method, which searches a sorted array using the binary
search algorithm.
Src: http://aspnet.4guysfromrolla.com/articles/110602-1.aspx
Src: http://code.dreamincode.net/snippet515.htm
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Tyler
Wright
Sent: Tuesday, September 19, 2006 4:36 PM
To: Flashcoders mailing list
Subject: Re: [Flashcoders] Find item in array
:)
So, for the sake of another one of those big arguments over what's better
where no one ever test, I wrote some code to find out exact results:
The following code executes one particular test on my Windows XP machine.
For results I got an averate of 347 miliseconds executeing the --i -(-1) and
343 ms with the for..in loop. I was surprised at how close they were. Now
that being the difference over 10,000 iterations, I can't really say for..in
is much faster, if at all. Perhaps the results are different on someone
else's machine, or perhaps different results from a different type of array.
Now iterating through the entire array the for..in did seem to be faster,
but for the test I chose a value directly in the middle so each method had
the same amount of value's to cover. anyway, I conclude nothing. ;)
except that we should always test our results.
Tyler
var myArray:Array = [a, b, c, d, e, f, g, h, i, j, k,
l, m, n, o, p];
var time:Number = getTimer();
var loop:Number = ;
while (loop--)
{
/*/
var j:Number = myArray.length
while (--j -(-1)) {
if(myArray[j] == h){
break;
}
}
/*/
for (var j in myArray)
{
if (myArray[j] == h)
break;
}
//*/
}
trace(getTimer() - time);
// 347
// 343
On 9/19/06, Merrill, Jason [EMAIL PROTECTED] wrote:
using a for..i..in loop will always be faster. Even more then --a
-(-1)
I'm ducking and running for cover.
Jason Merrill
Bank of America
Learning Organization Effectiveness - Technology Solutions
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
...even more relevant, an AS1 implementation of BinarySearch.
http://proto.layer51.com/d.aspx?f=1333
-mL
http://knowledge.lapasa.net
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Mark
Lapasa
Sent: Tuesday, September 19, 2006 4:44 PM
To: Flashcoders mailing list
Subject: RE: [Flashcoders] Find item in array
Wow, good thread.
Here's my 2 cents. Perhaps one other thing to factor is if the array is
sorted:
If the array is not sorted the best you can do is iterate through all of
the items in the array, checking each element, until you either find the
matching string or reach the end of the array. This approach is said to run
in linear time since the amount of time required for the algorithm to run is
linearly proportional to the length of the array. That is, if the array
contains 1,000 elements, you will have to check at most 1,000 elements
(assuming the element is in the last position of the array, or is not found
at all in the array); if the array contains 1,000,000 elements, you will
have to check at most 1,000,000 elements. Hence, there is a linear
proportionality between the amount of work that needs to be done to search
the array and the size of the array (namely, a proportion of 1).
However, if your array is sorted there is a much faster algorithm you can
employ to determine whether or not a particular element exists within the
array, known as the binary search algorithm. In this article we will examine
how this algorithm works, its running time, and how to use the
Array.BinarySearch method, which searches a sorted array using the binary
search algorithm.
Src: http://aspnet.4guysfromrolla.com/articles/110602-1.aspx
Src: http://code.dreamincode.net/snippet515.htm
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Tyler
Wright
Sent: Tuesday, September 19, 2006 4:36 PM
To: Flashcoders mailing list
Subject: Re: [Flashcoders] Find item in array
:)
So, for the sake of another one of those big arguments over what's better
where no one ever test, I wrote some code to find out exact results:
The following code executes one particular test on my Windows XP machine.
For results I got an averate of 347 miliseconds executeing the --i -(-1) and
343 ms with the for..in loop. I was surprised at how close they were. Now
that being the difference over 10,000 iterations, I can't really say for..in
is much faster, if at all. Perhaps the results are different on someone
else's machine, or perhaps different results from a different type of array.
Now iterating through the entire array the for..in did seem to be faster,
but for the test I chose a value directly in the middle so each method had
the same amount of value's to cover. anyway, I conclude nothing. ;)
except that we should always test our results.
Tyler
var myArray:Array = [a, b, c, d, e, f, g, h, i, j, k,
l, m, n, o, p];
var time:Number = getTimer();
var loop:Number = ;
while (loop--)
{
/*/
var j:Number = myArray.length
while (--j -(-1)) {
if(myArray[j] == h){
break;
}
}
/*/
for (var j in myArray)
{
if (myArray[j] == h)
break;
}
//*/
}
trace(getTimer() - time);
// 347
// 343
On 9/19/06, Merrill, Jason [EMAIL PROTECTED] wrote:
using a for..i..in loop will always be faster. Even more then --a
-(-1)
I'm ducking and running for cover.
Jason Merrill
Bank of America
Learning Organization Effectiveness - Technology Solutions
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
using a for..i..in loop will always be faster It's been proven before here on flashcoders that for in is not faster than --a -(-1) because it compiles to more lines of pcode. I guess it's time to use Flasm to bust out some pcode and post it here on the list instead of making claims based on hunches and past posts in the archives. ___ Flashcoders@chattyfig.figleaf.com 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
RE: [Flashcoders] Find item in array
And to be specific about why your for in as you put it would not be
faster, you're declaring var i in your loop, which results in more
pcode, which means it will take longer.
var a;
for (a in array) {}
would be faster.
___
Flashcoders@chattyfig.figleaf.com
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
Re: [Flashcoders] Find item in array
I think you have to keep the Flash player version in mind as well. Those tests and what lead to the awkward notation -- while (--i -(-1)) were done quite some time ago. Which each new flash player version, performance improves, so what once was true (one being slower than the other), may no longer be the case. regards, Muzak - Original Message - From: Tyler Wright [EMAIL PROTECTED] To: Flashcoders mailing list flashcoders@chattyfig.figleaf.com Sent: Tuesday, September 19, 2006 10:35 PM Subject: Re: [Flashcoders] Find item in array :) So, for the sake of another one of those big arguments over what's better where no one ever test, I wrote some code to find out exact results: The following code executes one particular test on my Windows XP machine. For results I got an averate of 347 miliseconds executeing the --i -(-1) and 343 ms with the for..in loop. I was surprised at how close they were. Now that being the difference over 10,000 iterations, I can't really say for..in is much faster, if at all. Perhaps the results are different on someone else's machine, or perhaps different results from a different type of array. Now iterating through the entire array the for..in did seem to be faster, but for the test I chose a value directly in the middle so each method had the same amount of value's to cover. anyway, I conclude nothing. ;) except that we should always test our results. Tyler ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
Actually, Tyler's tests proved that var a in is faster with today's player. I tried his test out myself and my results were even wider than his. I published for AS2 and ran in Flash Player 9. I was averaging roughly 265ms for var a in and 275ms for (--a -(-1)). Then I compiled for AS3 and it ran too fast for testing at 7ms for both AS3/Player 9 rocks!!! So, I added another 9 to the loop counter making it 9 iterations. Then var a in ran at 70ms, (--a -(-1)) and (a--) ran the same at 77ms. Then I added another 9 making the loops 99. var a in ran at 740ms, (--a -(-1)) ran 765ms and (a--) at 770ms. I'm satisfied that for (var a in array) is faster than while (--a -(-1)). Perhaps in the past that wasn't always the case, but with player 9 it is the case and that's what I'll be basing my decisions on. James O'Reilly http://www.jamesor.com Steven Sacks | BLITZ wrote: using a for..i..in loop will always be faster It's been proven before here on flashcoders that for in is not faster than --a -(-1) because it compiles to more lines of pcode. I guess it's time to use Flasm to bust out some pcode and post it here on the list instead of making claims based on hunches and past posts in the archives. ___ Flashcoders@chattyfig.figleaf.com 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 ___ Flashcoders@chattyfig.figleaf.com 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
RE: [Flashcoders] Find item in array
Is there an easy/quick way to find out if an item is in an array?
No built in methods I know of. But quick and easy, is just to loop.
Something like:
public function findStringItem(theArray:Array,
identifier:String):Number{
var i:Number = theArray.length
while (--i -(-1)) {
if(theArray[i] == identifier){
return i;
}
}
}
Jason Merrill
Bank of America
Learning Organization Effectiveness - Technology Solutions
-Original Message-
From: [EMAIL PROTECTED] [mailto:flashcoders-
[EMAIL PROTECTED] On Behalf Of Mendelsohn, Michael
Sent: Monday, September 18, 2006 4:39 PM
To: Flashcoders mailing list
Subject: [Flashcoders] Find item in array
Hi list...
Is there an easy/quick way to find out if an item is in an array? For
instance:
Var a:Array = [a,b,c,d];
Var y:Number = a[b];
//y would be the position in the array of b or undefined if it's not
in the array/
I'm looking for the equivalent of Director's getOne() function.
Thanks,
- Michael M.
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
Re: [Flashcoders] Find item in array
Yeah, you may want to try an indexed(?, sorry tired!) array: var a:Array = new Array(); a[b] = 1; . . a[d] = 4; then, var y:Number = a[b]; will result in y == 1; Scott On 9/18/06, Mendelsohn, Michael [EMAIL PROTECTED] wrote: Hi list... Is there an easy/quick way to find out if an item is in an array? For instance: Var a:Array = [a,b,c,d]; Var y:Number = a[b]; //y would be the position in the array of b or undefined if it's not in the array/ I'm looking for the equivalent of Director's getOne() function. Thanks, - Michael M. ___ Flashcoders@chattyfig.figleaf.com 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 -- : : ) Scott ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
Merrill, Jason wrote:
while (--i -(-1)) {
Jason, very interesting way of counting through the array. I haven't
see this approach before. Are there any benefits to using (--i -(-i))
in the expression over something like the following?:
while (i--) {
It seems like your loop would need to do two calculations each trip.
One for decrementing i and the second for adding 1 to it to keep the
number above zero so it returns true. If you decrement i after the
condition using i-- instead of before the condition with --i you won't
need add 1 to it. Just an idea.
However, as far as I know you're right looping through the array in AS
2.0 is the only way to find the index of an item. You might also want
to use === instead of == to do strict comparing so 12 doesn't equal
12. Depends on what you need tho.
One thing I might add to your function is the ability to return -1
instead of undefined when an item isn't found which is more consistent
with the String.indexOf method.
Thankfully, in AS 3.0 there is a method to find the index and as fate
would have it it's called indexOf(). It returns either the index if
found or -1 if not found. You would use it like:
var idx:Number = a.indexOf(d);
Cheers,
-- James
James O'Reilly
www.jamesor.com
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
It's the fastest because: Pre-decrementation (--i) is faster than post-decrementation (i--) And substraction (- (-1) is faster than addition (+ 1). They are faster because it's less code that gets produced when you compile. http://flasm.sourceforge.net/#optimization For most cases, it's a matter of milliseconds or even less, which isn't that big a deal, but I use it anyway because it's a good habit to have and it makes my code logic work with that in mind always so when it does make a difference in seconds, it's already there. ___ Flashcoders@chattyfig.figleaf.com 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
Re: [Flashcoders] Find item in array
Steven Sacks | BLITZ wrote:
It's the fastest because:
Pre-decrementation (--i) is faster than post-decrementation (i--)
I don't see why that would be. Both var i=1;i--; and var i=1;--i;
compile down to the exact same 8 lines of p-code:
_constantPool i
_push i 1
_var
_push i i
_getVariable
_decrement
_setVariable
_end
So i don't see how one can be faster than the other. Maybe in other
languages this is the case?
And substraction (- (-1) is faster than addition (+ 1).
I ran numerous tests using loops of 1 million on this but was unable to
conclude one way or the other because roughly half the time one method
was faster than the other. differences ranged from 1 millisecond to 175
milliseconds in both directions. My only take on my results is that
they are at least negligably similar.
They are faster because it's less code that gets produced when you
compile.
http://flasm.sourceforge.net/#optimization
This isn't true. (i--) is one less line of p-code (and 9 less bytes of
data) than (--i -(-1)) because it isn't doing the extra calculation of
subtraction like I mentioned in my email. Take a look at the p-code:
var i:Number = 1;
while (i--) {
trace(i);
}
_constantPool i
_push i 1
_var
#4 _push i
_getVariable
_push i i
_getVariable
_decrement
_setVariable
_not
_if true goto #16
_push i
_getVariable
_trace
_jump to #4
#16 _end
--
var i:Number = 1;
while (--i -(-1)) {
trace(i);
}
_constantPool i
_push i 1
_var
#4 _push i i
_getVariable
_decrement
_storeRegister 0
_setVariable
_push register0 4294967295
_subtract
_not
_if true goto #17
_push i
_getVariable
_trace
_jump to #4
#17 _end
For most cases, it's a matter of milliseconds or even less, which isn't
that big a deal, but I use it anyway because it's a good habit to have
and it makes my code logic work with that in mind always so when it does
make a difference in seconds, it's already there.
I agree about it not being a big deal, but I prefer the (i--) method
over (--i -(-1)) since I find it easier to read.
-- James
James O'Reilly
www.jamesor.com
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
Go James!
Thanks for doing the due-diligence on this one.
I read the thread and it was somethin I had not heard of before.
Thanks for clearing it up.
Regards,
Bjorn Schultheiss
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of JOR
Sent: Tuesday, 19 September 2006 1:23 PM
To: Flashcoders mailing list
Subject: Re: [Flashcoders] Find item in array
Steven Sacks | BLITZ wrote:
It's the fastest because:
Pre-decrementation (--i) is faster than post-decrementation (i--)
I don't see why that would be. Both var i=1;i--; and var i=1;--i;
compile down to the exact same 8 lines of p-code:
_constantPool i
_push i 1
_var
_push i i
_getVariable
_decrement
_setVariable
_end
So i don't see how one can be faster than the other. Maybe in other
languages this is the case?
And substraction (- (-1) is faster than addition (+ 1).
I ran numerous tests using loops of 1 million on this but was unable to
conclude one way or the other because roughly half the time one method
was faster than the other. differences ranged from 1 millisecond to 175
milliseconds in both directions. My only take on my results is that
they are at least negligably similar.
They are faster because it's less code that gets produced when you
compile.
http://flasm.sourceforge.net/#optimization
This isn't true. (i--) is one less line of p-code (and 9 less bytes of
data) than (--i -(-1)) because it isn't doing the extra calculation of
subtraction like I mentioned in my email. Take a look at the p-code:
var i:Number = 1;
while (i--) {
trace(i);
}
_constantPool i
_push i 1
_var
#4 _push i
_getVariable
_push i i
_getVariable
_decrement
_setVariable
_not
_if true goto #16
_push i
_getVariable
_trace
_jump to #4
#16 _end
--
var i:Number = 1;
while (--i -(-1)) {
trace(i);
}
_constantPool i
_push i 1
_var
#4 _push i i
_getVariable
_decrement
_storeRegister 0
_setVariable
_push register0 4294967295
_subtract
_not
_if true goto #17
_push i
_getVariable
_trace
_jump to #4
#17 _end
For most cases, it's a matter of milliseconds or even less, which isn't
that big a deal, but I use it anyway because it's a good habit to have
and it makes my code logic work with that in mind always so when it does
make a difference in seconds, it's already there.
I agree about it not being a big deal, but I prefer the (i--) method
over (--i -(-1)) since I find it easier to read.
-- James
James O'Reilly
www.jamesor.com
___
Flashcoders@chattyfig.figleaf.com
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
___
Flashcoders@chattyfig.figleaf.com
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
RE: [Flashcoders] Find item in array
There has been extensive testing on this (search the archives) and it's
been proven to my satisfaction that pre-decrementated loops are
consistently faster than post-decremented loops, and specifically that
while (--i -(-1)) is faster than while (i--), less p-code or not.
To the point that it's more readable, that's like saying that you prefer
quarter notes instead of sixteenth notes when reading music. Once you
write while (--i -(-1)) a bunch, you have no trouble reading it. It's a
hell of a lot easier to read than the fastest for loop syntax.
for (var i = myArray.length; --i -(-1); ) {}
I mean, if you find inline conditionals or non-braced if statements hard
to read, does that mean you shouldn't write them or that you should
learn to write them so you can learn to read them.
I didn't like mustard when I was younger. Does that mean I shouldn't
ever like mustard? ;)
___
Flashcoders@chattyfig.figleaf.com
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
