homepage Welcome to WebmasterWorld Guest from 54.166.66.204
register, free tools, login, search, pro membership, help, library, announcements, recent posts, open posts,
Become a Pro Member

Home / Forums Index / Code, Content, and Presentation / JavaScript and AJAX
Forum Library, Charter, Moderator: open

JavaScript and AJAX Forum

    
Javascript Array - scan for value
Need to find the biggest number...
toadhall




msg:1471011
 3:00 am on Apr 30, 2003 (gmt 0)

Question.

What's the fastest way to find the largest number in an array?

var foo new Array("215","322","314","321");

These are image widths.

Thanks.

 

DrDoc




msg:1471012
 3:11 am on Apr 30, 2003 (gmt 0)

I think the "bubble" effect is pretty much the only solution... A loop that compares the values, if it's larger than the previously largest, it replaces that information.

Try googling [google.com] it.

toadhall




msg:1471013
 3:33 am on Apr 30, 2003 (gmt 0)

Google, what a concept.

Here's what I scraped together from a chart makers code samples:


var foo = new Array("215","322","314","321","322");
var biggest = 10; // set lower than any image width
for (x=0;x<foo.length;x++){
if (foo[x] > biggest) { // if the value is greater...
biggest = foo[x] // it becomes the "biggest"
} // and the loop goes on until...
}
document.write(biggest); // you end up with the biggest

Yow! Science.

Thanks for the prod DrDoc

T

ShawnR




msg:1471014
 3:45 am on Apr 30, 2003 (gmt 0)

I'm going to go out on a limb here, and hope my reasoning is correct:

If (a) the array is unsorted, and (b) you are not using a language and computer with parrallel processing; then there is only one answer... You have to look at every element of the array once and once only, all implementations will just be varients of the same algorithm and will take order-n time, where n is the length of the array (you need to make n-1 comparisons). To make it faster, you could ensure that the array is sorted in the first place (if that suites you application); but you may not have that freedom.

If the problem was how to sort the array, then there would be a number of trade-offs with different alorithms, some optimised for number of comparisons, some for number of swaps or insertions required, some for simplicity of algorithm and maintenance of the resulting sorted datastructure. Examples are bubble sort, quicksort, heapsort, binsort. But if the problem is just to search for an element in an unsorted list, there is only one answer.

Shawn

ShawnR




msg:1471015
 3:51 am on Apr 30, 2003 (gmt 0)

"...var biggest = 10; // set lower than any image width
for (x=0;x<foo.length;x++){

Not that it will be noticable at all, but just from a purist perspective, that does one comparison too many. You can make it more efficient as follows:

var biggest = foo[0];
for (x=1;x<foo.length;x++){
biggest = foo[x] // it becomes the "biggest"
}

gph




msg:1471016
 4:03 am on Apr 30, 2003 (gmt 0)

You can do this a few ways, a loop using Math.max() for example. But since it's just numbers I'd use sort()

foo = new Array("215","322","314","321","322")
blah = foo.sort().reverse()
alert(blah[0])

[edited by: gph at 4:04 am (utc) on April 30, 2003]

toadhall




msg:1471017
 4:04 am on Apr 30, 2003 (gmt 0)

Javascrpt sort() is pretty limited. It sorts right then and there - no saving the value(s) to a new array. Even if you do the original array is rearranged permanently.

Bit of a shock.

And it only sorts alphabetically. If you want to sort numerically you have to add a wee function:


var nob = new Array(4,8,2,3,1,11,6);
function numberorder(a,b) { return a - b; }
document.write(nob.sort(numberorder));

(from O'Reilly, the Definitive Guide)

<added>I need to keep the original array intact - it's part of a multidimensional array with all the image data in it.
Thanks Shawn. I'll try that.
</added>

T

ShawnR




msg:1471018
 5:04 am on Apr 30, 2003 (gmt 0)

If you are after the fastest algorithm, then I suggest don't sort first. Finding the number takes order-n, sorting takes between order(n log n) to order(n squared), dependig on the sort algorithm used. May not be significant... just depends on the size of your data.

So, I'd suggest only sort it if you intend to sort it once and then keep it sorted by inserting any new records in their correct position rather than tacking them on to the end. Don't sort it every time. Of course there are counter arguments, such as the sort() function is built in to the browser and hence, being compiled, may run faster than an interpreted function.

Shawn

toadhall




msg:1471019
 6:28 pm on May 6, 2003 (gmt 0)

An update:

If you use, as I have, an array of strings to store the width numbers, you'll have to use parseInt() to change them to integers when passing the value to the 'biggest' variable. Otherwise you'll end up with comparisons between strings after the first iteration. Apparently the comparison would then be between character codes of the numbers in the strings.

It's enough to convert foo[x] in just the first instance of upping the 'biggest' value as after that the conversion is automatic in the comparison, typical of untyped Javascript.

Anyway, moral is "Store the image widths (and heights) as INTEGERS in the first place and save yourself some trouble."

var foo = new Array("215","322","314","321","322");
var biggest = 10;
for (x=0;x<foo.length;x++) {
if (foo[x] > biggest) {
biggest = parseInt(foo[x]); //right here
}
}
document.write(biggest);

T

Global Options:
 top home search open messages active posts  
 

Home / Forums Index / Code, Content, and Presentation / JavaScript and AJAX
rss feed

All trademarks and copyrights held by respective owners. Member comments are owned by the poster.
Home ¦ Free Tools ¦ Terms of Service ¦ Privacy Policy ¦ Report Problem ¦ About ¦ Library ¦ Newsletter
WebmasterWorld is a Developer Shed Community owned by Jim Boykin.
© Webmaster World 1996-2014 all rights reserved