Finding the highest values a and b from an array

Question

I struggled a short while to make this work, so I'm wondering if there are any smarter ways for finding the highest of two values per array element? Uh, hard to explain by words, but by code its easy:

Data (random):

    (a) (b) // a and b are both positive values.
    10  0.5
    13  10.8
    8   0.123
    9   0.123
    17  0.3
    17  0.4  <- must find this
    17  0.1
    0   0.13
    0   0.5

Code:

int max_a = -1;
float max_b = -1;

for(int i = 0; i < total_values; i++){
    if(values[i].a > max_a){
        max_a = values[i].a;
        max_b = -1; // reset
    }
    if(values[i].a == max_a){
        if(values[i].b > max_b){
            max_b = values[i].b;
            found_id = i;
        }
    }
}

So far it seems to work. But is this the most efficient way of doing this? (without changing the for loop; must loop linearly like that)

Edit: Some notes: I use std::vector for my arrays. The code should work with any struct given to the vector, only 2 of the elements from that struct will be used for value checking. Edit2: Values cannot have negative values, thats why there is initial -1 values set to mean "not set".

Edit: My test code:

struct valuestruct {
    int a;
    float b;
    // this could have more values than just two. still, only two values are tested.
    // using shortest struct as possible to save memory for testing.

    valuestruct(int a, float b) : a(a), b(b) {}
};

bool operator<(const valuestruct &v1, const valuestruct &v2){
    return (v1.a < v2.a) || ((v1.a == v2.a) && (v1.b < v2.b));
}


void test_speeds(){
    // initialize array values:
    int total_values = 10000000; // = 80megs ram
    vector<valuestruct> values;
    for(int i = 0; i < total_values; i++){
        values.push_back(valuestruct(random(0,1000), random(0.0f,100.0f)));
    }

    int found_id = -1;
    // dummy stuff for preventing loops optimized off:
    int ids = 0;
    int out_id1 = -1;
    int out_id2 = -1;
    int out_id = -1;

    // Loki's solution:
    float t1 = microtime();
    if(total_values > 0){ // prevent crash accessing empty array.
        for(int dummy_repeat = 0; dummy_repeat < 100; dummy_repeat++){
            valuestruct max = values[0];
            for(int i = 1; i < total_values; i++){
                if(max < values[i]){
                    max = values[i];
                    found_id = i;
                }
            }
            out_id = found_id;
            ids += found_id; // dummy
        }
        out_id2 = out_id;
    }
    float speed1 = microtime()-t1;

    // Keith's solution:
    float t2 = microtime();
    for(int dummy_repeat = 0; dummy_repeat < 100; dummy_repeat++){
        int max_a = -1;
        float max_b = -1;
        for(int i = 0; i < total_values; i++){
            if(values[i].a > max_a || (values[i].a == max_a && values[i].b > max_b)){
                max_a = values[i].a;
                max_b = values[i].b;
                found_id = i;
            }
        }
        out_id = found_id;
        ids += found_id; // dummy
    }
    out_id1 = out_id;
    float speed2 = microtime()-t2;

    clock_t t3 = clock();
    for(int dummy_repeat = 0; dummy_repeat < 100; dummy_repeat++){
        std::vector<valuestruct>::iterator find = std::max_element(values.begin(), values.end());
        found_id = std::distance(values.begin(), find);
        out_id = found_id;
        ids += found_id; // dummy
    }
    clock_t speed3 = clock() - t3;

    // Output:
    // Lokis: 6166.7ms
    // Keith: 3932.1ms


   // Timing on Loki's machine (using 1000 dummy iterations)
   // Compiled uisng g++ -O3 (replaced microtime() with clock())
   // Times are in seconds (result is the value of ids)
   Loki:  12.814812000 Result: 53500000
   Keith: 12.885715000 Result: 53500000
   Max:   12.832419000 Result: 53500000
}

Answer 1

What you are doing is just normal search for a max pair using lexicographical ordering.

The issue with your code is that, it is linear O(n). While for a single use, this might be the best way, if you have to do it repeatedly, it would be better to build a priority queue [O(n)] with the comparison operator defined as pair compare, and then extract the top. (Even better if you can build the priority queue as you receive the elements.)

The pair comparison is derived directly from the definition

(a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).

However you have mentioned the constraint that the loop shouldn't be changed. Is there a reason for that?

Answer 2

Real SOlution

typedef  std::pair<int, float>       Value;
typedef  std::vector<Value>          Values;

Values   values;
// Initialize all values;

// Then.
Values::const_iterator find = std::max_element(values.begin(), values.end());

// Want the raw index number for some strange reason.
int     index = std::distance(values.begin(), find);

// Note if you insist on using arrays rather than vectors then the C++11 version
//      works with vectors and arrays exactly the same way:
Value* find = std::max_element(std::begin(values), std::end(values));

// But if you insist on using arrays but are stuck with C++03
Value* find = std::max_element(&values[0], &values[size]);

Review of code

Neither of this is a minimum value.

int max_a = -1;
float max_b = -1;

So if your data happens to be all negative it will fail.

Unless there is some space concerns I do not see the point in using float. Prefer double the extra precision is usually worth it.

Why did you use two variables to hold the max. This is sort of an indication that you are looking for the max in each column separately. This is not the case so you should have a max value object.

Value   max = values[0]; // Initialize with first element.

OK. This is always going to be a linear algorithm O(n) as the data is not sorted. But prefer pre-increment ++i over post increment. Technically there will be no difference for POD types (like int) but it is a good habit to get into for when you start using other types to iterate across the array.

Personally I hate such short variables names. But I know other like it for looping. The problem is that if the loop gets to any non trivial size the looking for all occurrences of i becomes a pain the arse. It is much easier to spot a longer variable name.

for(int i = 0; i < total_values; i++){

All this is way to complex.

    if(values[i].a > max_a){
        max_a = values[i].a;
        max_b = -1; // reset
    }
    if(values[i].a == max_a){
        if(values[i].b > max_b){
            max_b = values[i].b;
            found_id = i;
        }
    }

• You don't need a found_id. If the container is empty then you will not find a max.
• Otherwise use the first element to initialize the max.
• The loop over the other elements (ie starting at 1)
• See below on how to do the test in one condition.

Algorithm should look like this:

    Value max   = values[0];
    for(int loop = 1; loop < size; ++loop)
    {
        max = std::max(max, values[loop]);
    }
    // Modified based on comments. To get index use:
    Value max   = values[0];
    int   index = 0;
    for(int loop = 1; loop < size; ++loop)
    {
        if (max < values[loop])
        {
             index = loop; 
             max   = values[loop];
        }
    }

Now all you need to do is define the relationship between elements. By default std::max() will use the operator< to do comparisons but you can define your own comparison operator if you want a non standard way of determining max.

If The type of Value (which holds your int/float) pair is actualy typedefed to std::pair<int, float> then this is the default behavior.

 // It would be equivalent to this
 bool operator<(Value const & lhs, Value const& rhs)
 {
      return     (lhs.first < rhs.first)
             ||  ((lhs.first == rhs.first) && (lhs.second < rhs.second));
 }

Answer 3

if(values[i].a > max_a || (values[i].a == max_a && values[i].b > max_b))
{
        max_a = values[i].a;
        max_b = values[i].b;
        found_id = i;
}

or...eliminating max_a and max_b

if(values[i].a > values[found_id].a || (values[i].a == values[found_id].a && values[i].b > values[found_id].b))
    {
            found_id = i;
    }