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

Question

Имея, например, массив из 4 целых чисел, как определить его ненулевой минимум - самым быстрым способом?

Answer 1

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

Не существует «быстрого» способа тестирования каждого члена.

Обычно я советую не оптимизировать что-либо, если только оно не окажется медленным.Старое правило вашей программы тратит 90% своего времени на 10% кода, как правило, верно.То же самое можно сказать и о правилах, согласно которым программисты с вероятностью 99,99% могут оптимизировать код, а не на 10%.

Answer 2

Существует параллельное решение этой проблемы, но оно, вероятно, не стоит усилий.

Сначала мы определим операцию xchg(m, n) над массивом a :

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n])

Эта операция сортирует два элемента 'm' и 'n' в порядке возрастания, если они оба содержат ненулевые значения, или заменяет их, если значение в элементе 'm' равно нулю.

Затем мы выполняем набор из пяти таких операций следующим образом:

xchg(0,2) xchg(1,3)
xchg(0,1) xchg(2,3)
xchg(1,2)

Сопряженные xchg операции могут выполняться параллельно, что сокращает временные затраты на 40% по сравнению со строго последовательнымивыполнение.Когда мы закончим, все ненулевые элементы в массиве будут отсортированы в порядке возрастания.Элемент с наименьшим значением будет в [0].Если это значение равно нулю, в массиве нет ненулевых значений.

Это решение использует врожденный параллелизм, обеспечиваемый сетями сортировки (http://en.wikipedia.org/wiki/Sorting_network),, но также последовательно сканирует 4 элементаиспользует не более трех операций сравнения, и, что особенно важно, требует в среднем вдвое меньше операций записи в хранилище:

последовательное сканирование

int v = a[0]
for (n = 1; n < 4; n++) {
   if ((a[n] < v && a[n] != 0 ) || v == 0) v = a[n]
} 

Answer 3

Если мы думаем о микрооптимизации, то, возможно, было бы быстрее вычислить min(min(a,b),min(c,d)) вместо min(min(min(a,b),c),d) на современном процессоре с неправильным порядком из-за менее последовательных зависимостей: в первом процессор может независимо вычислять min(a,b) и min(c,d) параллельно, если для этого доступно достаточно исполнительных единиц. Это предполагает, что процессор имеет команду условного перемещения, так что вычисления min не требуют ветвления.

Answer 4

Зависит от входа. Если массив не отсортирован, вам придется перебирать весь массив. Если массив отсортирован, вам просто нужно выполнить цикл, пока не найдете что-то, что не равно нулю - оно намного короче.

Answer 5

Ну, самый быстрый способ кодирования это std::min({a,b,c,d}).

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

Параллелизм, вероятно, помог бы больше, чем попытка написать минимальную функцию в ассемблере.