Блог

#c #optimization #minimum

#c #оптимизация #минимальный

Вопрос:

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

Комментарии:

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

2. Было бы еще лучше инициализировать min_cost и second_min_cost первыми двумя элементами массива, начиная цикл с i = 2. (Это, конечно, при условии, что массив содержит как минимум два элемента.)

3. Я думаю, что многое зависит от того, что get_ith_element_from_array делает. Если он действительно обращается к массиву такого размера width , то вам следует подумать о поведении кэша (и, в частности, если вы зацикливаете более 10 КБ памяти миллионы раз, тогда, вероятно, есть некоторое перекрытие, поэтому наиболее важной оптимизацией может быть выбор наилучшего порядка для 2 или 3 циклов за пределами этого).). Если он вычисляет значение из i , то производительность памяти вполне может быть совершенно неуместной.

4. Стив, ‘get_ith_element_from_array’ — это следующее: » return m[global_j][i] - n[i] »

5. @osgx: Итак, если global_j изменяется между различными запусками этого внутреннего цикла, то вы потенциально могли бы получить хорошую оптимизацию, гарантируя, что запуски с равными значениями global_j выполняются последовательно. Таким образом, m[global_j] все равно будет кэшироваться при повторном использовании.

Ответ №1:

 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
  

Комментарии:

1. 1, вы правы, я неправильно прочитал документацию. Если я думал, что это O(n * log(n / 2)), используя это: (last-first)*log(middle-first). Но середина — это не n / 2, а скорее 2 в вашем случае, что просто соответствует O (n). Итак, ваше решение оптимально.

2. @sehe: поскольку ему нужны два наименьших значения, я думаю, partial_sort это лучше, чем nth_element , поскольку он вернет два за один выстрел.

3. @MatthieuM.: Я прочитал вопрос. Тем не менее, я оставляю здесь немного пространства для маневра в XY-вопросе . Кто знает, что на самом деле делает точка доступа? (Кроме того, я думаю, что я сделал это довольно ясно из моего ответа)

4. сехе, другие части программы слишком сложно изменить (и она уже была написана опытным студентом acm / ICPC), поэтому я спросил об этой небольшой части XY.

5. @Matthieu M.: std::nth_element также вернет два за один выстрел и линейное время. Компромисс с std::nth_element заключается в том, что порядок в поддиапазонах не гарантируется. В этом случае слева находится только один элемент, и он должен быть меньше или равен второму.

Ответ №2:

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

Комментарии:

1. Хорошее предложение. Предполагая хорошо перемешанный набор значений, это должно немного ускорить процесс. Худшая производительность в случае, когда массив отсортирован в совершенно неправильном порядке, и в этом случае это не хуже, чем код OPS.

2. @DavidHammen Нет, в лучшем случае выполняется 1/2 ifs, в худшем случае выполняется 2 ifs. В конце концов, это уравновешивает.

Ответ №3:

Комментарии:

1. «оставшиеся элементы (менее 8) должны быть обработаны вне цикла — развернуты …» — и устройство Даффа в начале!

2. @Steve: Я думал, что устройство Даффа (и развертывание вручную) устарело из-за современных компиляторов 🙂 ?

3. @Matthieu: иногда ручная развертка (с или без Duff) обеспечивает более быстрый код, чем оптимизатор, для данного теста или для данного практического использования. Чего достигла современная технология оптимизации, так это того, что вы не можете с уверенностью предсказать, поможет это или нет, что примерно так же хорошо, как и получается, учитывая, что всегда будут патологические варианты использования, чтобы победить конкретную тактику оптимизации.

4. Стив Джессоп, как программист, который немного разбирается в работе компилятора, я могу сказать, что Duff device — это кошмар для компилятора, потому что он очень нелинейный (в графике потока управления). Большинство компиляторов пытаются обнаружить ошибки и вернуть их к нормальному циклу. Даже Xfree в какой-то момент заменил ВСЕ duff на простые циклы.

Ответ №4:

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

Ответ №5:

Ответ №6:

Комментарии:

1. OP явно заинтересован в оптимизации в пределах O(n) границы, 5 * n операций и 10 * n операций — это оба O(n) , но один явно быстрее другого. Простого анализа нотации big O здесь, по-видимому, недостаточно.

Ответ №7: