Поскольку я до этого жил в теплом мире фреймворков и библиотек и перед мной никогда не стояло подобных задач я был слегка удивлен такой лабе. В общем не смотря на числительные попытки преподавателя натолкнуть меня на правильное решение фразами вроде “числа ограниченны диапазоном от 0 до 100” и “можно использовать больше одного массива” найти решения не удалось, по крайней мере за период пары. В общем говоря пара закончилась тем, что за 5 минут до ее окончания задания про сортировку было замененною каким-то пустяком вроде подсчета количество разных цифр в числе.
И как иногда случается, вместо того что бы счастливо забыть про эту лабараторку и продолжать радоваться жизни я время от времени возвращался к задачи сортировки, и все таки придумал ее решение. Собственно им и хочу с вами поделиться. Оно вышло на удивления простым и без использования дополнительных массивов(поэтому скорей всего у задачи существует еще одно решение, наверное).
Вот собственно говоря код программы:
#include <iostream>
using namespace std;
int myAbs(int a){
int oldByte = (a >> 31)& 0x1;
return -a*(1+oldByte-1)-a*(oldByte-1);
}
int getMax(int a, int b) {
return (a + b + myAbs(a - b)) / 2;
}
int getMin(int a, int b) {
return (a + b - myAbs(a - b)) / 2;
}
int main() {
int arr[] = {34, 12, 24, 65, 63, 22};
int arraySize = (sizeof(arr) / sizeof(*arr));
int maxPosition = 0;
int maxElement = arr[0];
int minValue= arr[0];
for (int k = 0; k < arraySize; k++) {
for (int i = k; i < arraySize; i++) {
int newMax = getMax(maxElement, arr[i]);
minValue = getMin(minValue, arr[i]);
maxPosition =getMin((myAbs(newMax ^ maxElement) + 1) * (maxPosition + 1), (myAbs(newMax ^ arr[i]) + 1) * (i + 1)) -1;
maxElement = newMax;
}
int buf = arr[k];
arr[k] = maxElement;
arr[maxPosition] = buf;
maxElement = minValue;
}
for(int a:arr){
cout<<a<<endl;
}
return 0;
}
P.S. В универе бывает даже интересно.
Комментарии (71)
NeoCode
30.10.2015 20:39+4Кстати, в реальной практике столкнулся с тем что иногда алгоритмы без if'ов могут быть полезны. При разработке прошивки для микроконтроллера обнаружилось (реально, осциллографом) что наличие if'ов в процедуре обработки прерывания существенно замедляет эту самую обработку. Ну и оказалось проще придумать и написать нечто на арифметических и битовых операциях, но без условных переходов.
ZnW
30.10.2015 20:48+2Не знаю, насколько это применимо к «реальной практике», но:
Когда писал свой буфер глубины для изометрического движка, который строился на обработке пикселей процессором (велосипед от скуки, развлекал себя), как раз пригодилась замена if'а, выкидывающего пиксель, на нехитрую формулу с альфой двух пикселей. Прирост был, т.к. пикселей было много (:
BelBES
30.10.2015 21:08+6Еще бывает полезно избавиться от if'ов для того, чтобы немного помочь предиктору ветвлений.
stychos
31.10.2015 01:18Но разве циклы не генерируют те же compare+jump, что и if? Или при частом повторении процессору это легче делать, можете пояснить неучу?
zo_oz
31.10.2015 01:39+3Вот тоже самое хотел написать, выход из цикла в любом случае будет jnz/jz или loop по cx/ecx/итд
Можете пояснить чем это отличается от if?
p.s. код платформозависим) кто вам сказал что в int 32 разряда?stychos
31.10.2015 01:45Ну я в ассемблере совсем не силён, потому написал абстрактно — compare+jump. В детальностях архитектур тем более (и к сожалению) не разбираюсь, потому уж как написал, так и получилось =)
kosmos89
31.10.2015 15:14+1В современных процессорах есть предсказатель ветвлений, который накапливает статистику по jump'ам и спекулятивно выполняет ту ветвь которая до этого часто выполнялась. Поэтому если сброс конвейера и будет, то только на первой-второй итерации.
В более старых процессорах без предиктора, но со спекулятивным выполнением просто считалось, что jump назад всегда будет выполняться (потому что это очень похоже на цикл), а jump вперед — нет (потому что это похоже на выход из цикла).
DaylightIsBurning
31.10.2015 12:10+2if очень сильно бьют по производительности в OpenCL, там по сути просто выполняются все ветки кода и потом просто ненужные выкидываются…
Torvald3d
01.11.2015 12:51и не только огл, а практически на любой simd архитектуре
Torvald3d
02.11.2015 11:17Поясните, кто не согласен — где я ошибся? При simd архитектуре выполняется одна команда сразу над всеми нитями в варпе, соответственно ветвление возможно только в одном случае — когда этот варп прогоняется по всем веткам.
kosmos89
02.11.2015 12:21На самом деле не всегда. Если в варпе все нити пойдут по одной и той же ветке, то никакого пеналти не будет.
vagran
31.10.2015 16:04+1Это очень актуально при написании шейдеров. Открывая статью, даже ожидал увидеть, что речь идёт о работе с GPU. А ветвления там не приветствуются из-за того, что код выполняется параллельно на сотнях ядер. Если один и тот же код выполняется на разных ядрах разное время, то выполняется дорогая синхронизация.
zelyony
30.10.2015 20:50+7https://graphics.stanford.edu/~seander/bithacks.html
DanmerZ
31.10.2015 14:32-1Спасибо за ссылку!
pehat
31.10.2015 14:45Как говорила моя учительница, 3 я ставлю тем, кто может обменять две переменные, 4 — тем, кто делает это через XOR, 5 — тем, кто может объяснить, почему так делать не надо.
SWAP(x, x)DanmerZ
31.10.2015 14:52Рад за вашу учительницу, но по ссылке сборник хаков, а не руководство к действию :)
ankh1989
01.11.2015 01:50-3SWAP(x, x) это типа контрпример такой? Никто так писать никогда не будет, поэтому на этот сферический контрпример в вакууме (вращающийся где то на орбите между Землей и Марсом) никто никогда не наткнётся. А вот SWAP(x, y) работает даже когда x = y, лишь бы это разные переменные были.
geovas333
30.10.2015 20:57+5Надо бы взять на вооружение, когда рассказывать уже нечего, а до конца занятия времени валом!
p.s. что-то код у вас длинноват.a = [5,7,3,2,7,9,8] def bsort(x): for i in range(len(x)): for j in range(len(x)-1): a = x[j] b = x[j+1] x[j] = int ((a+b)/2.0 - ((a-b)**2)**0.5/2.0) x[j+1] = int ((a+b)/2.0 + ((a-b)**2)**0.5/2.0) return x print a print bsort(a)
lair
30.10.2015 21:02+1А вот если известно, что числа не повторяются, то можно решить за O(N).
Как-то такlet ub = 100 let sort (input: _[]) = let founds = Array.zeroCreate ub input |> Array.iter (fun e -> founds.[e] <- 1) let output = Array.zeroCreate (input.Length + 1) founds |> Seq.indexed |> Seq.scan (fun (prevPos, _) (i, v) -> let pos = prevPos + (1*v) let target = pos*v (pos, i) ) (0, 0) |> Seq.iter (fun (pos, i) -> output.[pos] <- i) output |> Array.skip 1lair
30.10.2015 21:07+1Исправленный кодlet sort (input: _[]) = let founds = Array.zeroCreate ub input |> Array.iter (fun e -> founds.[e] <- 1) let output = Array.zeroCreate (input.Length + 1) founds |> Seq.indexed |> Seq.scan (fun (prevPos, _, _) (i, v) -> let pos = prevPos + (1*v) let target = pos*v (pos, target, i) ) (0, 0, 0) |> Seq.iter (fun (_, pos, i) -> output.[pos] <- i) output |> Array.skip 1lair
30.10.2015 21:24Ну да, а если решать для повторяющихся, то общий случай оказывается проще. Shame on me.
Уупсlet sort input = let founds = Array.zeroCreate ub input |> Seq.iter (fun e -> founds.[e] <- founds.[e] + 1) founds |> Seq.indexed |> Seq.collect (fun (i, v) -> Seq.replicate v i) |> Seq.toArrayhalyavin
30.10.2015 21:08+5Вы не смогли додуматься до сортировки подсчётом?
geovas333
30.10.2015 21:18-1Это как-то так?
Скрытый текстa = [5,7,3,2,7,9,8] def psort(x): b = range(100) c = [] for i in range(len(b)): b[i] = 0 for i in range(len(x)): b[x[i]] += 1 for i in range(len(b)): for j in range(b[i]): c.append(i) return c print a print psort(a)
Mirn
30.10.2015 21:46+1статья конечно хороша как эксперимент.
Так можно не только для ифов делать и всю логику линейной сделать.
Я ранее подобное описывал в каментах.
НО
я как то наталкнулся на свой код 15 летней давности… больше я так делать не буду никогда ни прикаких условиях как бы задача оптимизации не стояла. Код который нельзя исправить через 5-10 лет когда ты вообще забыл ЧТО ЭТО мне больше не нужен.
Даже если есть задача оптимизации и надо выжимать буквально байты, то можно делать это средствами самого языка не уродуя понимание и смысл.
А в микроконтроллерах уже есть неявное устранение IF. Например в ARM Cortex Mx инструкции с предикатами — часть инструкций испольняются если выставлен флаг а часть нет. Даже если этого не хватает то можно применить чёрную магию (для Россиян): например научить DMA и железо писать или читать данные аппаратно напрямую в lock-free очередь — экономиться и размер и скорость повышается. Причём в разы повышается. Так например поступил WIZNET в своих езернет чипах. Есть бит бандинг, алиасы регионов, аппаратные ускорители и прочие шалости. Все они неплохо заменяют то что описано в статье и совсем не портят сам исходник.
nikitasius
31.10.2015 02:02-4Поскольку я до этого жил в теплом мире фреймворков и библиотек
Прямо бальзам на сердце противнику фреймворков!
raid
31.10.2015 10:07В myAbs какая-то тёмная магия. Можете пояснить, как оно работает?
Braiko
31.10.2015 10:24-1Это работает для платформ, где int занимает 4 байта.
int oldByte = (a >> 31)& 0x1; // тут мы получаем старший бит и логически добавляем его к 0x1. В результате oldByte равна 1 если число отрицательное и 0 если положительное.
в случае если число отрицательное то выражение (1+oldByte-1) равно 1, а (oldByte-1) равно 0. В итоге возвращается -а, а поскольку а уже отрицательное то минус перед ним делает его положительным. В противном случае (1+oldByte-1) равно нулю а (oldByte-1) равно -1. В результате выходит -а*(-1) то есть просто а. Поскольку а положительное то возвращается просто а.ZnW
31.10.2015 11:38+1>(1+oldByte-1)
Серьёзно? Может, я что-то упускаю, но нельзя ли это записать «несколько проще»?
leshabirukov
31.10.2015 12:59+1Вот так вроде должно работать:
int myAbs(int a){ int sign = a >> 31; return (a ^ sign)-sign; }
Iceg
31.10.2015 14:57+1можно же упростить
int myAbs(int a){ int sign = a & 0x80000000; return a ^ sign; }
mambet
31.10.2015 12:58+5Мне в своё время очень понравилась эта идея:
rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
DmitryLeonov
31.10.2015 14:13Что особенно забавно — и сама эта задача, и полученный взамен пустяк с подсчетом разных цифр в числе решаются практически одинаково. Преподаватель все-таки добился желаемого.
Aingis
31.10.2015 14:27+7Я вас огорчу, но «k < arraySize» в цикле for — тоже if. Увы!
lair
31.10.2015 14:41Я подозреваю, что преподавать намекал на сортировку без сравнений (т.е., такую, в которой два элемента входных данных не сравниваются между собой на больше/меньше). А если вы вкладываете условия в обходе массива в недопустимые, то задача не имеет решения.
Mrrl
31.10.2015 21:38А если вы вкладываете условия в обходе массива в недопустимые, то задача не имеет решения.
Что, серьёзно?lair
31.10.2015 21:39Хм, а вы знаете, как обойти массив, не используя условие?
Mrrl
31.10.2015 21:55+1Знаю, но это потребует очень альтернативной архитектуры программы. Основная проблема — что я не знаю, как выйти из функции, которая занимается обходом. Передать управление в другую функцию (которая, используя тот же протокол, может передать его ещё дальше) — легко.
Mrrl
31.10.2015 22:10+6Примерно так (суммируем элементы массива):
int Array[100],Sum,Idx; int Len=100; int PC; void Func_0(){ Sum=Idx=0; PC=1; } void Func_1(){ PC=3+((Idx-Len)>>31); // 3 or 2 } void Func_2(){ Sum+=A[Idx++]; PC=1; } void Func_3(){ printf("All done\n"); exit(0); } void (*(Func[]))()={Func_0,Func_1,Func_2,Func_3}; void MainLoop(){ PC=0; for(;;) Func[PC](); }lair
31.10.2015 22:46+3Уважаю.
Mrrl
31.10.2015 23:22Собственно, то же самое можно было сделать с помощью одного switch внутри бесконечного цикла: он тоже транслируется в переход по массиву. К сожалению, компилятор никогда не поверит, что возможные значения переменной, из которых идёт выбор, все перечислены в case, и вставит перед переходом парочку проверок.
Mrrl
31.10.2015 21:52Можно было чуть проще (опять же в предположении 32-битных целых):
void sort(int *A,int N){ for(int a=0;a<N;a++){ for(int b=a+1;b<N;b++){ int s=((A[a]-A[b])>>31)&(A[a]^A[b]); A[a]^=s; A[b]^=s; } } }
Хотя если числа окажутся по модулю больше 230, приём может не сработать.ankh1989
01.11.2015 02:06Менее хитро и медленнее, но зато не зависит от разрядности чисел:
bool s = a[i] > a[j]; // true -> 1, false -> 0 a[i] = a[i] * !s + a[j] * s; a[j] = a[i] * s + a[j] * !s;
Этакое матричное умножение получилось.Mrrl
01.11.2015 09:29+1Две проблемы.
bool s = a[i] > a[j] — на половине процессоров реализуется как cmp + условный переход, а это тот же if. В половине остальных есть условное выполнение команды — не знаю, куда отнести, и только в оставшихся возможен set по флагу/условию.
!s — тоже не очень хорошо, лучше int s и 1-s.
Sirion
02.11.2015 08:37-1Эм… А ничего, что
if(условие){ какой-то код }
можно тривиальным образом трансформировать в
while(условие){ какой-то код break; }
?Mrrl
02.11.2015 09:54+1Ничего. Все for (с непустой второй частью), while, switch,?:, !, сравнения чисел и прочие проверяющие конструкции приравниваются к if.
К счастью, эмулятор машины Тьюринга легко пишется без if-ов, а любую программу можно переписать на машину Тьюринга.Sirion
02.11.2015 14:55В авторском решении for присутствует, ещё как. Впрочем, я вчитался повнимательнее в комменты и понял, о чём вы.
algorithmist
04.11.2015 06:41Не знаю, писали ли об этом выше. Но, как мне кажется, речь шла вовсе не о трюках, вроде замены if на abs, который в свою очередь заменяется битовой арифметикой. А о гораздо более глубоких вещах. Которые реально используются, к примеру, чтобы написать быстрый bilateral filter или median-filter на 2d матрице.
Смысл идеи в том, чтобы вычислять гистограммы значений. Глобально, или в локальных окнах. Гистограммы быстро вычисляются в обоих случаях, и дают массу полезной информации. К примеру сортировка массива, после того, как есть гистограмма, представляется тривиальной (даже с повторяющимися элементами). Так же быстро по гистограмме вычисляются median, bilateral -свертка и многое другое.
algorithmist
04.11.2015 06:53Вообще, «программа без IF» надо читать не буквально (потому что по сути IF есть даже в битовых операциях, не говоря уж о циклах и прочем), а «программа, допускающая большую степень параллелизации». И тогда все становится на свои места.
Потому что min/max/if, если они не являются абсолютно локальными, мешают параллельному вычислению (это же относится и к динамическим массивам), а циклы с фиксированным количеством итераций, пре-аллокированные массивы и т.п. не мешают.
lair
Квадратичная алгоритмическая сложность?
Интересно, кстати, а повторяющиеся числа по условию задачи могли быть?
Braiko
Повторов по условию нету.
3bab00n
Если повторов нет, то можно вот так сделать: