3
\$\begingroup\$

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
}
\$\endgroup\$
  • \$\begingroup\$ Do you have max_bounds for either a or b? That is other than max_int? \$\endgroup\$ – rahul May 30 '12 at 15:33
  • \$\begingroup\$ @blufox, no other bounds than the values cant be < 0. both of the values wont exceed 1000000, im sure about that, if that matters. \$\endgroup\$ – Rookie May 30 '12 at 16:02
  • \$\begingroup\$ I was wondering if you could use some thing like (a << 20) + b > (a' << 20) + b' as the comparison perhaps?. \$\endgroup\$ – rahul May 30 '12 at 16:18
  • \$\begingroup\$ @blufox, no no no... this must work for any datatype. basically im just finding better if-structures there. if possible. \$\endgroup\$ – Rookie May 30 '12 at 16:51
  • \$\begingroup\$ I was thinking, if the a was float value, should i compare equality? I heard that same value in float can be represented in many ways or something like that, so equality wont always work... \$\endgroup\$ – Rookie May 30 '12 at 17:02
1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ The loop cannot be changed because i dont want to add any more complexity there, keeping it simple; i can later optimize it myself. I will probably optimize this by quadtrees (these objects are in 2d world); i would still have to loop linearly, but that doesnt hurt much on performance. \$\endgroup\$ – Rookie May 30 '12 at 16:12
1
\$\begingroup\$

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));
 }
\$\endgroup\$
  • \$\begingroup\$ Will this work? I need to find the array index, not the array values. Interesting solution though! \$\endgroup\$ – Rookie Jun 1 '12 at 10:59
  • \$\begingroup\$ @Rookie: It already does that. std::max_element returns an iterator the max element. Which can be the index if you are using raw arrays (which is bad idea use a vector). \$\endgroup\$ – Martin York Jun 1 '12 at 11:16
  • \$\begingroup\$ Unfortunately your code is twice as slow as the code made by Keith. I didnt test your distance() solution yet, though, but im not sure will it even work; I should also mention that i cant use std::pair here, because my struct is larger than just a pair, and the code should work with any struct. PS. i do use vectors. \$\endgroup\$ – Rookie Jun 1 '12 at 11:38
  • \$\begingroup\$ @Rookie: If you think my code is twice as slow as anything then you are doing something wrong. The STL algorithms are very efficient. So add to your question what you wrote and how you tested it. so we can point out your mistakes. \$\endgroup\$ – Martin York Jun 1 '12 at 11:42
  • \$\begingroup\$ @Rookie: If you use vectors then that should be part of the code you have in your question! \$\endgroup\$ – Martin York Jun 1 '12 at 11:43
0
\$\begingroup\$
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;
    }
\$\endgroup\$
  • \$\begingroup\$ Your latter code isnt right. How could it, when it doesnt remember the previous value? (i tested it and it doenst work). Your first code works so far, im not sure why though.... need to think more. \$\endgroup\$ – Rookie Jun 1 '12 at 10:41
  • \$\begingroup\$ I'm surprised, your first version is 30% faster. \$\endgroup\$ – Rookie Jun 1 '12 at 10:57
  • \$\begingroup\$ second one doesn't try to remember it just uses the index location of the highest value and compares new values against that, never tested it though \$\endgroup\$ – Keith Nicholas Jun 2 '12 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.