Re: [Flashcoders] Doing a binary search in AS3?
Merrill, Jason wrote: I understand what a binary search algorithm is, but am wondering how that could be implemented on an array in Actionscript (if at all) without using methods that would defeating the purpose of a binary search (speed). Anyone have experience in this area? So for example, if you have a list like this: [apple, orange, banana, pear, cherry, pineapple, kiwi, peach] Then to do a binary search for say, pineapple, as I understand binary searching, you would first split the list in the middle (between pear and cherry) and determine if pineapple was in that list - if not, search the other half and so on until you find pineapple. That is wrong, you know that it will be in a certain half due to the list being sorted. There is no need to scan the half for the object, by the list already being sorted, you know that if the object exists, it's in that half. Just compare the middle element, if it is bigger, use the left half, else use the right half. ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
RE: [Flashcoders] Doing a binary search in AS3?
Just compare the middle element, if it is bigger, use the left half, else use the right half. I don't follow - can you post an Actionscript example? Jason Merrill Bank of America Global Learning Learning Performance Solutions Join the Bank of America Flash Platform Community and visit our Instructional Technology Design Blog (note: these are for Bank of America employees only) -Original Message- From: flashcoders-boun...@chattyfig.figleaf.com [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Henrik Andersson Sent: Thursday, May 06, 2010 10:45 AM To: Flash Coders List Subject: Re: [Flashcoders] Doing a binary search in AS3? Merrill, Jason wrote: I understand what a binary search algorithm is, but am wondering how that could be implemented on an array in Actionscript (if at all) without using methods that would defeating the purpose of a binary search (speed). Anyone have experience in this area? So for example, if you have a list like this: [apple, orange, banana, pear, cherry, pineapple, kiwi, peach] Then to do a binary search for say, pineapple, as I understand binary searching, you would first split the list in the middle (between pear and cherry) and determine if pineapple was in that list - if not, search the other half and so on until you find pineapple. That is wrong, you know that it will be in a certain half due to the list being sorted. There is no need to scan the half for the object, by the list already being sorted, you know that if the object exists, it's in that half. Just compare the middle element, if it is bigger, use the left half, else use the right half. ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Re: [Flashcoders] Doing a binary search in AS3?
the most important thing being as Hendrik said that it is sorted, which in your example it is not. Say you have: [apple, banana, cherry, kiwi, orange, peach pear, pineapple, ] and you are looking for banana: middle element is orange (or kiwi) take apple, banana, cherry, kiwi, middle element is cherry take apple, banana middle element is banana yeah a hit My description is a bit shabby but you get the idea. Whether it beats a dictionary ... I don't think so, I've only done this when searching through huge sorted files with random file access, not with arrays in flash. regards Hans On Thu, May 6, 2010 at 4:44 PM, Henrik Andersson he...@henke37.cjb.netwrote: Merrill, Jason wrote: I understand what a binary search algorithm is, but am wondering how that could be implemented on an array in Actionscript (if at all) without using methods that would defeating the purpose of a binary search (speed). Anyone have experience in this area? So for example, if you have a list like this: [apple, orange, banana, pear, cherry, pineapple, kiwi, peach] Then to do a binary search for say, pineapple, as I understand binary searching, you would first split the list in the middle (between pear and cherry) and determine if pineapple was in that list - if not, search the other half and so on until you find pineapple. That is wrong, you know that it will be in a certain half due to the list being sorted. There is no need to scan the half for the object, by the list already being sorted, you know that if the object exists, it's in that half. Just compare the middle element, if it is bigger, use the left half, else use the right half. ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Re: [Flashcoders] Doing a binary search in AS3?
Merrill, Jason wrote:
Just compare the middle element, if it is bigger, use the left half,
else use the right half.
I don't follow - can you post an Actionscript example?
//warning, not fully correct, will infinity loop
while(leftright) {
var middle=(left+right)/2;
var value=arr[middle];
if(valueneedle) {
right=middle;
} else {
left=middle;
}
}
___
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
RE: [Flashcoders] Doing a binary search in AS3?
Ah - I see - very good, thanks! But you also need to employ some logic at looking at the characters in the string - first the first letter, then once you get down to a list where they all have the same first letter, then take the second, and so forth until you only have one item left - sounds complicated. Reason this whole thing got started with me was Grant Skinner's presentation on AS3 optimization http://www.gskinner.com/talks/quickNL/ See slides 68 69. Binary way faster than linear searching - but no examples on implementing it. I can see how to write this now - but wonder if it would be worth it if using Dictionary would be faster - anyone know? Jason Merrill Bank of America Global Learning Learning Performance Solutions Join the Bank of America Flash Platform Community and visit our Instructional Technology Design Blog (note: these are for Bank of America employees only) -Original Message- From: flashcoders-boun...@chattyfig.figleaf.com [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Hans Wichman Sent: Thursday, May 06, 2010 11:06 AM To: Flash Coders List Subject: Re: [Flashcoders] Doing a binary search in AS3? the most important thing being as Hendrik said that it is sorted, which in your example it is not. Say you have: [apple, banana, cherry, kiwi, orange, peach pear, pineapple, ] and you are looking for banana: middle element is orange (or kiwi) take apple, banana, cherry, kiwi, middle element is cherry take apple, banana middle element is banana yeah a hit My description is a bit shabby but you get the idea. Whether it beats a dictionary ... I don't think so, I've only done this when searching through huge sorted files with random file access, not with arrays in flash. regards Hans On Thu, May 6, 2010 at 4:44 PM, Henrik Andersson he...@henke37.cjb.netwrote: Merrill, Jason wrote: I understand what a binary search algorithm is, but am wondering how that could be implemented on an array in Actionscript (if at all) without using methods that would defeating the purpose of a binary search (speed). Anyone have experience in this area? So for example, if you have a list like this: [apple, orange, banana, pear, cherry, pineapple, kiwi, peach] Then to do a binary search for say, pineapple, as I understand binary searching, you would first split the list in the middle (between pear and cherry) and determine if pineapple was in that list - if not, search the other half and so on until you find pineapple. That is wrong, you know that it will be in a certain half due to the list being sorted. There is no need to scan the half for the object, by the list already being sorted, you know that if the object exists, it's in that half. Just compare the middle element, if it is bigger, use the left half, else use the right half. ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Re: [Flashcoders] Doing a binary search in AS3?
Hi Jason, the complexity probably isnt that hard. You have s, you look at wordlist[wordlist.length/2], you find a g, so clearly you have to repeat that for the upper half of the list etc. Dictionary is not going to work here at least not on the whole words, you would have to store partial lookups eg dictionary[a] - all words starting with a here, etc. Maybe even nested dictionaries. regards, JC On Thu, May 6, 2010 at 5:19 PM, Merrill, Jason jason.merr...@bankofamerica.com wrote: Ah - I see - very good, thanks! But you also need to employ some logic at looking at the characters in the string - first the first letter, then once you get down to a list where they all have the same first letter, then take the second, and so forth until you only have one item left - sounds complicated. Reason this whole thing got started with me was Grant Skinner's presentation on AS3 optimization http://www.gskinner.com/talks/quickNL/ See slides 68 69. Binary way faster than linear searching - but no examples on implementing it. I can see how to write this now - but wonder if it would be worth it if using Dictionary would be faster - anyone know? Jason Merrill Bank of America Global Learning Learning Performance Solutions Join the Bank of America Flash Platform Community and visit our Instructional Technology Design Blog (note: these are for Bank of America employees only) -Original Message- From: flashcoders-boun...@chattyfig.figleaf.com [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Hans Wichman Sent: Thursday, May 06, 2010 11:06 AM To: Flash Coders List Subject: Re: [Flashcoders] Doing a binary search in AS3? the most important thing being as Hendrik said that it is sorted, which in your example it is not. Say you have: [apple, banana, cherry, kiwi, orange, peach pear, pineapple, ] and you are looking for banana: middle element is orange (or kiwi) take apple, banana, cherry, kiwi, middle element is cherry take apple, banana middle element is banana yeah a hit My description is a bit shabby but you get the idea. Whether it beats a dictionary ... I don't think so, I've only done this when searching through huge sorted files with random file access, not with arrays in flash. regards Hans On Thu, May 6, 2010 at 4:44 PM, Henrik Andersson he...@henke37.cjb.netwrote: Merrill, Jason wrote: I understand what a binary search algorithm is, but am wondering how that could be implemented on an array in Actionscript (if at all) without using methods that would defeating the purpose of a binary search (speed). Anyone have experience in this area? So for example, if you have a list like this: [apple, orange, banana, pear, cherry, pineapple, kiwi, peach] Then to do a binary search for say, pineapple, as I understand binary searching, you would first split the list in the middle (between pear and cherry) and determine if pineapple was in that list - if not, search the other half and so on until you find pineapple. That is wrong, you know that it will be in a certain half due to the list being sorted. There is no need to scan the half for the object, by the list already being sorted, you know that if the object exists, it's in that half. Just compare the middle element, if it is bigger, use the left half, else use the right half. ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
RE: [Flashcoders] Doing a binary search in AS3?
Thanks - no, I only mentioned Dictionary to see if anyone knew if looking something up in a Dictionary object was faster or slower than a binary search. Jason Merrill Bank of America Global Learning Learning Performance Solutions Join the Bank of America Flash Platform Community and visit our Instructional Technology Design Blog (note: these are for Bank of America employees only) -Original Message- From: flashcoders-boun...@chattyfig.figleaf.com [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Hans Wichman Sent: Thursday, May 06, 2010 12:49 PM To: Flash Coders List Subject: Re: [Flashcoders] Doing a binary search in AS3? Hi Jason, the complexity probably isnt that hard. You have s, you look at wordlist[wordlist.length/2], you find a g, so clearly you have to repeat that for the upper half of the list etc. Dictionary is not going to work here at least not on the whole words, you would have to store partial lookups eg dictionary[a] - all words starting with a here, etc. Maybe even nested dictionaries. regards, JC On Thu, May 6, 2010 at 5:19 PM, Merrill, Jason jason.merr...@bankofamerica.com wrote: Ah - I see - very good, thanks! But you also need to employ some logic at looking at the characters in the string - first the first letter, then once you get down to a list where they all have the same first letter, then take the second, and so forth until you only have one item left - sounds complicated. Reason this whole thing got started with me was Grant Skinner's presentation on AS3 optimization http://www.gskinner.com/talks/quickNL/ See slides 68 69. Binary way faster than linear searching - but no examples on implementing it. I can see how to write this now - but wonder if it would be worth it if using Dictionary would be faster - anyone know? Jason Merrill Bank of America Global Learning Learning Performance Solutions Join the Bank of America Flash Platform Community and visit our Instructional Technology Design Blog (note: these are for Bank of America employees only) -Original Message- From: flashcoders-boun...@chattyfig.figleaf.com [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Hans Wichman Sent: Thursday, May 06, 2010 11:06 AM To: Flash Coders List Subject: Re: [Flashcoders] Doing a binary search in AS3? the most important thing being as Hendrik said that it is sorted, which in your example it is not. Say you have: [apple, banana, cherry, kiwi, orange, peach pear, pineapple, ] and you are looking for banana: middle element is orange (or kiwi) take apple, banana, cherry, kiwi, middle element is cherry take apple, banana middle element is banana yeah a hit My description is a bit shabby but you get the idea. Whether it beats a dictionary ... I don't think so, I've only done this when searching through huge sorted files with random file access, not with arrays in flash. regards Hans On Thu, May 6, 2010 at 4:44 PM, Henrik Andersson he...@henke37.cjb.netwrote: Merrill, Jason wrote: I understand what a binary search algorithm is, but am wondering how that could be implemented on an array in Actionscript (if at all) without using methods that would defeating the purpose of a binary search (speed). Anyone have experience in this area? So for example, if you have a list like this: [apple, orange, banana, pear, cherry, pineapple, kiwi, peach] Then to do a binary search for say, pineapple, as I understand binary searching, you would first split the list in the middle (between pear and cherry) and determine if pineapple was in that list - if not, search the other half and so on until you find pineapple. That is wrong, you know that it will be in a certain half due to the list being sorted. There is no need to scan the half for the object, by the list already being sorted, you know that if the object exists, it's in that half. Just compare the middle element, if it is bigger, use the left half, else use the right half. ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders ___ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
