Найти среднее (С++)

[realeugene]

Legioner93 в сообщении #1368219 писал(а):

Пузырёк вручную и выводим второй элемент

И этот вариант будет самым быстрым, если в системе команд процессора есть условно выполняемые пересылки между регистрами. И если их нет, то несложно сделать условный swap на битовых операциях.

[SergeCpp]

photon в сообщении #1368643 писал(а):

...

У меня нет возможности инструментально всё это выполнить-проверить, но даже такие ныне старые, как VC5 и VC6 (по моим воспоминаниям), справлялись со всем. У меня в проектах даже специально ассемблерные листинги были включены в проект и я это всегда смотрел-сравнивал (и Randall Hyde Great Debate и подобное читал).

1) Для бОльшей наглядности сложения можно заменить на |.
===
Это не имеет значения, всё это вместе с умножениями оптимизируется. Плюс считаю естественнее (в статье Википедии "Позиционная система счисления" стоит сумма). Кстати, с плюсом компилятору будет легче выяснить, всё ли есть в switch.

2) Статический анализатор может обругать такой код, сказав, что не все пути имеют return. Чтобы его удовлетворить, можно добавить поле default или воткнуть return за switch-ем.
===
Он должен (сколь помню) разобраться, что там всё перечислено. У вас есть возможность если, посмотрите с разными оптимизациями.

3) Нулевое возвращаемое значение является вполне корректным для данной функции - не очень красиво писать его в return без какой-либо дополнительной обработки, даже если программа туда никогда не зайдет. Кстати, а зачем выписывать варианты, которые не могут случиться?
===
И для красоты-симметрии и для помощи анализатору (2) и для "ровности" кода -- посмотрите в асме, что выходит при разных изменениях.

Если б мог, я бы всё это и сам посмотрел -- интересно же.

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

-- 14.01.2019, 17:02 --

Используется синтаксис C++

int mid( int a, int b, int c )
{
  switch( (a<b)*4 + (b<c)*2 + (a<c)*1 )
  {
  case 0: return b; // 000: a>b, b>c, a>c
  case 1: return 0; // 001: a>b, b>c, a<c: cannot be
  case 2: return c; // 010: a>b, b<c, a>c
  case 3: return a; // 011: a>b, b<c, a<c
  case 4: return a; // 100: a<b, b>c, a>c
  case 5: return c; // 101: a<b, b>c, a<c
  case 6: return 0; // 110: a<b, b<c, a>c: cannot be
  case 7: return b; // 111: a<b, b<c, a<c
  }
}

...симметрично относительно центральной горизонтали (между 3 и 4).

Можно воспользоваться этой симметричностью:

Используется синтаксис C++

int mid( int a, int b, int c )
{
  switch( ((b<c)^(a<b))*2 + ((a<c)^(a<b))*1 )
  {
  case 0: return b;
  case 1: return 0;
  case 2: return c;
  case 3: return a;
  }
}

-- 14.01.2019, 17:20 --

Дальше можно воспользоваться и тем, что один результат не используется (схлопываем "0" и "c"):

Используется синтаксис C++

int mid( int a, int b, int c )
{
  switch( ((b<c)^(a<b)) + ((a<c)^(a<b)) )
  {
  case 0: return b;
  case 1: return c;
  case 2: return a;
  }
}

[SergeCpp]

Нашёл онлайн с асмом.

В первом варианте условных переходов нет, switch "решён" (x86-64 gcc 8.2 -O):

Используется синтаксис ASM

; mid(int, int, int):

        cmp     edi, esi
        setl    al
        movzx   eax, al
        cmp     esi, edx
        setl    cl
        movzx   ecx, cl
        add     ecx, ecx
        lea     ecx, [rcx+rax*4]
        cmp     edi, edx
        setl    al
        movzx   eax, al
        add     ecx, eax
        mov     ecx, ecx
        jmp     [QWORD PTR .L6[0+rcx*8]]
.L6:
        .quad   .L5
        .quad   .L7
        .quad   .L13
        .quad   .L10
        .quad   .L9
        .quad   .L13
        .quad   .L7
        .quad   .L5
.L7:
        mov     eax, 0
        ret
.L10:
        mov     eax, edi
        ret
.L9:
        mov     eax, edi
        ret
.L5:
        mov     eax, esi
        ret
.L13:
        mov     eax, edx
        ret

[realeugene]

SergeCpp в сообщении #1368687 писал(а):

В первом варианте условных переходов нет, switch "решён".

Зато есть принципиально тут непредсказуемый переход по таблице по индексу.

-- 14.01.2019, 18:27 --

Вот один из вариантов без переходов:

Используется синтаксис C++

int mid( int a, int b, int c )
{
    return -(b <= a && a <= c)  & a
        | -(a <= b && b <= c) & b
        | -(a <= c && c <= b) & c;
}

-- 14.01.2019, 18:41 --

SergeCpp в сообщении #1368687 писал(а):

Нашёл онлайн с асмом.

Самый быстрый вариант для этого компилятора (если я нигде не ошибся):

Используется синтаксис C++

inline void sortX(int& a, int& b)
{
    int x = -(a > b) & (a ^ b);
    a ^= x;
    b ^= x;
}

inline void sort(int& a, int& b)
{
    if (a > b) 
    {
        int oldB = b;
        b = a;
        a = oldB;
    }
}

int mid( int a, int b, int c )
{
    sortX(a, b);
    sort(b, c);
    sort(a, b);
    return b;
}

Используется синтаксис ASM

        cmp     edi, esi
        setg    cl
        movzx   ecx, cl
        neg     ecx
        mov     eax, edi
        xor     eax, esi
        and     ecx, eax
        xor     esi, ecx
        cmp     esi, edx
        cmovg   esi, edx
        xor     ecx, edi
        cmp     ecx, esi
        mov     eax, esi
        cmovge  eax, ecx
        ret

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

UPD: ещё немного сократил выражения

[SergeCpp]

Называется оптимизирующий компилятор 21 века...

Используется синтаксис ASM

        mov     ecx, ecx
...
.L10:
        mov     eax, edi
        ret
.L9:
        mov     eax, edi
        ret

[_Ivana]

Чет жестко О0? С сохранением дебаг-информации для брейкпоинтов? Тогда еще может быть.

[realeugene]

В варианте с тремя обычными sort (без sortX) в моём коде gcc зачем-то оставляет короткий условный переход, из-за чего и приходится извращаться с sortX. А вот x86-64 clang 7.0.0 компилирует его в следующий ассемблерный код:

Используется синтаксис ASM

        cmp     edi, esi
        mov     eax, edi
        cmovg   eax, esi
        cmovge  esi, edi
        cmp     esi, edx
        cmovg   esi, edx
        cmp     eax, esi
        cmovge  esi, eax
        mov     eax, esi
        ret
 

Но победитель, безусловно, ARM64 gcc 8.2:

Используется синтаксис ASM

        cmp     w0, w1
        csel    w3, w0, w1, le
        csel    w1, w1, w0, le
        cmp     w1, w2
        csel    w1, w1, w2, le
        cmp     w3, w1
        csel    w0, w3, w1, ge
        ret
 

UPD Пузырёк в обратную сторону экономит на x86-64 clang 7.0.0 ещё одну команду:

Используется синтаксис C++

inline void sort(int& a, int& b)
{
    if (a > b)
    {
        int oldB = b;
        b = a;
        a = oldB;
    }
}

int mid(int a, int b, int c)
{
    sort(b, c);
    sort(a, b);
    sort(b, c);
    return b;
}
 

Используется синтаксис ASM

        cmp     esi, edx
        mov     eax, esi
        cmovg   eax, edx
        cmovge  edx, esi
        cmp     eax, edi
        cmovl   eax, edi
        cmp     eax, edx
        cmovg   eax, edx
        ret
 

[SergeCpp]

_Ivana в сообщении #1368701 писал(а):

... О0? С сохранением дебаг-информации для брейкпоинтов? Тогда еще может быть.

Если вы про моё замечание по моему примеру, то там "O", что есть "O1" и по документации и по проверке (добавить единичку или нолик и сравнить).
3.10 Options That Control Optimization

-- 14.01.2019, 20:05 --

realeugene в сообщении #1368707 писал(а):

...

Да, это хороший пример. Кстати, а может он есть в книге?

[realeugene]

realeugene в сообщении #1368692 писал(а):

Вот один из вариантов без переходов:

Этот вариант ошибочный: условия неполные. Пожалуй, с пузырьком будет быстрее всего в любом случае.