0

На данный момент я изучаю простейшие алгоритмы поиска и указатели, в связи с чем у меня возник вопрос:

Как можно ускорить данный алгоритм поиска наибольшего значения в элементах массива?

int array[]{ 1,4,6,2};

    int max = 0;
    
    for (auto i : array)
    {
        if (i > max) max = i;
    }
    
std::cout << max;
  1. У меня были мысли преобразовать объявляемый элемент (i) в указатель, чтобы принимать адрес ячейки массива, но в цикле for-each, видимо, это невозможно.

  2. Также была идея преобразовать (int max) в указатель, чтобы хранить адрес объявляемого элемента (i), но чтобы произвести первое сравнение max и i, max должен указывать на какое-то значение.

Понимаю, что скорее всего есть готовое решение в STL бибилиотеке, однако моя дотошность не дает покоя. Есть ли смысл вообще думать на эту тему?

32
  • 3
    На эту тему есть смысл думать, чтобы не написать плохой алгоритм. Что бы вы не писали, придется рассматривать все элементы и придется сравнивать или явно или под "капотом". Так что для данного случая лучше не напишете. Для встроенных типов ссылка только ухудшит. Подсказка от Павел Ериков не верна 27 янв 2021 в 8:34
  • 8
    @ReturnNullprt поиск максимума - это задача которая решается за O(n). можно пытаться ускорить, пытаясь "перехитрить компилятор", но в большинстве случаев это только ухудшит скорость. Одно дело, если в массиве большие объекты (размером десятки байт) - там указатели/ссылки/итераторы помогут (просто не копировать без причины), но для примитивных типов - нет. Но если исполльзовать специальные инструкции процессора, к примеру _mm512_max_epi32, то можно по 16 элементов за один раз сравнивать и получить прирост.
    – KoVadim
    27 янв 2021 в 8:47
  • 5
    @SelfishCrawler Ваш тест не верный, sizeof ссылки выдаст размер типа
    – Jester
    27 янв 2021 в 8:53
  • 3
    По-моему, быстрее, чем int max = array[0]; for(int i = 1; i < size(array); ++i) if (max < array[i]) max = array[i]; ничего не сделать. Разве что распараллеливать или векторизовать - но это сработает только на реально больших массивах.
    – Harry
    27 янв 2021 в 9:01
  • 2
    главное, что бы массив не был пустой, @Harry
    – KoVadim
    27 янв 2021 в 9:02

1 ответ 1

1

Попробую собрать в едино все споры из комментариев.

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

  1. Указание auto даёт свободу компилятору, и он сможет делать с переменной что захочет, например задействовать регистр процессора (они самые быстрые), а не создавать её в стеке. Это и есть ускорение. Так же это "сигнал" оптимизатору, который возможно применит тут оптимизацию которую он умеет делать. Возможно указание register вместо auto даст тот же результат, несколько лет назад отдельные источники рекомендовали register.

  2. Использование SSE MMX. Есть определенный набор команд, который позволяет, например сравнивать одновременно 4 пары чисел за одну инструкцию. При колличестве данных думаю от 1000 штук, это даст эффект. Писать нужно на ассемблере, и такой набор команд должен быть на процессорах у того - кто будет использовать программу. Т.е. или intel/amd или свежий intel/amd, не ARMv7 и т п.

  3. Использование встроеных в ЦП операций большей разрядности над данными меньшей разрядности. Например 32-битных или 64-битных операций над 8-битными числами. Если массив у вас 8-битный беззнаковый, то применив тест допустим *((int*)(a + i)) & 0xF0F0F0F0 (что равно *((int*)&a[i]) & 0xF0F0F0F0) вы можете проверить, содержит ли двойное слово байты больше чем 15 (0xFF-0xF0 = 0xF = 15) или не содержит. Если не содержит - то условно не делать поиск внутри этих 4-х байт раздельно сэкономив 3-ри инструкции сравнения, иначе итого 1+4=5 инструкций (вместо 4) + накладные расходы. При определённых условиях это может дать небольшой прирост производительности. Возможно можно ещё придумать похожую "хитрость" игры с битами.

  4. Отказ от цикла улучшает производительность. Если к-во елементов в цикле внутри алгоритма - константа и оно малое, где-то до 20 или до 100 элементов (я так думаю, возможно и до 1000) - то можно составить древесную условную структуру, для поиска максимума без цикла, что даст ускорение. В этом поможет тернарный оператор.

    #define MAX2X(a,b) ((a>b)?a:b)
    // тогда
    max = MAX2X(a[0],a[1]); // для  двух
    max = MAX2X(MAX2X(a[0],a[1]), a[2]); // для трёх
    max = MAX2X(MAX2X(a[0],a[1]), MAX2X(a[2],a[3])); // для чётырёх
    

Универсальный поиск можно сделать через template. В template-аргументы можно подставлять константы.

template<typename T, size_t N>
T FindMax(T (&a)[N])
{
  switch (N) {            
      case 2: return MAX2X(a[0],a[1]);
      case 3: // .....
      // и так далее
      default:
         // assert-ошибка
         ;
      }
}

Учтите что такое ускорение приводит к разрастанию кода. До определённого момента ускорение будет расти, но после критического значения будет падать.

Может ли оптимизатор сам сгенерироваь такое из примера который в вопросе - сомневаюсь.

  1. Если уже зараннее извесно что массив осортирован - то максимум - крайний элемент. (Если по-возрастанию - то последний элемент).

  2. Если данных более 10000 то распараленый поиск (т.е. ответ ищёт несколько ядер процессора - посредством threads) - даёт результат лучше чем линейный.

  3. Из пожеланий, отдельные методы поиска можно применить используя библиотечную std::max_element

Некоторые из этих методов можно смешивать вместе, что даст ещё больше вариантов найти максимум, некоторые из смешений могут быть эффективны.

Из ошибок. max=0 - так при поиске максисмума не принято делать. Конкретно в даном случае это сработает, но в будущем это может привести к багам, незачёту, да и каждый кто увидет такой "почерк" скажет что вы непрофессионал в плохом смысле слова.

UDP Также была идея преобразовать (int max) в указатель Если max сделать указателем, то для проверки указатель прийдётся привести к неуказателю, а это дополнительная операция. Поэтому вместо четырёх сревнений с регистром будет операция памяти получения значения по-указателю, а потом сравнение из памяти - итого 8 (минимум) операций с памятью вместо 4. Поэтому вместо ускорения вы получите наоборот - замедление, раза в 1,5-2. Если L0 кеш имеет скорость регистров (не уверен) то есть шанс получить ту же скорость.

P.S. Используйте обычный линейный цикл, или библиотечную функцию. А ускорение - ускорение есть смысл делать только если вы анализируете очень большие обьёмы данных, там пишите компрессор/декомпрессор, или анализ больших массивов данных, или что-то где скорость имеет важное значение.

7
  • 2
    Поиск максимума в отсортированном массиве двоичным поиском?..
    – wololo
    27 янв 2021 в 11:09
  • 1
    Я понял))))))))
    – nick_n_a
    27 янв 2021 в 11:19
  • 2
    Ещё есть стандартный std::max_element, который, теоретически, должен быть максимально оптимизирован, и ему можно передавать execution policy, чтобы он ещё и параллельно выполнялся.
    – wololo
    27 янв 2021 в 11:22
  • 4
    @Стас, думаю, что замена &a[i] на (a + i) вообще никакого прироста не даст. Что-то вы совсем плохого мнения о компиляторах :)
    – wololo
    27 янв 2021 в 11:48
  • 1
    @Стас часть программистов любят первую форму записи, часть - вторую форму записи, не всем кто любит первую понятна вторая и наоборот. Они равнозначны, потому что в обеих случаях берётся адрес элемента вначале. Я предпочитаю через a[i]. Но оставлю обе формы.
    – nick_n_a
    27 янв 2021 в 11:49

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.