Finding the max number in a list

[Eric Sosman]

Chris Smith wrote:




I certainly assumed it was a joke. For that reason I chose to not point
out (there) that the sum of 1/2 + 1/4 + 1/8 + ... is 1, thus his
algorithm was still O(N), as opposed to O(logN) as he claimed. Even if
you inverted it so that you initially started just two threads, one for
each half of the array, and they each started two threads, etc., you
still end up with a number of comparisons governed by that same sum, and
hence having no better than linear complexity.

Not if you have enough parallelism. If you've got at
least N/2 CPUs, each "stage" can run all its threads in
parallel and take no more time than running just one thread.
There are ceil(lg(N)) stages in all, hence logarithmic and
not linear complexity.

My method will find the maximum of Chris' 20000 elements
in just 15 steps -- on a 10000-CPU machine ...

 

[John C. Bollinger]

Not if you have enough parallelism. If you've got at
least N/2 CPUs, each "stage" can run all its threads in
parallel and take no more time than running just one thread.
There are ceil(lg(N)) stages in all, hence logarithmic and
not linear complexity.

Granted, efficient use of hardware parallelism can reduce the clock time
consumed, and arguably that may be the most relevant metric.
Parallelism does nothing for the total CPU time consumed overall,
however, so whether the approach is linear or logarithmic depends on the
resource you consider.

 

[John C. Bollinger]

Patricia Shanahan wrote:

However, in this case we are sorting ints, which are known
to be numbers in a bounded range, so a radix sort is
possible and is O(n).

Ah, yes. I should have thought of that myself (too used to thinking of int-s
as a reasonably approximation to integers -- silly).

Come to think of it, a bucket sort (if that's the right name) could do it too,
although the space overheads (2**32 elements-worth of int[] arrays) would make
it a little impractical. (Unless the range if ints were known to be more
severely limited than to just the 32-bit range).

But neither algorithm sounds as if it's the one that John was talking about --
unless the "uniform distribution" precondition he mentioned was to allow most
of the steps of a radix sort to do some useful partitioning.

I have lost the reference (and indeed, my test implementation), but the
sort in question is more or less an in-place bucket sort. First it
computes a histogram with dynamically-determined (but uniform) bucket
width (requiring two linear scans of the array), then it uses the
histogram to assist in a round-robin style element permutation so that
the elements of each histogram bucket end up consecutive in the array
and bucket-wise in the correct sort order (each element is moved at
most once), and finally it follows up with an insertion sort of the
nearly-sorted array (equivalently: an insertion sort of each bucket).

It's that last step that's the problem: if the array elements are
distributed roughly uniformly, then the number of elements for any
bucket (and hence the total time / comparisons for any bucket) can be
bounded by a small positive number, thus the insertion sort performs
linearly with respect to the total number of elements. If, however, the
distribution is highly non-uniform, then the O(N*N) complexity of the
insertion sort can kick in on one or a few buckets that contain the
majority of the elements.

The problem with non-uniform value distributions might be addressable by
using nonuniform bucket widths, but then I don't see how you assign a
value to its bucket in constant time (as required for linear scaling of
this algorithm) -- you'd have to perform some kind of lookup.

Well, there you are, probably more than you wanted to know.

 

[steve]

Not if you have enough parallelism. If you've got at
least N/2 CPUs, each "stage" can run all its threads in
parallel and take no more time than running just one thread.
There are ceil(lg(N)) stages in all, hence logarithmic and
not linear complexity.

My method will find the maximum of Chris' 20000 elements
in just 15 steps -- on a 10000-CPU machine ...

good job Chris has a 20,000 CPU machine then.

Steve

 

[Dale King]

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.

In addition to all the other fun discussions on algorithm efficiencies I
thought I would add that there is a nice little algorithm if you need to
find both the min and the max at the same time. It requires only 1.5n
comparisons over the 2n comparisons for the brute force method
consisting of 2 loops like yours above.

You can see the pseudocode for it here:

http://en.wikibooks.org/wiki/Computer_Science:Algorithms:Chapter_4#find-min-max

 

[Chris Uppal]

Well, there you are, probably more than you wanted to know.

No indeed. I can't think of a use for the algorithm off-hand, but it's always
nice to know about algorithms beyond the "normal" set.

Thanks.

-- chris