Самый быстрый способ найти два минимальных элемента int64 в массиве

Question

У меня есть массивы с размерами от 1000 до 10000 (1k .. 10k).Каждый элемент int64.Моя задача состоит в том, чтобы найти два наименьших элемента из массивов, минимальный элемент и минимальный из оставшихся.

Я хочу получить максимально быстрый однопоточный код на C ++ для Intel Core2 или Corei7 (режим процессора равен 64немного).

Эта функция (получение 2 самых маленьких из массива) является горячей точкой, она вложена в два или три цикла с большим числом итераций.

Текущий код выглядит так:

int f()
{
    int best; // index of the minimum element
    int64 min_cost = 1LL << 61;
    int64 second_min_cost = 1LL << 62;
    for (int i = 1; i < width; i++) {
     int64 cost = get_ith_element_from_array(i); // it is inlined
     if (cost < min_cost) {
        best = i;
        second_min_cost = min_cost;
        min_cost = cost;
     } else if (cost < second_min_cost) {
        second_min_cost = cost;
     }
    }
    save_min_and_next(min_cost, best, second_min_cost);
}

Answer 1

Посмотрите на partial_sort и nth_element

std::vector<int64_t> arr(10000); // large

std::partial_sort(arr.begin(), arr.begin()+2, arr.end());
// arr[0] and arr[1] are minimum two values

Если вам нужно только второе наименьшее значение, nth_element - ваш парень

Answer 2

Попробуйте инвертировать if:

if (cost < second_min_cost) 
{ 
    if (cost < min_cost) 
    { 
    } 
    else
    {
    }
} 

И вам, вероятно, следует инициализировать min_cost и second_min_cost с одним и тем же значением, используя максимальное значение int64 (или даже лучше использовать предложение qbert220)

Answer 3

Некоторые мелочи (которые, возможно, уже происходят, но, может быть, стоит попробовать)

1. Немного разверните цикл - скажем, например, итерация с шагом 8 (т.е. строка кэша за раз), предварительная выборка следующей строки кэша в теле, затем обработка 8 элементов. Чтобы избежать множества проверок, убедитесь, что конечное условие кратно 8, а оставшиеся элементы (менее 8) должны обрабатываться вне цикла - развернуто ...

2. Для предметов, не представляющих интереса, вы делаете две проверки в теле, может быть, вы можете урезать до 1? то есть, если cost меньше second_min, то также проверьте min - иначе не нужно беспокоиться ...

Answer 4

Вам лучше сначала проверить second_min_cost, так как это единственное условие, которое требует изменения результата.Таким образом, вы получите одну ветку вместо 2 в ваш основной цикл.Это должно немного помочь.

Кроме этого, оптимизировать очень мало, вы уже близки к оптимальному.Развертывание может помочь, но я сомневаюсь, что оно даст какое-то существенное преимущество в этом сценарии.

Итак, оно становится:

int f()
{
    int best; // index of the minimum element
    int64 min_cost = 1LL << 61;
    int64 second_min_cost = 1LL << 62;
    for (int i = 1; i < width; i++) {
    int64 cost = get_ith_element_from_array(i); // it is inlined
    if (cost < second_min_cost)
    {
      if (cost < min_cost) 
      {
        best = i;
        second_min_cost = min_cost;
        min_cost = cost;
      } 
      else second_min_cost = cost;
    }
    save_min_and_next(min_cost, best, second_min_cost);
}

Answer 5

Убедитесь, что ваше чтение массива ведется по собственному желанию, чтобы оно не приводило к ненужным промахам кэша.

Этот код, вероятно, должен быть очень близок к полосе пропускания на современных процессорах: при условии, что чтение массива простое.Вам нужно профилировать и / или рассчитать, если он все еще имеет запас для оптимизации процессора.

Answer 6

Хорошо, что ваш алгоритм сканирует числа один раз. Ты оптимален.

Важным источником медлительности может быть то, как устроены ваши элементы. Если они находятся в массиве, я имею в виду массив C (или вектор C ++), где все элементы являются смежными, и вы сканируете их вперед, тогда в отношении памяти вы тоже оптимальны. В противном случае у вас могут быть некоторые сюрпризы. Например, если ваши элементы находятся в связанном списке или разбросаны, то вы можете получить штраф за доступ к памяти.

Answer 7

То, что у вас есть, это O(n) и оптимально для случайных данных. Это означает, что у вас уже есть самый быстрый.

Единственный способ улучшить это - присвоить массиву определенные свойства, например, постоянно сортировать его или создать кучу.