Поиск наименьшего числа в векторе

Question

Для вектора, содержащего более 5000 элементов (расстояний), каков самый быстрый способ определения наименьшего ненулевого значения? В настоящее время, у меня есть что-то наивные, как это:

double distance=1E10; //I know that my distances are always less than this 
for (unsigned int i=0; i< a.size(); i++){ 
    if (a.at(i) < distance && a.at(i) != 0){ 
    distance=a.at(i); 
    } 
} 

Я считал сортировкой вектор первый, а затем принимать первое ненулевое значение, но я надеялся, что кто-то может предложить еще быстрее оптимизированный подход.

Answer 1

auto min = std::numeric_limits<double>::max(); 
for(auto& v : a) { 
    if(v < min && v != 0) { 
     min = v; 
    } 
} 

Довольно прямо. Если вы можете сохранить отсортированную подборку, вы можете сделать лучше, чем O (n). Вы в настоящее время используете .at(), несколько раз, который выполняет проверку границ.

Answer 2

Некоторые простые и очень незначительные методы.

double best=1E10; //I know that my distances are always less than this 
for (unsigned int i=0; i< a.size(); i++){ 
    if (a[i] < best && a[i] != 0){ 
    best=a[i]; 
    } 
} 

double best=1E10; //I know that my distances are always less than this 
for (auto it = a.begin(); it!= a.end(); ++it){ 
    if (*it < best && *it != 0){ 
    best=*it; 
    } 
} 

Answer 3

Почему вы пытаетесь найти линейно в этом векторе? Это худший случай. Просто сортировать вектор затем найдите наименьшее значение. просто не так ли? проверить код:

предположим, что,

vector <int> v; // it contains values 5,4,1,2,3 
sort(v.begin(),v.end()); //STL sort function 

затем v [0] наименьшее значение = 1

Answer 4

Вы можете попробовать использовать std::sort и std::upper.

std::sort(vec.begin(), vec.end()); 
auto upper = std::upper(vec.begin(), vec.end(), 0.0); 
std::cout << *upper; 

Answer 5

Стандартная функция для этого:

auto min = *std::min_element(begin(distances), end(distances), 
    [](double a, double b) { return b==0 || a<b; });