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
}
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