Finding the max number in a list

[Sharp]

Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.
I could write a method that compares a pair of integers at a time using
Maths.max(int,int) method, but seems to long for my arraylist.
What is the easiest way of doing this?

Cheers
Sharp

 

[Sharp]

Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.
I could write a method that compares a pair of integers at a time using
Maths.max(int,int) method, but seems to long for my arraylist.
What is the easiest way of doing this?

Cheers
Sharp

found that by using an arraylist i could use the max() of collections class
but i would have to wrap my integers as objects.
again, is this the easiest way of doing this?

Ideally i would like to use a method of some class without having to wrap
these integers.

Cheers
Sharp

 

[Arnaud Berger]

Hi,

Wouldn't the following be enough ?

int max=Integer.MIN_VALUE;

for(int i=0;i<array.length;i++){
max=Math.max(max,array);
}

Regards,

Arnaud

 

[Wannabee]

"Sharp"

Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.

Have you considered using
static void java.util.Arrays.sort (int[] a)

.... if that really was an array of integers you are talking about. Hmmm ...
I notice you are also talking about "a list" and your "arraylist" ... Make
up your mind, man!

 

[Ross Bamford]

Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.
I could write a method that compares a pair of integers at a time using
Maths.max(int,int) method, but seems to long for my arraylist.
What is the easiest way of doing this?

Cheers
Sharp

This won't be popular but it's easy:

int largest = 0;
for (int i : myInts) if (i > largest) largest = i;

It's not especially efficient, but then it's not especially inefficient
either.

Cheers,
Ross

 

[Sharp]

Hi,

Wouldn't the following be enough ?

int max=Integer.MIN_VALUE;

for(int i=0;i<array.length;i++){
max=Math.max(max,array);
}

Regards,

Arnaud

Yes, very clever.
Another question, why don't you use?

int max=0; //instead of int max=Integer.MIN_VALUE;

Cheers
Sharp

 

[Arnaud Berger]

Because integers may be negative...

Regards,

Arnaud

Hi,

Wouldn't the following be enough ?

int max=Integer.MIN_VALUE;

for(int i=0;i<array.length;i++){
max=Math.max(max,array);
}

Regards,

Arnaud

Yes, very clever.
Another question, why don't you use?

int max=0; file://instead of int max=Integer.MIN_VALUE;

Cheers
Sharp

 

[Fred L. Kleinschmidt]

This won't be popular but it's easy:

int largest = 0;
for (int i : myInts) if (i > largest) largest = i;

It's not especially efficient, but then it's not especially inefficient
either.

Cheers,
Ross

It also will not work. What happens if all values in the array are
negative?

int mx = array[0];
for (int i=1; i < array.length; i++) {
mx = (mx < array) ? array : mx; // or: mx = Math.max(mx,
array)
}

Assumes, of course, that array.length > 0
Why use the extra overhead of a function (Math.max) ?

 

[Patricia Shanahan]

This won't be popular but it's easy:

int largest = 0;
for (int i : myInts) if (i > largest) largest = i;

It's not especially efficient, but then it's not especially inefficient
either.

Cheers,
Ross

I don't know why you expect it to be unpopular. Almost all
the instances of finding the maximum or minimum of an
unsorted list or array that I have seen in real code follow
that pattern.

The general method is the most efficient possible. It visits
each element once. Unless there is additional data about the
order of the values in the list, every element must be
examined at least once.

However, it is invalid if the initial value of largest is
greater than the actual maximum. Consider, for example,
applying the code as written to new int[]{-3,-10}.

For something like int, with a known minimum value,
Integer.MIN_VALUE, you can initialize largest with that. See
Arnaud Berger's first posting in this thread.

If in any doubt about the correct initial value, or if it is
not known, use an input element:

int largest = myInts[0];

Of course, to turn any of this into real code, you need to
decide what result you want for a length zero array, or
empty list.

Patricia

 

[Ross Bamford]

I don't know why you expect it to be unpopular. Almost all
the instances of finding the maximum or minimum of an
unsorted list or array that I have seen in real code follow
that pattern.

You and I know that, but many "Java people" seem to imagine that this
stuff happens by magic, and if you're not using a weighted hash or some
such thing, or performing sorts, or whatever then you're an idiot /
should have your JDK license revoked / etc. The attitude seems to be
that we should leave 'that stuff' to other people (who? why?) and make
everything work by wiring together two hundred and eleven classes (plus
dependencies) so that we can be 'extensible' (as if it wasn't big enough
already).

The general method is the most efficient possible. It visits
each element once. Unless there is additional data about the
order of the values in the list, every element must be
examined at least once.

This is what I meant by "it's not particularly inefficient either". I
don't believe it is particularly efficient, and if your particular
circumstances allow you to track the largest element some other way then
do, but if not...

Ross

 

[Ross Bamford]

It also will not work. What happens if all values in the array are
negative?

As Patricia suggests in another reply, initialize the starting 'largest'
to Integer.MIN_VALUE. Apologies for this oversight.

Assumes, of course, that array.length > 0
Why use the extra overhead of a function (Math.max) ?

I didn't? Or is that to OP?

Ross

 

[Boudewijn Dijkstra]

"Sharp"

Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.

Have you considered using
static void java.util.Arrays.sort (int[] a)

Overkill.

 

[Lasse Reichstein Nielsen]

This is what I meant by "it's not particularly inefficient either". I
don't believe it is particularly efficient,

It's probably as effective as at all possible. There is no superfluous
operation in the loop, and the loop accesses each element of the array
exactly once.

and if your particular circumstances allow you to track the largest
element some other way then do, but if not...

If there is a known structure on the values in the list, then maybe
you can do better (if it's sorted, you can find the max in constant
time .


/L

 

[Eric Sosman]

"Sharp"

Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.

Have you considered using
static void java.util.Arrays.sort (int[] a)

Overkill.

And woefully inefficient on modern hardware, too.
To take advantage of SMP systems, CMT processors, even
hyperthreaded(tm) machines, you need some parallelism.
Here's the approach I'd recommend:

- If there are N numbers in the array, launch N/2
threads and give each thread two of the numbers.
Each thread's job is to compute the larger of the
two numbers it's been given. (If N is odd, launch
one extra thread to compute the larger of the final
value and Integer.MIN_VALUE.)

- When all N/2 threads have terminated, collect the
N/2 "first round winners" that they computed. You
have reduced the problem size by half, the first
step of a classic divide-and-conquer strategy.

- Now launch N/4 threads, handing each of them a pair
of the "first round winners." Collect their N/4
results and launch N/8 threads to compute the winners
of the next round, and so on until you finish up by
running N/N == 1 thread to compute the larger of the
two "semifinalists:" the Grand Champion.

This requires only ceil(lg(N)) stages, with each stage
except the final few exploiting all the computing resources
on the system toward the solution of the problem. That's
why it's so much more efficient than the primitive single-
threaded O(N) methods suggested thus far, methods that
cannot hope to take advantage of today's machines.

;-)

 

[Ross Bamford]

It's probably as effective as at all possible. There is no superfluous
operation in the loop, and the loop accesses each element of the array
exactly once.

Just because something is the *only* way to do something doesn't mean
it's efficient. That's my point. It's just 'not particularly
inefficient' with reference to other general solutions.

If there is a known structure on the values in the list, then maybe
you can do better (if it's sorted, you can find the max in constant
time .

true, but you take a hit on keeping the list sorted (since a one-time
sort takes you back to linear or worse I'd expect?)

Cheers,
Ross

 

[Ross Bamford]

"Sharp"

Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.

Have you considered using
static void java.util.Arrays.sort (int[] a)

Overkill.

And woefully inefficient on modern hardware, too.
To take advantage of SMP systems, CMT processors, even
hyperthreaded(tm) machines, you need some parallelism.
Here's the approach I'd recommend:

- If there are N numbers in the array, launch N/2
threads and give each thread two of the numbers.
Each thread's job is to compute the larger of the
two numbers it's been given. (If N is odd, launch
one extra thread to compute the larger of the final
value and Integer.MIN_VALUE.)

- When all N/2 threads have terminated, collect the
N/2 "first round winners" that they computed. You
have reduced the problem size by half, the first
step of a classic divide-and-conquer strategy.

- Now launch N/4 threads, handing each of them a pair
of the "first round winners." Collect their N/4
results and launch N/8 threads to compute the winners
of the next round, and so on until you finish up by
running N/N == 1 thread to compute the larger of the
two "semifinalists:" the Grand Champion.

This requires only ceil(lg(N)) stages, with each stage
except the final few exploiting all the computing resources
on the system toward the solution of the problem. That's
why it's so much more efficient than the primitive single-
threaded O(N) methods suggested thus far, methods that
cannot hope to take advantage of today's machines.

;-)

))

 

[John Rushford]

"Wannabee" <[email protected]> schreef in bericht

"Sharp"


Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.

Have you considered using
static void java.util.Arrays.sort (int[] a)

Overkill.

And woefully inefficient on modern hardware, too.
To take advantage of SMP systems, CMT processors, even
hyperthreaded(tm) machines, you need some parallelism.
Here's the approach I'd recommend:

- If there are N numbers in the array, launch N/2
threads and give each thread two of the numbers.
Each thread's job is to compute the larger of the
two numbers it's been given. (If N is odd, launch
one extra thread to compute the larger of the final
value and Integer.MIN_VALUE.)

- When all N/2 threads have terminated, collect the
N/2 "first round winners" that they computed. You
have reduced the problem size by half, the first
step of a classic divide-and-conquer strategy.

- Now launch N/4 threads, handing each of them a pair
of the "first round winners." Collect their N/4
results and launch N/8 threads to compute the winners
of the next round, and so on until you finish up by
running N/N == 1 thread to compute the larger of the
two "semifinalists:" the Grand Champion.

This requires only ceil(lg(N)) stages, with each stage
except the final few exploiting all the computing resources
on the system toward the solution of the problem. That's
why it's so much more efficient than the primitive single-
threaded O(N) methods suggested thus far, methods that
cannot hope to take advantage of today's machines.

;-)

java.util.Arrays.sort according to the documentation, uses a tuned
quicksort algorithm. Quicksort is O(nlg(n)).

 

[John C. Bollinger]

true, but you take a hit on keeping the list sorted (since a one-time
sort takes you back to linear or worse I'd expect?)

Worse: a typical efficient sort is O(NlogN). I have even seen a sort
that scales linearly for uniformly distributed data, but the coefficient
of N in that case would probably be a couple of orders of magnitude
greater than that for the simple comparison loop.

 

[Wibble]

Quicksort is N log(n), but iterating the list is just O(n).

"Wannabee" <[email protected]> schreef in bericht


"Sharp"


Hi

I have an array of integers.
I would like to retrieve the maximum integer from that array.


Have you considered using
static void java.util.Arrays.sort (int[] a)



Overkill.

And woefully inefficient on modern hardware, too.
To take advantage of SMP systems, CMT processors, even
hyperthreaded(tm) machines, you need some parallelism.
Here's the approach I'd recommend:

- If there are N numbers in the array, launch N/2
threads and give each thread two of the numbers.
Each thread's job is to compute the larger of the
two numbers it's been given. (If N is odd, launch
one extra thread to compute the larger of the final
value and Integer.MIN_VALUE.)

- When all N/2 threads have terminated, collect the
N/2 "first round winners" that they computed. You
have reduced the problem size by half, the first
step of a classic divide-and-conquer strategy.

- Now launch N/4 threads, handing each of them a pair
of the "first round winners." Collect their N/4
results and launch N/8 threads to compute the winners
of the next round, and so on until you finish up by
running N/N == 1 thread to compute the larger of the
two "semifinalists:" the Grand Champion.

This requires only ceil(lg(N)) stages, with each stage
except the final few exploiting all the computing resources
on the system toward the solution of the problem. That's
why it's so much more efficient than the primitive single-
threaded O(N) methods suggested thus far, methods that
cannot hope to take advantage of today's machines.

;-)

java.util.Arrays.sort according to the documentation, uses a tuned
quicksort algorithm. Quicksort is O(nlg(n)).

 

[Chris Smith]

Worse: a typical efficient sort is O(NlogN). I have even seen a sort
that scales linearly for uniformly distributed data, but the coefficient
of N in that case would probably be a couple of orders of magnitude
greater than that for the simple comparison loop.

Of course, if we want to start off in that direction, we'd soon abandon
the plan to use a sort, per se, and replace it with a heap data
structure. Adding data to a heap is O(log N), and finding the maximum
value is still O(1). A binary dense heap may be easily maintained in an
array with no additional storage overhead. If finding the maximum value
is the most important or performance-critical operation on the
structure, it's definitely worth it to get O(log N) rather than O(N)
performance.

Of course, this is a specific instance of the more general concept.
Exactly how efficient the code can be made depends on the information
available about the numbers. For example, if I know that numbers will
only be added and never removed, then I can give you the maximum in O(1)
time with O(1) additions and constant additional space requirement as
well!

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation