Author: Ricardo Gibert
Date: 08:36:16 01/04/05
Go up one level in this thread
On January 04, 2005 at 08:43:45, Antonio Senatore wrote:
>
>Hi friends:
>
>I need to find the index of the highest value in an array of N integer positive
>numbers. Does anyone know a faster algorithm than the following:
>
>int find_index (int *arr, int N) {
>
> int best_val = -INF, i, index;
>
> for (i = 0; i < N; i++) {
> if (arr[i] > best_val) {
> index = i;
> best_val = arr[i];
> }
> }
> return index;
>}
>
>Thank you very much in advance
>Antonio
The following little demo programs exploit the idea of using sentinels to avoid
2 tests in the main loop, i.e. in the above code, both i and arr[i] get tested
in each iteration. The following assumes that the array a[] contains few
duplicates values. It uses a tricky idea to avoid incurring a lot of overhead.
#include <stdlib.h>
#include <stdio.h>
int main(void)
{
int a[] = {3, 7, 16, 8, 9, -3, 7, 1}, max_value;
int const a_size = sizeof(a)/sizeof(a[0]), last_index = a_size - 1;
int i, j, max_value_index;
i = 0; j = last_index;
max_value = a[0];
while (1)
{
while (max_value > a[j]) j--;
max_value = a[j];
if (i == j) break;
do i++;
while (max_value > a[i]);
max_value = a[i];
if (i == j) break;
j--;
}
max_value_index = i;
printf("a[] = {%i", a[0]);
for (i = 1; i < a_size; i++) printf(", %i", a[i]);
puts("}");
printf("a[%i] = %i\n", max_value_index, max_value);
return 0;
}
The next one has a lot of overhead, but does not have the weakness of exiting
the inner loop when encountering a duplicate value. It also realizes a very nice
virtually *free* bonus of stopping when it finds a value equal to
max_possible_value without testing the remaining values in the array. For large
arrays it should do well. BTW, I realize it looks ugly as hell and I do not
recommend this approach for readability reasons.
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
int main(void)
{
int a[] = {3, 7, 9, 8, 6}, max_value, last_value;
int const a_size = sizeof(a)/sizeof(a[0]), last_index = a_size - 1,
int const max_possible_value = INT_MAX; /* set this as low as possible */
int i, max_value_index;
max_value_index = last_index;
max_value = a[max_value_index];
if (max_value != max_possible_value)
{
last_value = a[last_index]; /* save last value for later restore */
a[last_index] = max_possible_value; /* guarantees trigger of stop
condition */
i = 0;
while (1)
{
while (a[i] <= max_value) i++;
if (a[i] == max_possible_value) /* will be true only once */
{
if (i < last_index) /* false new max on i == last_index */
{
max_value_index = i;
max_value = max_possible_value;
}
break; /* from while (1) */
}
max_value_index = i;
max_value = a[max_value_index];
i++;
}
a[last_index] = last_value;
}
printf("a[] = {%i", a[0]);
for (i = 1; i < a_size; i++) printf(", %i", a[i]);
puts("}");
printf("a[%i] = %i\n", max_value_index, max_value);
return 0;
}
I would suppose the above could be further improved with loop unrolling. Also, I
haven't gotten around to benching the above, so I really don't know how
worthwhile they are.
I have a strong bias for the most easy to understand way which is the one you
gave. Imagine someone else trying to read your program and running up against
the last one above. Instead of finding the code they expect and taking a matter
of seconds to understand it, they find themselves having to spend about a
hundred times longer to understand the above horror.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.