Comments 71
Квадратичная алгоритмическая сложность?
Интересно, кстати, а повторяющиеся числа по условию задачи могли быть?
Интересно, кстати, а повторяющиеся числа по условию задачи могли быть?
0
Повторов по условию нету.
0
Если повторов нет, то можно вот так сделать:
#include <iostream>
using namespace std;
int main() {
int arr[] = {34, 12, 24, 65, 63, 22};
int arraySize = (sizeof(arr) / sizeof(*arr));
unsigned char buf[101]={0};
for (int k = 0; k < arraySize; k++) {
buf[arr[k]]++;
}
unsigned char i=0;
for (int k = 0; k <= 100; k++) {
arr[i]=k;
i+=buf[k];
}
for(int a:arr){
cout<<a<<endl;
}
return 0;
}
+6
Кстати, в реальной практике столкнулся с тем что иногда алгоритмы без if'ов могут быть полезны. При разработке прошивки для микроконтроллера обнаружилось (реально, осциллографом) что наличие if'ов в процедуре обработки прерывания существенно замедляет эту самую обработку. Ну и оказалось проще придумать и написать нечто на арифметических и битовых операциях, но без условных переходов.
+4
Не знаю, насколько это применимо к «реальной практике», но:
Когда писал свой буфер глубины для изометрического движка, который строился на обработке пикселей процессором (велосипед от скуки, развлекал себя), как раз пригодилась замена if'а, выкидывающего пиксель, на нехитрую формулу с альфой двух пикселей. Прирост был, т.к. пикселей было много (:
Когда писал свой буфер глубины для изометрического движка, который строился на обработке пикселей процессором (велосипед от скуки, развлекал себя), как раз пригодилась замена if'а, выкидывающего пиксель, на нехитрую формулу с альфой двух пикселей. Прирост был, т.к. пикселей было много (:
+2
Еще бывает полезно избавиться от if'ов для того, чтобы немного помочь предиктору ветвлений.
+6
UFO just landed and posted this here
Вот тоже самое хотел написать, выход из цикла в любом случае будет jnz/jz или loop по cx/ecx/итд
Можете пояснить чем это отличается от if?
p.s. код платформозависим) кто вам сказал что в int 32 разряда?
Можете пояснить чем это отличается от if?
p.s. код платформозависим) кто вам сказал что в int 32 разряда?
+3
В современных процессорах есть предсказатель ветвлений, который накапливает статистику по jump'ам и спекулятивно выполняет ту ветвь которая до этого часто выполнялась. Поэтому если сброс конвейера и будет, то только на первой-второй итерации.
В более старых процессорах без предиктора, но со спекулятивным выполнением просто считалось, что jump назад всегда будет выполняться (потому что это очень похоже на цикл), а jump вперед — нет (потому что это похоже на выход из цикла).
В более старых процессорах без предиктора, но со спекулятивным выполнением просто считалось, что jump назад всегда будет выполняться (потому что это очень похоже на цикл), а jump вперед — нет (потому что это похоже на выход из цикла).
+1
if очень сильно бьют по производительности в OpenCL, там по сути просто выполняются все ветки кода и потом просто ненужные выкидываются…
+2
и не только огл, а практически на любой simd архитектуре
0
На самом деле не всегда. Если в варпе все нити пойдут по одной и той же ветке, то никакого пеналти не будет.
0
Это очень актуально при написании шейдеров. Открывая статью, даже ожидал увидеть, что речь идёт о работе с GPU. А ветвления там не приветствуются из-за того, что код выполняется параллельно на сотнях ядер. Если один и тот же код выполняется на разных ядрах разное время, то выполняется дорогая синхронизация.
+1
https://graphics.stanford.edu/~seander/bithacks.html
+7
Спасибо за ссылку!
-1
UFO just landed and posted this here
Рад за вашу учительницу, но по ссылке сборник хаков, а не руководство к действию :)
0
SWAP(x, x) это типа контрпример такой? Никто так писать никогда не будет, поэтому на этот сферический контрпример в вакууме (вращающийся где то на орбите между Землей и Марсом) никто никогда не наткнётся. А вот SWAP(x, y) работает даже когда x = y, лишь бы это разные переменные были.
-3
А почему не надо делать это через xor?
-2
Надо бы взять на вооружение, когда рассказывать уже нечего, а до конца занятия времени валом!
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)
+5
А вот если известно, что числа не повторяются, то можно решить за O(N).
На самом деле, и для повторяющихся тоже можно.
Update: какой-то у меня странный баг, перепроверю. Но идея понятна.
Как-то так
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 1
На самом деле, и для повторяющихся тоже можно.
Update: какой-то у меня странный баг, перепроверю. Но идея понятна.
+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 1
+1
Ну да, а если решать для повторяющихся, то общий случай оказывается проще. 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.toArray
0
Мм… этот код для 64-битных чисел потребует 2**64 байт памяти?
-1
Вы не смогли додуматься до сортировки подсчётом?
+5
«Сортировка месива» – в этом что-то есть…
+15
статья конечно хороша как эксперимент.
Так можно не только для ифов делать и всю логику линейной сделать.
Я ранее подобное описывал в каментах.
НО
я как то наталкнулся на свой код 15 летней давности… больше я так делать не буду никогда ни прикаких условиях как бы задача оптимизации не стояла. Код который нельзя исправить через 5-10 лет когда ты вообще забыл ЧТО ЭТО мне больше не нужен.
Даже если есть задача оптимизации и надо выжимать буквально байты, то можно делать это средствами самого языка не уродуя понимание и смысл.
А в микроконтроллерах уже есть неявное устранение IF. Например в ARM Cortex Mx инструкции с предикатами — часть инструкций испольняются если выставлен флаг а часть нет. Даже если этого не хватает то можно применить чёрную магию (для Россиян): например научить DMA и железо писать или читать данные аппаратно напрямую в lock-free очередь — экономиться и размер и скорость повышается. Причём в разы повышается. Так например поступил WIZNET в своих езернет чипах. Есть бит бандинг, алиасы регионов, аппаратные ускорители и прочие шалости. Все они неплохо заменяют то что описано в статье и совсем не портят сам исходник.
Так можно не только для ифов делать и всю логику линейной сделать.
Я ранее подобное описывал в каментах.
НО
я как то наталкнулся на свой код 15 летней давности… больше я так делать не буду никогда ни прикаких условиях как бы задача оптимизации не стояла. Код который нельзя исправить через 5-10 лет когда ты вообще забыл ЧТО ЭТО мне больше не нужен.
Даже если есть задача оптимизации и надо выжимать буквально байты, то можно делать это средствами самого языка не уродуя понимание и смысл.
А в микроконтроллерах уже есть неявное устранение IF. Например в ARM Cortex Mx инструкции с предикатами — часть инструкций испольняются если выставлен флаг а часть нет. Даже если этого не хватает то можно применить чёрную магию (для Россиян): например научить DMA и железо писать или читать данные аппаратно напрямую в lock-free очередь — экономиться и размер и скорость повышается. Причём в разы повышается. Так например поступил WIZNET в своих езернет чипах. Есть бит бандинг, алиасы регионов, аппаратные ускорители и прочие шалости. Все они неплохо заменяют то что описано в статье и совсем не портят сам исходник.
+1
Поскольку я до этого жил в теплом мире фреймворков и библиотек
Прямо бальзам на сердце противнику фреймворков!
-4
В myAbs какая-то тёмная магия. Можете пояснить, как оно работает?
0
Это работает для платформ, где 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) то есть просто а. Поскольку а положительное то возвращается просто а.
int oldByte = (a >> 31)& 0x1; // тут мы получаем старший бит и логически добавляем его к 0x1. В результате oldByte равна 1 если число отрицательное и 0 если положительное.
в случае если число отрицательное то выражение (1+oldByte-1) равно 1, а (oldByte-1) равно 0. В итоге возвращается -а, а поскольку а уже отрицательное то минус перед ним делает его положительным. В противном случае (1+oldByte-1) равно нулю а (oldByte-1) равно -1. В результате выходит -а*(-1) то есть просто а. Поскольку а положительное то возвращается просто а.
-1
--Не та ветка
0
Мне в своё время очень понравилась эта идея:
rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
+5
Что особенно забавно — и сама эта задача, и полученный взамен пустяк с подсчетом разных цифр в числе решаются практически одинаково. Преподаватель все-таки добился желаемого.
0
UFO just landed and posted this here
Я подозреваю, что преподавать намекал на сортировку без сравнений (т.е., такую, в которой два элемента входных данных не сравниваются между собой на больше/меньше). А если вы вкладываете условия в обходе массива в недопустимые, то задача не имеет решения.
0
А если вы вкладываете условия в обходе массива в недопустимые, то задача не имеет решения.
Что, серьёзно?
0
Хм, а вы знаете, как обойти массив, не используя условие?
0
Знаю, но это потребует очень альтернативной архитектуры программы. Основная проблема — что я не знаю, как выйти из функции, которая занимается обходом. Передать управление в другую функцию (которая, используя тот же протокол, может передать его ещё дальше) — легко.
+1
Примерно так (суммируем элементы массива):
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]();
}
+6
Уважаю.
+3
Собственно, то же самое можно было сделать с помощью одного switch внутри бесконечного цикла: он тоже транслируется в переход по массиву. К сожалению, компилятор никогда не поверит, что возможные значения переменной, из которых идёт выбор, все перечислены в case, и вставит перед переходом парочку проверок.
0
Прикольно. Только в Func_1 надо вычитать из тройки, вроде.
0
Можно было чуть проще (опять же в предположении 32-битных целых):
Хотя если числа окажутся по модулю больше 230, приём может не сработать.
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, приём может не сработать.
0
Менее хитро и медленнее, но зато не зависит от разрядности чисел:
Этакое матричное умножение получилось.
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;
Этакое матричное умножение получилось.
0
Две проблемы.
bool s = a[i] > a[j] — на половине процессоров реализуется как cmp + условный переход, а это тот же if. В половине остальных есть условное выполнение команды — не знаю, куда отнести, и только в оставшихся возможен set по флагу/условию.
!s — тоже не очень хорошо, лучше int s и 1-s.
bool s = a[i] > a[j] — на половине процессоров реализуется как cmp + условный переход, а это тот же if. В половине остальных есть условное выполнение команды — не знаю, куда отнести, и только в оставшихся возможен set по флагу/условию.
!s — тоже не очень хорошо, лучше int s и 1-s.
+1
И, кстати, при s=1 работать не будет — нужна временная переменная.
+1
Эм… А ничего, что
можно тривиальным образом трансформировать в
?
if(условие){
какой-то код
}
можно тривиальным образом трансформировать в
while(условие){
какой-то код
break;
}
?
-1
Ничего. Все for (с непустой второй частью), while, switch,?:, !, сравнения чисел и прочие проверяющие конструкции приравниваются к if.
К счастью, эмулятор машины Тьюринга легко пишется без if-ов, а любую программу можно переписать на машину Тьюринга.
К счастью, эмулятор машины Тьюринга легко пишется без if-ов, а любую программу можно переписать на машину Тьюринга.
+1
Не знаю, писали ли об этом выше. Но, как мне кажется, речь шла вовсе не о трюках, вроде замены if на abs, который в свою очередь заменяется битовой арифметикой. А о гораздо более глубоких вещах. Которые реально используются, к примеру, чтобы написать быстрый bilateral filter или median-filter на 2d матрице.
Смысл идеи в том, чтобы вычислять гистограммы значений. Глобально, или в локальных окнах. Гистограммы быстро вычисляются в обоих случаях, и дают массу полезной информации. К примеру сортировка массива, после того, как есть гистограмма, представляется тривиальной (даже с повторяющимися элементами). Так же быстро по гистограмме вычисляются median, bilateral -свертка и многое другое.
Смысл идеи в том, чтобы вычислять гистограммы значений. Глобально, или в локальных окнах. Гистограммы быстро вычисляются в обоих случаях, и дают массу полезной информации. К примеру сортировка массива, после того, как есть гистограмма, представляется тривиальной (даже с повторяющимися элементами). Так же быстро по гистограмме вычисляются median, bilateral -свертка и многое другое.
0
Вообще, «программа без IF» надо читать не буквально (потому что по сути IF есть даже в битовых операциях, не говоря уж о циклах и прочем), а «программа, допускающая большую степень параллелизации». И тогда все становится на свои места.
Потому что min/max/if, если они не являются абсолютно локальными, мешают параллельному вычислению (это же относится и к динамическим массивам), а циклы с фиксированным количеством итераций, пре-аллокированные массивы и т.п. не мешают.
Потому что min/max/if, если они не являются абсолютно локальными, мешают параллельному вычислению (это же относится и к динамическим массивам), а циклы с фиксированным количеством итераций, пре-аллокированные массивы и т.п. не мешают.
0
Sign up to leave a comment.
Сортировка без if-ов