Braiko30 окт 2015 в 17:28

Сортировка без if-ов

2 мин

39K

C++ * Алгоритмы *

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

lair 30 окт 2015 в 17:35

Квадратичная алгоритмическая сложность?

Интересно, кстати, а повторяющиеся числа по условию задачи могли быть?

Braiko 30 окт 2015 в 18:17

Повторов по условию нету.

3bab00n 31 окт 2015 в 13:54

Если повторов нет, то можно вот так сделать:

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

NeoCode 30 окт 2015 в 17:39

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

ZnW 30 окт 2015 в 17:48

Не знаю, насколько это применимо к «реальной практике», но:
Когда писал свой буфер глубины для изометрического движка, который строился на обработке пикселей процессором (велосипед от скуки, развлекал себя), как раз пригодилась замена if'а, выкидывающего пиксель, на нехитрую формулу с альфой двух пикселей. Прирост был, т.к. пикселей было много (:

BelBES 30 окт 2015 в 18:08

Еще бывает полезно избавиться от if'ов для того, чтобы немного помочь предиктору ветвлений.

НЛО прилетело и опубликовало эту надпись здесь

zo_oz 30 окт 2015 в 22:39

Вот тоже самое хотел написать, выход из цикла в любом случае будет jnz/jz или loop по cx/ecx/итд
Можете пояснить чем это отличается от if?

p.s. код платформозависим) кто вам сказал что в int 32 разряда?

НЛО прилетело и опубликовало эту надпись здесь

Randl 31 окт 2015 в 11:15

Надо заменить на int32_t из cstdint

kosmos89 31 окт 2015 в 12:14

В современных процессорах есть предсказатель ветвлений, который накапливает статистику по jump'ам и спекулятивно выполняет ту ветвь которая до этого часто выполнялась. Поэтому если сброс конвейера и будет, то только на первой-второй итерации.
В более старых процессорах без предиктора, но со спекулятивным выполнением просто считалось, что jump назад всегда будет выполняться (потому что это очень похоже на цикл), а jump вперед — нет (потому что это похоже на выход из цикла).

НЛО прилетело и опубликовало эту надпись здесь

DaylightIsBurning 31 окт 2015 в 09:10

if очень сильно бьют по производительности в OpenCL, там по сути просто выполняются все ветки кода и потом просто ненужные выкидываются…

Torvald3d 1 ноя 2015 в 09:51

и не только огл, а практически на любой simd архитектуре

Torvald3d 2 ноя 2015 в 08:17

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

kosmos89 2 ноя 2015 в 09:21

На самом деле не всегда. Если в варпе все нити пойдут по одной и той же ветке, то никакого пеналти не будет.

vagran 31 окт 2015 в 13:04

Это очень актуально при написании шейдеров. Открывая статью, даже ожидал увидеть, что речь идёт о работе с GPU. А ветвления там не приветствуются из-за того, что код выполняется параллельно на сотнях ядер. Если один и тот же код выполняется на разных ядрах разное время, то выполняется дорогая синхронизация.

zelyony 30 окт 2015 в 17:50

https://graphics.stanford.edu/~seander/bithacks.html

DanmerZ 31 окт 2015 в 11:32

Спасибо за ссылку!

НЛО прилетело и опубликовало эту надпись здесь

DanmerZ 31 окт 2015 в 11:52

Рад за вашу учительницу, но по ссылке сборник хаков, а не руководство к действию :)

ankh1989 31 окт 2015 в 22:50

SWAP(x, x) это типа контрпример такой? Никто так писать никогда не будет, поэтому на этот сферический контрпример в вакууме (вращающийся где то на орбите между Землей и Марсом) никто никогда не наткнётся. А вот SWAP(x, y) работает даже когда x = y, лишь бы это разные переменные были.

Mrrl 1 ноя 2015 в 06:31

SWAP(a[x],a[y]) написать могут. И случайно может оказаться x==y.

dimanonim 1 ноя 2015 в 08:15

А почему не надо делать это через xor?

geovas333 30 окт 2015 в 17:57

Надо бы взять на вооружение, когда рассказывать уже нечего, а до конца занятия времени валом!

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 окт 2015 в 18:02

А вот если известно, что числа не повторяются, то можно решить за 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 1

На самом деле, и для повторяющихся тоже можно.

Update: какой-то у меня странный баг, перепроверю. Но идея понятна.

lair 30 окт 2015 в 18:07

Исправленный код

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

lair 30 окт 2015 в 18: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.toArray

ankh1989 31 окт 2015 в 22:53

Мм… этот код для 64-битных чисел потребует 2**64 байт памяти?

lair 31 окт 2015 в 23:02

Нет, O(N).

ankh1989 1 ноя 2015 в 22:06

ну если у нас три числа 3, 7, 2^64-3, то сколько надо будет памяти?

lair 1 ноя 2015 в 22:18

По условию задачи числа находятся в диапазоне от 0 до 100.

halyavin 30 окт 2015 в 18:08

Вы не смогли додуматься до сортировки подсчётом?

geovas333 30 окт 2015 в 18:18

Это как-то так?

Скрытый текст

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)

miriarder 30 окт 2015 в 18:23

Думаю, что это как-то так.

geovas333 30 окт 2015 в 18:28

Ух, помню оказывается! Значит можно с чистой совестью ложиться спать…

excoder 30 окт 2015 в 18:20

«Сортировка месива» – в этом что-то есть…

Braiko 30 окт 2015 в 18:22

Спасибо, исправил

excoder 30 окт 2015 в 20:48

Да я не с целью исправить :) После нескольких лет разработки спелл-чекера душа радуется таким примерчикам со смыслом.

VioletGiraffe 30 окт 2015 в 19:51

На входе месиво, на выходе массив :)

НЛО прилетело и опубликовало эту надпись здесь

Mirn 30 окт 2015 в 18:46

статья конечно хороша как эксперимент.
Так можно не только для ифов делать и всю логику линейной сделать.
Я ранее подобное описывал в каментах.
НО
я как то наталкнулся на свой код 15 летней давности… больше я так делать не буду никогда ни прикаких условиях как бы задача оптимизации не стояла. Код который нельзя исправить через 5-10 лет когда ты вообще забыл ЧТО ЭТО мне больше не нужен.
Даже если есть задача оптимизации и надо выжимать буквально байты, то можно делать это средствами самого языка не уродуя понимание и смысл.
А в микроконтроллерах уже есть неявное устранение IF. Например в ARM Cortex Mx инструкции с предикатами — часть инструкций испольняются если выставлен флаг а часть нет. Даже если этого не хватает то можно применить чёрную магию (для Россиян): например научить DMA и железо писать или читать данные аппаратно напрямую в lock-free очередь — экономиться и размер и скорость повышается. Причём в разы повышается. Так например поступил WIZNET в своих езернет чипах. Есть бит бандинг, алиасы регионов, аппаратные ускорители и прочие шалости. Все они неплохо заменяют то что описано в статье и совсем не портят сам исходник.

nikitasius 30 окт 2015 в 23:02

Поскольку я до этого жил в теплом мире фреймворков и библиотек

Прямо бальзам на сердце противнику фреймворков!

raid 31 окт 2015 в 07:07

В myAbs какая-то тёмная магия. Можете пояснить, как оно работает?

Braiko 31 окт 2015 в 07:24

Это работает для платформ, где 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 окт 2015 в 08:38

>(1+oldByte-1)
Серьёзно? Может, я что-то упускаю, но нельзя ли это записать «несколько проще»?

leshabirukov 31 окт 2015 в 09:59

Вот так вроде должно работать:

int myAbs(int a){
    int sign = a >> 31;
    return (a ^ sign)-sign;
}

Iceg 31 окт 2015 в 11:57

можно же упростить

int myAbs(int a){
    int sign = a & 0x80000000;
    return a ^ sign;
}

ZnW 31 окт 2015 в 08:37

--Не та ветка

mambet 31 окт 2015 в 09:58

Мне в своё время очень понравилась эта идея:
rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

DmitryLeonov 31 окт 2015 в 11:13

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

НЛО прилетело и опубликовало эту надпись здесь

lair 31 окт 2015 в 11:41

Я подозреваю, что преподавать намекал на сортировку без сравнений (т.е., такую, в которой два элемента входных данных не сравниваются между собой на больше/меньше). А если вы вкладываете условия в обходе массива в недопустимые, то задача не имеет решения.

Mrrl 31 окт 2015 в 18:38

А если вы вкладываете условия в обходе массива в недопустимые, то задача не имеет решения.

Что, серьёзно?

lair 31 окт 2015 в 18:39

Хм, а вы знаете, как обойти массив, не используя условие?

Mrrl 31 окт 2015 в 18:55

Знаю, но это потребует очень альтернативной архитектуры программы. Основная проблема — что я не знаю, как выйти из функции, которая занимается обходом. Передать управление в другую функцию (которая, используя тот же протокол, может передать его ещё дальше) — легко.

Mrrl 31 окт 2015 в 19:10

Примерно так (суммируем элементы массива):

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 окт 2015 в 19:46

Уважаю.

Mrrl 31 окт 2015 в 20:22

Собственно, то же самое можно было сделать с помощью одного switch внутри бесконечного цикла: он тоже транслируется в переход по массиву. К сожалению, компилятор никогда не поверит, что возможные значения переменной, из которых идёт выбор, все перечислены в case, и вставит перед переходом парочку проверок.

Iceg 31 окт 2015 в 22:29

Прикольно. Только в Func_1 надо вычитать из тройки, вроде.

Mrrl 1 ноя 2015 в 06:23

Значение (a >> 31) для int a равно 0 или -1. Можно было написать (int)((unsigned int)a >> 31) — это слегка честнее. И тогда надо было бы прибавлять.

Mrrl 31 окт 2015 в 18: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;
    }
  }
}

Хотя если числа окажутся по модулю больше 2³⁰, приём может не сработать.

ankh1989 31 окт 2015 в 23: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 1 ноя 2015 в 06:29

Две проблемы.
bool s = a[i] > a[j] — на половине процессоров реализуется как cmp + условный переход, а это тот же if. В половине остальных есть условное выполнение команды — не знаю, куда отнести, и только в оставшихся возможен set по флагу/условию.
!s — тоже не очень хорошо, лучше int s и 1-s.

Mrrl 1 ноя 2015 в 06:30

И, кстати, при s=1 работать не будет — нужна временная переменная.

ankh1989 2 ноя 2015 в 09:55

Хм… мда, получилось менее хитро и медленнее и неправильно :)

Sirion 2 ноя 2015 в 05:37

Эм… А ничего, что

if(условие){
    какой-то код
}

можно тривиальным образом трансформировать в

while(условие){
    какой-то код
    break;
}

Mrrl 2 ноя 2015 в 06:54

Ничего. Все for (с непустой второй частью), while, switch,?:, !, сравнения чисел и прочие проверяющие конструкции приравниваются к if.
К счастью, эмулятор машины Тьюринга легко пишется без if-ов, а любую программу можно переписать на машину Тьюринга.

Sirion 2 ноя 2015 в 11:55

В авторском решении for присутствует, ещё как. Впрочем, я вчитался повнимательнее в комменты и понял, о чём вы.

algorithmist 4 ноя 2015 в 03:41

Не знаю, писали ли об этом выше. Но, как мне кажется, речь шла вовсе не о трюках, вроде замены if на abs, который в свою очередь заменяется битовой арифметикой. А о гораздо более глубоких вещах. Которые реально используются, к примеру, чтобы написать быстрый bilateral filter или median-filter на 2d матрице.

Смысл идеи в том, чтобы вычислять гистограммы значений. Глобально, или в локальных окнах. Гистограммы быстро вычисляются в обоих случаях, и дают массу полезной информации. К примеру сортировка массива, после того, как есть гистограмма, представляется тривиальной (даже с повторяющимися элементами). Так же быстро по гистограмме вычисляются median, bilateral -свертка и многое другое.

algorithmist 4 ноя 2015 в 03:53

Вообще, «программа без IF» надо читать не буквально (потому что по сути IF есть даже в битовых операциях, не говоря уж о циклах и прочем), а «программа, допускающая большую степень параллелизации». И тогда все становится на свои места.
Потому что min/max/if, если они не являются абсолютно локальными, мешают параллельному вычислению (это же относится и к динамическим массивам), а циклы с фиксированным количеством итераций, пре-аллокированные массивы и т.п. не мешают.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий