1. Си / Говнокод #24496

    +5

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    void sort3(uint32_t a[static 3])
    {
      //                   0     1     2     3     4     5     6     7     8
      uint32_t tmp[9] = {a[0], a[1], a[2], a[0], a[1], a[0], a[2], a[1], a[0]};
      uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
      static const uint8_t b[] =
      {
        [0b000] = 6,
        [0b001] = 2,
        [0b010] = 1,
        [0b101] = 5,
        [0b110] = 4,
        [0b111] = 0,
      };
      memcpy(a, tmp+b[bits], 3*sizeof(uint32_t));
    }

    Новая инновационная сортировка на 3 элемента без if-ов
    https://wandbox.org/permlink/pTLXgxKKQuaiVCxb

    Запостил: j123123, 15 Июля 2018

    Комментарии (195) RSS

    • Еще одно интересное улучшение
      void sort3(uint32_t a[static 3])
      {
        //                             0  1  2  3  4  5  6  7  8
        static const uint8_t tmp[9] = {0, 1, 2, 0, 1, 0, 2, 1, 0};
        const uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
        static const uint8_t b[] =
        {
          [0b000] = 6,
          [0b001] = 2,
          [0b010] = 1,
          [0b101] = 5,
          [0b110] = 4,
          [0b111] = 0,
        };
        const uint32_t out[3] = {a[tmp[b[bits]]], a[tmp[b[bits]+1]], a[tmp[b[bits]+2]]};
        memcpy(a, out, sizeof(out));
      }
      Ответить
      • Для случая двух элементов массив b можно вообще опустить:
        void sort2(uint32_t a[static 2])
        {
          uint32_t tmp[3] = {a[0], a[1], a[0]};
          uint8_t bits = (a[0] > a[1]);
          memcpy(a, tmp+bits, 2*sizeof(uint32_t));
        }
        Ответить
        • Перевёл на WinApi:

          #define FLAG_SORT_NORMAL 1
          BOOL WINAPI Sort2Arr32(ULONG32 *lpArr, HANDLE hArrDevice, PVOID unused, DWORD dwFlagsSortAttributes)
          {
              if (NULL == lpArr) {
                  SetLastError(ERROR_INVALID_DATA);
                  return FALSE;
              }
          
              if (INVALID_HANDLE_VALUE == hArrDevice) {
                  SetLastError(ERROR_INVALID_HANDLE);
                  return FALSE;
              }
          
              if (NULL != unused || FLAG_SORT_NORMAL != dwFlagsSortAttributes) {
                  SetLastError(ERROR_INVALID_PARAMETER);
                  return FALSE;
              }
          
              ULONG32 aTmp[3] = { lpArr[0], lpArr[1], lpArr[0] };
              UINT8 iBits = (lpArr[0] > lpArr[1]);
              CopyMemory(lpArr, aTmp + iBits, 2 * sizeof(ULONG));
          
              SetLastError(ERROR_SUCCESS);
              return TRUE;
          }
          Ответить
      • Охуеть, шесть года прошло. А ведь почти как вчера было…
        Ответить
    • показать все, что скрытоvanished
      Ответить
      • Для Си это GNU extension, а вот в C++14 это есть по стандарту
        https://en.cppreference.com/w/cpp/language/integer_literal
        Ответить
    • показать все, что скрытоvanished
      Ответить
      • По приколу конечно. Не думаю что эта хрень будет быстро работать. Хотя надо будет как-нибудь бенчмарк замутить
        http://govnokod.ru/20309 еще есть
        Ответить
        • показать все, что скрытоvanished
          Ответить
          • > Нельзя было сделать 0o по аналогии с 0x и 0b?
            > … а потом удивляешься, почему не компилируется.

            Это ещё хорошо, что не компилируется. Вот если бы было 0о, то в каком-нибудь шрифте ты был бы твёрдо уверен, что пишешь десятичные нули, и всё бы компилировалось. И лови потом баги.

            Уже и так есть long с l на конце, который путают с единицей.
            Ответить
            • показать все, что скрытоvanished
              Ответить
            • То ли дело 8'o377 и 8'hFF.
              Ответить
              • показать все, что скрытоvanished
                Ответить
                • То ли дело FORTH:
                  42 \ здесь 10-чная СС
                  16 BASE ! \ установили 16-чную
                  ABBA
                  8 BASE ! \ 8-чная
                  101
                  HEX \ можно так
                  FEED
                  DECIMAL \ и так
                  .S

                  Спасибо, я кончел.
                  Ответить
                  • Забыл вставить.
                    https://ideone.com/3xysnu
                    Ответить
                    • https://ideone.com/GGzxJ3
                      Ответить
                    • показать все, что скрытоvanished
                      Ответить
                      • Не понял о чём ты.
                        Ответить
                        • показать все, что скрытоvanished
                          Ответить
                          • Зато я знаю, как там всё устроено у твоей мамки.
                            Ответить
                          • https://ideone.com/954DRG

                            Кстати, форт-система очень просто реализуется - всё уже спроектировано, нужно только реализовать, и состоит она из множества небольших определений - удобно тестировать. Я когда ещё на 2-м курсе учился, после пары месяцев изучения асма уже мог её реализовать (.COM, 3.5 Кб, набор слов не полный, и не всё по стандарту, но уже вполне можно было расширять форт из самого форта)
                            Ответить
                      • К одной строке несколько раз можно обратиться, только если её сохранить где-нибудь, а потом EVALUATE её (типа как eval в скриптушне), её интерпретация будет зависет от текущего состояния системы: словарь, основание СС, перемеменной STATE (0 - интерпретация, 1 - конпеляция), естественно от состояния стеков (их как минимум 2 - для данных, и стек возвратов) и, возможно, от чего-то ещё.
                        Ответить
              • > То ли дело 8'o377 и 8'hFF

                А что это за нотация? Я такого никогда не видел.

                Я вообще за то, чтобы было так:

                int a = 100_8;
                int b = AFF_16;
                double c = 1010101.01010_2;

                И чтобы основание системы счисления могло быть более-менее любым (например, покуда хватает латинского алфавита). Компилятору всё равно это несложно преобразовать.
                Ответить
                • > что за нотация
                  Verilog. <количество бит>'<основание><число>. Там иногда нужны числа с кривой разрядностью, к примеру 5 или 9 бит. Поэтому такой странный синтаксис.
                  Ответить
                  • А римскими цифрами в верилоге можно число записывать?
                    Ответить
                    • Это ж не форт чтобы такое можно было...
                      Ответить
                    • Есть еще система остаточных классов, фибоначчиевая система счисления и прочее. Зачем останавливаться на какой-то там позиционной? Модулярная арифметика для верилога была б вполне уместной
                      Ответить
                • показать все, что скрытоvanished
                  Ответить
    • показать все, что скрытоvanished
      Ответить
    • Всё красиво, кроме 4-й строчки: девять мувов, результаты большинства из которых никак не будут использованы.
      Ответить
      • Вариант, требующий меньше памяти:
        void sort3(uint32_t a[static 3])
        {
          uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
          uint8_t halfbits = bits >> 1;
          static const uint8_t b[] =
          {
            [0b000] = 2,
            [0b001] = 1,
            [0b010] = 2,
            [0b101] = 0,
            [0b110] = 1,
            [0b111] = 0,
          };
          uint32_t tmp = a[0];
          a[0] = a[1 + (halfbits == 0)];
          a[1] = a[1 + (halfbits == 1) + (halfbits == 2)];
          a[2] = a[1 + (halfbits == 3)];
          a[b[bits]] = tmp;
        }

        Но всё равно он мне не нравится.
        Ответить
    • Перевёл на «C++»:
      #include <iostream>
      #include <vector>
      #include <functional>
      #include <cinttypes>
      
      using namespace std;
      
      template<class T, uint8_t B>
      struct Hui {
          static void sort3_impl(vector<T> & arr);
      };
      
      template<class T>
      struct Hui<T, 0> {
          static void sort3_impl(vector<T> &)
          {
          }
      };
      
      template<class T>
      struct Hui<T, 1> {
          static void sort3_impl(vector<T> & arr)
          {
              swap(arr[0], arr[1]);
          }
      };
      
      template<class T>
      struct Hui<T, 2> {
          static void sort3_impl(vector<T> & arr)
          {
              swap(arr[1], arr[2]);
          }
      };
      
      template<class T>
      struct Hui<T, 5> {
          static void sort3_impl(vector<T> & arr)
          {
              swap(arr[0], arr[1]);
              swap(arr[1], arr[2]);
          }
      };
      
      template<class T>
      struct Hui<T, 6> {
          static void sort3_impl(vector<T> & arr)
          {
              swap(arr[0], arr[2]);
              swap(arr[1], arr[2]);
          }
      };
      
      template<class T>
      struct Hui<T, 7> {
          static void sort3_impl(vector<T> & arr)
          {
              swap(arr[0], arr[2]);
          }
      };
      
      template<class T>
      void sort3_runtime_call(vector<T> & arr, uint8_t bits)
      {
          static array<function<void(vector<T> &)>, 8> func_table = {
              Hui<T, 0>::sort3_impl,
              Hui<T, 1>::sort3_impl,
              Hui<T, 2>::sort3_impl,
              Hui<T, 0>::sort3_impl,
              Hui<T, 0>::sort3_impl,
              Hui<T, 5>::sort3_impl,
              Hui<T, 6>::sort3_impl,
              Hui<T, 7>::sort3_impl,
          };
          func_table[bits](arr);
      }
      
      template<class T>
      void sort3(vector<T> & arr)
      {
          sort3_runtime_call(arr, (arr[0] > arr[1]) | ((arr[1] > arr[2]) << 1) | ((arr[0] > arr[2]) << 2));
      }
      
      int main()
      {
          vector<vector<uint32_t>> tests = {
              {1, 2, 3}, {1, 3, 2}, {2, 1, 3},
              {2, 3, 1}, {3, 1, 2}, {3, 2, 1},
          };
      
          for (auto && arr : tests) {
              sort3(arr);
              cout << arr[0] << ", " << arr[1] << ", " << arr[2] << endl;
          }
          return EXIT_SUCCESS;
      }

      https://ideone.com/1RvRS7
      Ответить
      • Хуита

        Попробуй лучше на крестах сделать в компилтайме через говношаблоны и кококонстэкпры нахождение самой короткой (какую-нибудь из самых коротких) строки, в которой будут все возможные кобенации для N разных элементов. Вот например для массива из трех элементов будет 6! кобенаций
        1 0 2
        2 0 1
        
        0 1 2
        2 1 0
        
        0 2 1
        1 2 0


        И вот такая зожатая короткая строка, в которой все эти кобенации есть:
        .
              0, 1, 2, 0, 1, 0, 2, 1, 0
        (012) ^  ^  ^
        (120)    ^  ^  ^
        (201)       ^  ^  ^
        (102)             ^  ^  ^
        (021)                ^  ^  ^
        (210)                   ^  ^  ^

        А теперь попробуй на кококонстэкспрах и говношаблонах сделать обобщенный генератор сортировок для произвольной длинны моссива с зожатыми кобенациями всех массивов в один массив
        Ответить
        • https://en.wikipedia.org/wiki/Superpattern
          https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery
          Референс для желающих.
          Ответить
          • Вообще-то не superpattern, а superpermutation
            https://en.wikipedia.org/wiki/Superpermutation
            Ответить
          • > https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery

            > 4chan
            > anime

            Вот к чему ваше онимэ и борды приводят.
            Пока ты свое аниме сортируешь в оптимальном порядке, успешные программисты повращали матрицы на хакирране и работают в гугле. Должность - Senior Matrix Rotator
            Ответить
        • Пытаюсь перевести на современный, функциональный Javascript:
          const allPermutations = (arr, len) => arr
            .map((a, i, arr) => arr.slice(i, i + len))
            .filter(arr => 
              arr.length === len && (new Set(arr)).size === arr.length)
            
          const zipPy = (arr1,arr2) => Object.values(
            Object.assign(
              new Proxy(
                {}, 
                {
                  set: (target, name, val) =>
                    name in target?
                    target[name].push(val):
                    target[name] = [val]
                }
              ), arr1, arr2))
              
          const mergeDepth = (arr1, arr2, len) =>
            !len? len:
              zipPy(arr1.slice(-len), arr2.slice(0, len))
              .every(([el1, el2]) => el1 === el2)? len:
                mergeDepth(arr1, arr2, len-1)
            
          const superPermutation = arr =>
            arr.reduce((res,curr,i) =>
              allPermutations([].concat(res),i)
              .map(per => per.concat(curr, per))
              .reduce((res, curr) =>
                res.concat(curr.slice(mergeDepth(res, curr, i)))))
          
          const sortGenerator = len => arr =>
            allPermutations(
              superPermutation(
                [...Array(len).keys()]), len)
            .find(perm =>
              (arr =>
               zipPy(arr.slice(0,-1), arr.slice(1))
                .every(([a,b]) => a <= b))(perm.map(i => arr[i])))
            .map(i => arr[i])
              
          console.log(sortGenerator(5)([11,3,1,1,3]))//[1, 1, 3, 3, 11]

          Но получается нечестно: вместо хитрой генерации индекса в суперпермутации, который даст отсортированный массив я выбираю нужную пермутацию перебором.
          Так же есть сопутствующая проблема: на определенном размере(больше 4) длина суперпермутации становится длиннее количества всех пермутаций. Так, для 4 длина суперпермутации 33(30 возможных вариантов), а количество пермутаций - 24.
          Если кто-то может придумать как генерировать правила для нахождения индекса - подскажите.
          Ответить
    • Братишка, я тебе битов подвёз, проверь:
      void sort3(uint32_t a[static 3])
      {
        uint16_t mask = 0x6124;
        uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
        static const uint8_t b[] =
        {
          [0b000] =  3, // =0
          [0b001] =  8,
          [0b010] = 10,
          [0b101] =  2, // =5
          [0b110] =  1, // =4
          [0b111] = 12,
        };
        mask >>= b[bits];
        uint32_t tmp[3] = {a[(mask>>4)&0b11], a[(mask>>2)&0b11], a[(mask)&0b11]};
        memcpy(a, tmp, 3*sizeof(uint32_t));
      }


      https://ideone.com/OTt0wH
      Ответить
      • Кокококому не слабо́ отсортировать четыре элемента?

        void sort4(uint32_t a[static 4])
        {
          uint64_t mask = 0x6C6361E12D2724E4;
          uint8_t bits = ((a[0] <= a[1])     ) | ((a[1] <= a[2]) << 1) | ((a[2] <= a[3]) << 2)
                       | ((a[0] <= a[2]) << 3) | ((a[1] <= a[3]) << 4) | ((a[0] <= a[3]) << 5);
          static const uint8_t b[] =
          {
            [0b000000] = 11,
            [0b000001] = 32,
            [0b000010] = 42,
            [0b000100] = 22,
            [0b000101] = 54,
            [0b001001] = 10,
            [0b001010] = 20,
            [0b001011] = 47,
            [0b010010] = 34,
            [0b010100] = 3,
            [0b010110] = 43,
            [0b011010] = 1,
            [0b100101] = 46,
            [0b101001] = 2,
            [0b101011] = 44,
            [0b101101] = 24,
            [0b110100] = 6,
            [0b110101] = 38,
            [0b110110] = 48,
            [0b111010] = 4,
            [0b111011] = 36,
            [0b111101] = 5,
            [0b111110] = 26,
            [0b111111] = 45,
          };
          mask >>= b[bits];
          uint32_t tmp[4] = {a[(mask>>6)&0b11], a[(mask>>4)&0b11], a[(mask>>2)&0b11], a[(mask)&0b11]};
          memcpy(a, tmp, 4*sizeof(uint32_t));
        }


        https://ideone.com/sy4XWH
        Ответить
        • Нашёл решение для пяти элементов. Кокококонстанта mask занимает 1820 битов. Вот её значение:
          0x125a4937ec80000125a4936c812480125a4936c800136c8124936c800125a5a48136c800125a4800137ec80125a4800136c936c8124800136c925a5a48000136c925a4801248136c925a48000125b7ec81248000125b6da5a480000125b6da48012480125b6da48000136c8136da4800012480124937ec8012480124936c936c8000124936c92481248124936c92480125a48136c924801248125b7ec80001248125b6c812481248125b6c80125a480125b6c801248136c8136c80124812480137ec8124812480136da5a48012480136da48136c8000136da4812481248136da481248


          Описание массива b занимает почти две тысячи символов, так что придётся публиковать отдельным комментарием.

          Ну почему в сишке нет типа uint1820_t?
          Ответить
          • 1280'h125... Именно поэтому я за "verilog".
            Ответить
            • Уже представил себе: сопроцессор на FPGA, умеющий выполнять одну операцию: сортировать массив из пяти элементов.
              Ответить
              • За один такт.

                К слову, там этот алгоритм не выглядит настолько бесполезным, как его сишная версия.
                Ответить
            • Я наглючил. Константа будет всего лишь 460-битной:
              0x29c05310a60c4c15182838506620ca8194232817102d405a10b40c68109c2133026444c851908b8116222c28584630887110d421a303444688


              Можно подключить GMP, но тогда весь пирфоманс потеряется:
              mpz_t mask;
              mpz_init (mask, 460);
              mpz_set_str(mask, "29c0...", 16);


              К слову: https://en.wikipedia.org/wiki/512-bit

              Можно отказаться от сдвигов и хранить константу в неупакованном виде, как в первом комментарии j123123:
              http://govnokod.ru/24496#comment421387
              Тогда она займёт 154 байта, что всего лишь в ≈ 2,7 раза больше упакованной.
              Ответить
              • >> 512-bit

                AVX-512 позволяет использовать 512-битный регистр только как массив 32-битных или 64-битных чисел. 512-битных целых питухов у него нет, так что 460-битную константу за один раз не сдвинешь даже на таком процессоре.
                Ответить
                • > не сдвинешь
                  Можно сдвинуть вправо на 0..31 бита чтобы получить low половинки и влево на 31..0 бита чтобы получить high половинки. Затем грубый сдвиг с 32-битным шагом через shuffle. И совместить половинки через or.
                  Ответить
                • З.Ы. Но тебе же не нужно двигать всю константу, ты только выбираешь из неё небольшие фрагменты. А это намного легче - грубый 32-битный shuffle + точный 64-битный сдвиг.
                  Ответить
            • Перевёл на "PHP" сортировку массива из пяти элементов с упакованной константой с реализацией сдвигов библиотекой GMP:
              https://ideone.com/Co824j
              Ответить
              • Переходим на следующий уровень безумия. Семижопая галапагосская черепаха Сортировка шести элементов:
                https://ideone.com/L4ImJg
                Ответить
                • Пожалойсто, не говори что ты это вручную пишешь, а то мой маленький петушьий мохг не вынесет этого.
                  Ответить
                  • Я могу скокококозать что угодно. Всё равно вы не сможете проверить.

                    На самом деле я написал генератор генераторов генераторов констант.

                    1. Суперпермутации для n = 3; 4; 5; 6 взял в готовом виде отсюда:
                    https://arxiv.org/pdf/1408.5108.pdf

                    2. Перевёл суперпермутацию в двоичную систему (для n = 3 и 4 выделил по 2 бита на элемент; для n = 5 и 6 выделил по 3 бита на элемент). Это константа mask. Выделил подстроки фиксированной длины (2*3, 2*4, 3*5, 3*6 битов для n = 3; 4; 5; 6 соответственно), отфильтровал из них те, которые годятся для нужных перестановок. Получил отображение: сдвиг константы mask → вариант перестановки. Замечу, что обратное отображение может быть неоднозначным.

                    3. Нагенерировал всевозможные перестановки чисел для заданного диапазона. Для каждой из них автоматически нашёл решение сортировки. Оно ищется тупо. Поскольку мы заранее знаем, какие значения могут быть у элементов (мы их сами генерировали), просто поочерёдно ищем, по какому индексу расположено каждое из этих значений. Также для каждой перестановки нашёл значение выражения bits. Получил отображение bits → способ расстановки.

                    4. Сопоставив отображения, полученные в п. 2 и 3, получил отображение bits → требуемый сдвиг mask, т. е. массив b.
                    Ответить
                    • Только что нагуглил суперпермутации для семёрки и для восьмёрки:
                      https://github.com/tigertv/superpermutation
                      Ответить
                    • > На самом деле я написал генератор генераторов генераторов констант.

                      Теперь кокомпутер сайентисты говнококода ломают голову над тем, скоколько поебени на крестошаблонах и кококонстэкспрах нужно, чтобы это сделать в кокомпилтайме на крестоговне.
                      Ответить
                      • А зачем? Эта кобенаторная экспоненциушня сильно быстро растёт. Больше, чем за 2-4 элементов в чистом виде наверно никому и не нужна даже на FPGA.
                        Ответить
                        • Из академического интереса.
                          Ответить
                        • О росте кобенаторной питушни:
                          http://oeis.org/A180632
                          (целый сайт, посвящённый числовым последовательностям!)

                          0, 1, 3, 9, 33, 153...

                          Obviously bounded below by n! + n - 1 and above by 2(n! - (n - 1)!) + 1.

                          A better lower bound is n! + (n - 1)! + (n - 2)! + n - 3 and a better upper bound is A007489.

                          ...

                          In October 2018 Greg Egan found new records for n=7, 8, 9: a(7) <= 5908, a(8) <= 46205, and a(9) <= 408966. More generally, for any n >= 7, a(n) <= n! + (n-1)! + (n-2)! + (n-3)! + n - 3.
                          Ответить
                        • Итог: классификация песцов.

                          1. Лёгкий песец: O(n²) –— это количество сравнений.
                          2. Песец средней тяжести: O(n!) –— это минимальный размер таблицы возможных перестановок.
                          3. Песец чуть-чуть потяжелее: сумма прогрессии, состоящей из факториалов –— это длина суперпермутации.
                          4. Полный песец: O(2 в степени n²) –— это сколько на самом деле занимает таблица перестановок (включая неиспользуемые элементы), потому что у нас она представлена разреженным массивом.

                          Именно из-за последнего таблица перестановок для сортировки семи элементов будет весить 4 мегабайта, а для сортировки восьми элементов –— почти гигабайт.

                          Учитывая, что обращение к массиву b производится единственный раз, его можно представить ассоциативным массивом (потеряв некоторое время на поиск индекса). Тогда к гигабайту мы подберёмся при попытке отсортировать двенадцать элементов.

                          В общем, для большого количества элементов в чистом виде этот алгоритм может представлять лишь академический интерес.
                          Ответить
                        • Проверил алгоритм для случая 7 элементов. Работает. Всевозможные тесты включать не стал, ограничился тестированием десятка вариантов. Экзешник весит 4,4 мегабайта. Ideone отказался принимать исходник, потому что он весит 130 килобайт (у них ограничение 64к).
                          Ответить
                          • Фрагмент:
                            void sort7(uint32_t a[static 7])
                            {
                              static const uint8_t tmp[] = {0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 0, 6, 1, 2, 3, 4, 0, 5, 6, 1, 2, 3, 4...
                              uint32_t bits = 
                                        ((a[0] <= a[1])     ) | ((a[1] <= a[2]) << 1) | ((a[2] <= a[3]) << 2) | ((a[3] <= a[4]) << 3) | ((a[4] <= a[5]) << 4) | ((a[5] <= a[6]) << 5)
                                      | ((a[0] <= a[2]) << 6) | ((a[1] <= a[3]) << 7) | ((a[2] <= a[4]) << 8) | ((a[3] <= a[5]) << 9) | ((a[4] <= a[6]) <<10)
                                      | ((a[0] <= a[3]) <<11) | ((a[1] <= a[4]) <<12) | ((a[2] <= a[5]) <<13) | ((a[2] <= a[6]) <<14) 
                                      | ((a[0] <= a[4]) <<15) | ((a[1] <= a[5]) <<16) | ((a[1] <= a[6]) <<17)
                                      | ((a[0] <= a[5]) <<18) | ((a[0] <= a[6]) <<19)
                                      | ((a[0] <= a[6]) <<20);
                            
                              static const uint16_t b[] =
                              {
                                [0x000000uL] = 2034,
                                [0x000001uL] = 2082,
                                [0x000002uL] = 2041,
                                [0x000004uL] = 2027,
                                [0x000005uL] = 2075,
                                [0x000008uL] = 563,
                                [0x000009uL] = 570,
                                [0x00000auL] = 556,
                                [0x000010uL] = 3322,
                            ...
                                [0x1ffffauL] = 3804,
                                [0x1ffffbuL] = 5164,
                                [0x1ffffduL] = 4672,
                                [0x1ffffeuL] = 3852,
                                [0x1fffffuL] = 0,
                              };
                              const uint32_t out[] = {a[tmp[b[bits]]], a[tmp[b[bits]+1]], a[tmp[b[bits]+2]], a[tmp[b[bits]+3]], a[tmp[b[bits]+4]], a[tmp[b[bits]+5]], a[tmp[b[bits]+6]]};
                              memcpy(a, out, sizeof(out));
                            }
                            Ответить
                            • Немного крестоблядства:
                              #include <map>
                              std::map<std::uint32_t, std::uint16_t> b;

                              Определение массива b из функции sort7 стираем.
                              В самом начале функции main добавляем:
                              b[0x000000uL] = 2034;
                                b[0x000001uL] = 2082;
                                b[0x000002uL] = 2041;
                                b[0x000004uL] = 2027;
                                b[0x000005uL] = 2075;
                                b[0x000008uL] = 563;
                                b[0x000009uL] = 570;
                                b[0x00000auL] = 556;
                                b[0x000010uL] = 3322;
                              ...
                                b[0x1ffffauL] = 3804;
                                b[0x1ffffbuL] = 5164;
                                b[0x1ffffduL] = 4672;
                                b[0x1ffffeuL] = 3852;
                                b[0x1fffffuL] = 0;

                              Больше ничего не менял.

                              Теперь экзешник весит жалких полмегабайта вместо четырёх с половиной.

                              Кстати, существует вменяемый способ инициализации такой карты, чтобы не писать 100500 операторов присваивания?
                              Ответить
                              • А ведь вариант с std::map будет жрать в два раза больше памяти, чем кажется: сначала константы присутствуют в коде, потом после инициализации std::map они скопируются в область данных.
                                Ответить
                                • Предлагаю найти нужные паттерны в числе пи и записать оффсеты.
                                  Ответить
                                  • Пример: в первой тысяче знаков числа Пи кобенация «123» вообще не встречается, а кобенация «321» нашлась по смещению 959 (если считать, что целая часть находится по смещению ноль).

                                    У меня нехорошие предчувствия по поводу пирфоманса...
                                    Ответить
                                  • Голландский математик Брауэр в первой половине XX века привёл в качестве примера бессмысленной задачи поиск в десятичном разложении π последовательности 0123456789 — по его мнению, нужная для этого точность никогда не будет достигнута. В конце XX века эта последовательность была обнаружена, она начинается с 17 387 594 880-го знака после запятой.
                                    Ответить
                                  • Наткнулся на интересный факт:
                                    https://ru.wikipedia.org/wiki/Точка_Фейнмана

                                    А вдруг нас обманывают и на самом деле число Пи рационально: 761-я цифра равна 5, а дальше идут нули? Шесть девяток подряд в плавающем питухе выглядят подозрительно.
                                    Ответить
                                    • Сколько годноты Вы приносите на ГК!
                                      Ещё чуть-чуть, и если Вы скажете "А я на самом деле пользователь _____", то ГК запомнит _____ как файку Новогоднего петуха.
                                      Ответить
                              • > вменяемый способ инициализации такой карты, чтобы не писать 100500 операторов присваивания?

                                #include <map>
                                std::map<std::uint32_t, std::uint16_t> b { // initializer list
                                  {0x000000uL, 2034},
                                  {0x000001uL, 2082},
                                  {0x000002uL, 2041},
                                  {0x000004uL, 2027},
                                  {0x000005uL, 2075},
                                  {0x000008uL, 563},
                                  {0x000009uL, 570},
                                  {0x00000auL, 556},
                                  {0x000010uL, 3322},
                                ...
                                  {0x1ffffauL, 3804},
                                  {0x1ffffbuL, 5164},
                                  {0x1ffffduL, 4672},
                                  {0x1ffffeuL, 3852},
                                  {0x1fffffuL, 0}
                                };
                                Ответить
                                • Спасибо. Я предполагал, что должна быть инициализация массивом пар, но в явном виде не заметил такого.

                                  Экзешник полегчал: вместо 100500 вызовов перегруженных операторов [] и = теперь только массив пар и один вызов кокококонструктора. Итого теперь около 370 килобайт.
                                  Ответить
                                • Следующий «перл»:
                                  std::map<std::uint32_t, std::uint16_t> b {
                                      {0x0000000, 13701},
                                      {0x0000001, 14039},
                                      {0x0000002, 13764},
                                      {0x0000004, 13709},
                                      {0x0000005, 14047},
                                      {0x0000008, 13693},
                                      {0x0000009, 14031},
                                      {0x000000a, 13756},
                                  ...
                                      {0xffffff5, 32275},
                                      {0xffffff6, 26225},
                                      {0xffffff7, 41413},
                                      {0xffffffa, 25950},
                                      {0xffffffb, 38113},
                                      {0xffffffd, 32613},
                                      {0xffffffe, 26288},
                                      {0xfffffff, 0},
                                  };
                                  
                                  void sort8(uint32_t a[8])
                                  {
                                    static const uint8_t tmp[] = {0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 0, 7, 1, 2, 3, 4, 5, 0, 6, 7...
                                    uint32_t bits = 
                                              ((a[0] <= a[1])     ) | ((a[1] <= a[2]) << 1) | ((a[2] <= a[3]) << 2) | ((a[3] <= a[4]) << 3) | ((a[4] <= a[5]) << 4) | ((a[5] <= a[6]) << 5) | ((a[6] <= a[7]) << 6)
                                            | ((a[0] <= a[2]) << 7) | ((a[1] <= a[3]) << 8) | ((a[2] <= a[4]) << 9) | ((a[3] <= a[5]) <<10) | ((a[4] <= a[6]) <<11) | ((a[5] <= a[7]) <<12)
                                            | ((a[0] <= a[3]) <<13) | ((a[1] <= a[4]) <<14) | ((a[2] <= a[5]) <<15) | ((a[3] <= a[6]) <<16) | ((a[4] <= a[7]) <<17) 
                                            | ((a[0] <= a[4]) <<18) | ((a[1] <= a[5]) <<19) | ((a[2] <= a[6]) <<20) | ((a[3] <= a[7]) <<21)
                                            | ((a[0] <= a[5]) <<22) | ((a[1] <= a[6]) <<23) | ((a[2] <= a[7]) <<24)
                                            | ((a[0] <= a[6]) <<25) | ((a[1] <= a[7]) <<26)
                                            | ((a[0] <= a[7]) <<27);
                                  
                                    const uint32_t out[] = {a[tmp[b[bits]]], a[tmp[b[bits]+1]], a[tmp[b[bits]+2]], a[tmp[b[bits]+3]], a[tmp[b[bits]+4]], a[tmp[b[bits]+5]], a[tmp[b[bits]+6]], a[tmp[b[bits]+7]]};
                                    memcpy(a, out, sizeof(out));
                                  }


                                  Сортирует 8 элементов, брат жив. Экзешник весит 700 килобайт. С тупым сишным массивом он бы весил гигабайт.
                                  Ответить
                                  • Конечно, по оценке песцов, O(N^2) сравнений - это не самое страшное, что тут происходит, но нельзя ли приблизиться к теоретическому минимуму (заодно упростить b)?
                                    Или это приведёт к нарушению пирфоманса из-за лишних ветвлений?
                                    Нет ли хотя бы битовых хаков для восстановления результатов сравнений элементов из имеющихся O(NlogN) битов?
                                    Ответить
                                    • Мда, похоже, нельзя или нет смысла. Для O(NlogN) нужны сравнения в зависимости от других сравнений. Придётся сравнивать в лучшем случае в O(logN) подхода, а не одновременно, как сейчас.
                                      Ответить
                                      • Где-то ниже приведены примеры сетей сравнения, у которых тоже константное количество сравнений, при этом общее количество сравнений меньше, но количество слоёв (в каждом слое сравнения можно производить одновременно) больше.

                                        При N=8 «инновационный алгоритм» требует 8*7/2 = 28 сравнений, но слой один. Классическая битонная сеть требует 24 сравнения, но у неё 6 слоёв. Если на первом этапе использовать два параллельно работающих «инновационных алгоритма» для сравнения 4 элементов, то количество слоёв можно сократить до 4 (первые три слоя утопчутся в один).
                                        Ответить
                                    • Особенность оригинального алгоритма в том, что при данном N количество сравнений является константой при любых входных данных, даже несмотря на то, что обычно оно избыточно (даже при N=3 можно заметить, что при a[0]<a[1]<a[2] сравнивать a[0] с a[2] уже не нужно).
                                      Ответить
                                    • Как можно упростить, не используя if, пока не знаю. Есть идеи неявного ветвления:
                                      1. Воспользоваться ленивостью операторов || и &&.
                                      2. Возвращать указатели функции (тут будут некоторые расходы на передачу управления).

                                      Осталось дело за «малым»: придумать алгоритм.

                                      Пусть
                                      bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1)

                                      Тогда:
                                      1. При bits = 0 ответ a[2], a[1], a[0].
                                      2. При bits = 1 в ответе a[1] на последнем месте, а a[0] и a[2] нужно упорядочить.
                                      3. При bits = 2 в ответе a[1] на первом месте, а a[0] и a[2] нужно упорядочить.
                                      4. При bits = 3 ответ a[0], a[1], a[2].
                                      Ответить
                                      • В общем, для N=3 в 50% случаев можно сократить количество сравнений. В остальных же 50% случаев потребуется второй шаг.
                                        Ответить
                    • Отлично вы тут упоролись.
                      Ответить
                      • И это Вы называете отлично? Отлично было бы, если:

                        1. Реализовали бы генерацию суперпермутации для произвольного количества элементов.

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

                        3. Суперпермутация занимала бы меньше места. У меня модифицированный алгоритм: вместо представления суперпермутации как массива целых я использовал зожатие в битовое поле и сдвиг для выделения нужной пермутации. По этой причине используются не все элементы суперпермутации. Гипотетически её можно перепаковать, убрав неиспользуемые биты.

                        4. Массив b занимал бы меньше места. Однако, боюсь, что если его зожму, то потеряю пирфоманс. Вопрос об оптимальном представлении этого массива остаётся открытым.

                        5. Было бы больше примеров на других ЯП.
                        Ответить
                        • К слову об избыточности массива b: в нём возможны записи для нереальных вариантов вроде a[0]<a[1]<a[2]<a[0]. В сишном коде эти элементы занимают память, хотя и хранят нули или мусор. Т. е. вообще массив в определённой степени разреженный.
                          Ответить
                          • Готовые оценки:
                            ┌─┬──────────┬────────────┬──────────┬─────────┬────────────┬────────────┐
                            │n│количество│sizeof(mask)│count(b)  │count(b) │sizeof(b[0])│sizeof(b[0])│
                            │ │сравнений │битов×э-тов │брутто    │нетто    │неупак. mask│упак. mask  │
                            ├─┼──────────┼────────────┼──────────┴─────────┼────────────┼────────────┤
                            │2│        1 │  1×3       │тривиальный = {1, 0}│            │            │
                            ├─┼──────────┼────────────┼──────────┬─────────┼────────────┼────────────┤
                            │3│        3 │  2×9       │ 8        │ 6       │1 (4 бита)  │1 (5 битов) │
                            ├─┼──────────┼────────────┼──────────┼─────────┼────────────┼────────────┤
                            │4│        6 │  2×33      │ 64       │ 24      │1 (5 битов) │1 (7 битов) │
                            ├─┼──────────┼────────────┼──────────┼─────────┼────────────┼────────────┤
                            │5│       10 │  3×153     │ 1024     │ 120     │1 (8 битов) │2 (9 битов) │
                            ├─┼──────────┼────────────┼──────────┼─────────┼────────────┼────────────┤
                            │6│       15 │  3×872     │ 32768    │ 720     │2 (10 битов)│2 (12 битов)│
                            └─┴──────────┴────────────┴──────────┴─────────┴────────────┴────────────┘
                            Ответить
                          • Продолжение:
                            ┌─┬──────────┬────────────┬──────────┬─────────┬────────────┬────────────┐
                            │n│количество│sizeof(mask)│count(b)  │count(b) │sizeof(b[0])│sizeof(b[0])│
                            │ │сравнений │битов×э-тов │брутто    │нетто    │неупак. mask│упак. mask  │
                            ├─┼──────────┼────────────┼──────────┼─────────┼────────────┼────────────┤
                            │7│       21 │  3×5908    │ 2,1 млн  │ 5040    │2 (13 битов)│2 (15 битов)│
                            ├─┼──────────┼────────────┼──────────┼─────────┼────────────┼────────────┤
                            │8│       28 │  3×46205   │ 0,3 млрд │ 40320   │2 (16 битов)│4 (18 битов)│
                            ├─┼──────────┼────────────┼──────────┼─────────┼────────────┼────────────┤
                            │9│       36 │  4×408966  │ 69 млрд  │ 362880  │4 (19 битов)│4 (21 бит)  │
                            ├─┼──────────┼────────────┼──────────┼─────────┼────────────┼────────────┤
                            │n│ n*(n-1)/2│ к-во э-тов │ 2 в степ.│ n!      │            │            │
                            │ │          │  A180632   │ n*(n-1)/2│         │            │            │
                            │ │          │  <= ∑k!    │          │         │            │            │
                            └─┴──────────┴────────────┴──────────┴─────────┴────────────┴────────────┘
                            Ответить
                            • Брутто — это сколько элементов сейчас хранит программа.
                              Нетто — это сколько элементов реально используются программой.

                              Выводы:
                              1. Реализовывать сортировку в таком виде для n > 6 практически бессмысленно. Придётся либо тратить гигабайты оперативки, либо хранить b как ассоциативный массив (но в последнем случае придётся тратить такты на поиск). Также b можно заменить функцией, но открыт вопрос об её эффективной реализации (не тупым же свитч-кейсом её делать).

                              2. При n > 4 зожатие суперпермутации в битовое поле вряд ли приведёт к заметной экономии памяти (для n=5 и n=8 это зожатие приводит к увеличению размера элемента массива b).
                              Ответить
    • А ведь у этой фигни фиксированное время работы: для любых входных данных этот алгоритм производит фиксированное количество сравнений и фиксированное количество копирований. Это может быть важным для противодействия атаке по времени.
      Ответить
      • Пузырьковую сортировку тоже можно под фиксированное время подогнать.
        Ответить
        • Кстати, пузырьковая сортировка внутри себя использует частный случай этого алгоритма: сортировку массива из двух элементов.

          А существуют ли интересные алгоритмы, использующие внутри себя сортировку массива из трёх или из четырёх элементов?
          Ответить
          • Сортировку из трех или четырёх элементов можно в merge sort использовать
            Ответить
            • Ещё можно использовать на самом глубоком этапе qsort, если размер подмассива оказался небольшим, или в корзинной сортировке, если в корзине немного элементов.

              Посмотрел вот это:
              https://ru.wikipedia.org/wiki/Сеть_сортировки
              https://ru.wikipedia.org/wiki/Битонная_сортировка

              На начальных этапах битонной сортировки можно использовать.
              Ответить
              • > битонной сортировки
                Какой битон )))

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

                З.Ы. Кстати, можно же через SSE попробовать - составить маску для shuffle...
                Ответить
                • Некоторые этапы сетей можно параллелить. Например, у этих сетей первоначальную сортировку блоков по 4 элемента можно выполнить «инновационным алгоритмом»:
                  https://upload.wikimedia.org/wikipedia/commons/thumb/c/c6/BitonicSort.svg/843px-BitonicSort.svg.png
                  https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
                  https://en.wikipedia.org/wiki/Pairwise_sorting_network

                  У битонной параллелится всё, что на схеме внутри коричневых и розовых блоков.

                  >> Какой битон )))

                  У меня было желание написа́ть «битонная сартерофка». Ну чтобы было уж совсем ниграматна.
                  Ответить
                  • > внутри блоков
                    Ну я поэтому и писал про слои. В каждом слое компаратор. Каждый слой "ждёт" пока стабилизируются предыдущие. А компараторы медленные по сравнению с мультиплексорами (причём чем больше бит - тем медленнее).

                    В битонной сети для 16 элементов получается 10 слоёв по 8 компараторов. По схеме из данного треда получится 120 компараторов, всего в 1.5 раза больше. Зато вместо десяти слоёв будет один.
                    Ответить
                    • Попробую показать на схемах, что я имел в виду. Обозначу «инновационный алгоритм» sort4 зелёным прямоугольником.

                      Тогда модифицированная битонная для 16 будет выглядеть так (предварительный этап сортировки пар стал не нужен):
                      https://i.imgur.com/GYw0yDx.png

                      Batcher odd-even переделаем так:
                      https://i.imgur.com/FeQznf2.png
                      Маниакальный вариант:
                      https://i.imgur.com/V07ZZuc.png

                      Pairwise переделаем так:
                      https://i.imgur.com/Zz3GdLa.png
                      Маниакальный вариант:
                      https://i.imgur.com/JM4RDAC.png
                      Ответить
                      • Кстати, кобенация «инновационного алгоритма» и битонной сортировки работает:
                        void sort6(uint32_t a[static 6])
                        {
                          sort3(a + 0); sort3(a + 3);
                          sort2(a + 0, a + 5); sort2(a + 1, a + 4); sort2(a + 2, a + 3);
                          sort3(a + 0); sort3(a + 3);
                        }


                        https://ideone.com/Ayyl09

                        Я не случайно так отформатировал код: сортировки на каждой строчке можно выполнять параллельно.

                        P.S. Ideone выдаёт error 502 вместо кода, потому что он длинный (720 перестановок чисел), но сам код при этом работает. Хотя 20 килобайт кода — не так много. Они его там алгоритмом Шлемиля раскрашивают что ли?
                        Ответить
                        • Для сравнения для пяти:
                          void sort5(uint32_t a[static 5])
                          {
                            sort3(a + 0);        sort2(a + 3, a + 4);
                            sort2(a + 0, a + 4); sort2(a + 1, a + 3);
                            sort2(a + 0, a + 1); sort3(a + 2);
                          }


                          https://ideone.com/9I7048
                          Ответить
                        • Альтернативная сеть для шести (просто тестирую):
                          void sort6(uint32_t a[static 6])
                          {
                            sort4(a + 0);
                            sort4(a + 2); sort2(a + 0, a + 1);
                            sort4(a + 0);
                          }


                          https://ideone.com/mQGhHY
                          Ответить
                • void sort(int32_t data[4])
                  {
                      __m128i a = _mm_loadu_si128((const __m128i*)data);
                  
                      __m128i c1 = _mm_cmpgt_epi32(a, _mm_shuffle_epi32(a, 0x39));
                      __m128i c2 = _mm_cmpgt_epi32(a, _mm_shuffle_epi32(a, 0x4E));
                      __m128i c3 = _mm_cmpgt_epi32(a, _mm_shuffle_epi32(a, 0x93));
                  
                      __m128i p = _mm_sub_epi32(_mm_sub_epi32(_mm_setzero_si128(), c1),
                                                _mm_add_epi32(c2, c3));
                  
                      __m128i m = _mm_add_epi32(_mm_mullo_epi32(p, _mm_set1_epi32(0x04040404)),
                                                _mm_set1_epi32(0x03020100));
                  
                      __m128i r = _mm_shuffle_epi8(a, m);
                  
                      _mm_storeu_si128((__m128i*)data, r);
                  }
                  Ответить
                  • На 20% быстрее чем std::sort().
                    Ответить
                  • Ничего не понимаю! Придётся переводить:
                    // 0x39 = 0b 00 11 10 01
                    c1[0] = -1 * (a[0] > a[1]);
                    c1[1] = -1 * (a[1] > a[2]);
                    c1[2] = -1 * (a[2] > a[3]);
                    c1[3] = -1 * (a[3] > a[0]);
                    // 0x4E = 0b 01 00 11 10
                    c2[0] = -1 * (a[0] > a[2]);
                    c2[1] = -1 * (a[1] > a[3]);
                    c2[2] = -1 * (a[2] > a[0]);
                    c2[3] = -1 * (a[3] > a[1]);
                    // 0x93 = 0b 10 01 00 11
                    c2[0] = -1 * (a[0] > a[3]);
                    c2[1] = -1 * (a[1] > a[0]);
                    c2[2] = -1 * (a[2] > a[1]);
                    c2[3] = -1 * (a[3] > a[2]);
                    for (i = 0; i < 4; ++i) {
                        p[i] = -c1[i] - c2[i] - c3[i];
                        m[i] = p[i] * 4 + i;
                    }
                    
                    r[0] = a[m & 3];
                    r[1] = a[(m >> 2) & 3];
                    r[2] = a[(m >> 4) & 3];
                    r[3] = a[(m >> 6) & 3];


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

                    P.S. Я накосячил в последних строчках: там _mm_shuffle_epi8, а не _mm_shuffle_epi32, как мне показалось.
                    Ответить
                    • P.P.S. Ещё и с умножением я запутался...
                      for (i = 0; i < 4; ++i) {
                          p[i] = -c1[i] - c2[i] - c3[i];
                          m[i] = p[i] * 0x04040404 + 0x03020100;
                      }


                      В общем, 12 сравнений вместо шести, зато AssParallel.
                      Ответить
                    • _mm_shuffle_epi32 не умеет по регистру перемешивать, поэтому пришлось эти костыли с умножением городить :(
                      Ответить
                      • Понял. _mm_shuffle_epi32 требует immediate, следовательно, пришлось бы снимать защиту и писа́ть самомодифицирующийся код.
                        Ответить
                      • Из любопытства посмотрел документацию по первому «Итаниуму», ну чтобы сравнить возможности. На первый взгляд набор его инструкций напоминает голый «SSE» или «MMX» без «нормальных» инструкций (даже мнемоники некоторых инструкций в интеловском описании такие же). Однако, для перемешивания предназначена единственная инструкция mux, таблица преобразований задаётся в коде (immediate), в регистре задать нельзя. Зато на нём можно выполнять три произвольные инструкции AssParallel (это они и называют «VLIW»), а ещё у него есть предикаты, как в «ARM», чтобы пропускать инструкцию по условию без джампов.
                        Ответить
                        • Ну всё-таки динамическое планирование (как сейчас в интелах), имхо, шустрее чем vliw - лучше подстраивается к переменным задержкам в духе чтения из памяти. Конпелятор не сможет всё это учесть...
                          Ответить
                          • С одной стороны, динамическое планирование лучше подстраивается, с другой стороны, оно греет процессор (в случае VLIW планирование выполняет конпелятор один раз, а тут приходится каждый раз планировать).

                            В общем, тема для холивара.
                            Ответить
                        • Ну и современные x86 при хорошем конпеляторе чем-то похожи на vliw - загребают "длинное слово" в 16 байт и пытаются все инструкции из него зашедулить одновременно.
                          Ответить
                    • > Даже Царь был против таких функций. Он считал, что нужно использовать обычные арифметические операции, а конпелятор должен уметь это оптимизировать за тебя.
                      > Для этого он пытался подобрать такой код, который гэцэцэшечке (а других вменяемых конпеляторов по мнению Царя не существует) было легче оптимизировать.

                      Именно поэтому я за «Царя».
                      Ответить
                  • Зароллим анролл обратно:
                    for(i = 0; i < 4; ++i) {
                        c1[i] = (a[i] > a[(i+1) % 4]);
                        c2[i] = (a[i] > a[(i+2) % 4]);
                        c3[i] = (a[i] > a[(i+3) % 4]);
                        p[i] = c1[i] + c2[i] + c3[i];
                    }

                    Зароллим ещё раз:
                    for(i = 0; i < 4; ++i) {
                        p[i] = 0;
                        for(j = 0; j < 3; ++i) {
                            p[i] += (a[i] > a[(i+j) % 4]);
                        }
                    }

                    Нигде не ошибся?
                    Ответить
                    • Ну тип того. Считаем сколько раз число оказывается больше других и ставим его на соотв. позицию.
                      Ответить
                      • А что будет, если в массиве два равнозначных элемента?
                        Дано: {1, 2, 2, 3}
                        Единица ноль раз больше кого-нибудь => ставим её на место №0.
                        Двойка один раз больше единицы => ставим её на место №1.
                        Тройка три раза больше других элементов => ставим её на место №3.

                        Место №2 остаётся вакантным.
                        Ответить
                        • Бля. Мой код вообще не работает. Отсортировал один кейс, я и обрадовался... Вычисляю то я позицию куда надо ставить, а shuffle не ставит, он выбирает. Короче хуйня полная получилась.
                          Ответить
                          • Должно быть типа r[p[i]] = a[i], а ты сделал r[i] = a[p[i]] что ли? Т. е. перепутаны откуда и куда?
                            Ответить
                            • Ну тип того.
                              Ответить
                              • Значит, матрицу преобразования нужно ещё как-нибудь транспонировать?
                                Ответить
                                • Да, но пока не получается придумать, как это слепить из имеющихся инструкций. Отчасти из-за того, что имеющихся инструкций дохуя и они сложные. Пока разберёшься как все эти shuffle да unpack работают...
                                  Ответить
                    • индус-программист держит бложек наподобие stackoverflow...
                      Ответить
                  • А вообще мне нравится вид этого кода. Уже выражением _mm_shuffle_epi32(a, 0x39) можно пугать чайников.
                    Ответить
                    • Не знаю, у меня сразу же первая мысль была об этих SSE инструкциях.

                      Кто видел как в AVX-512 регистрах шаффлят зигзаг после DCT и квантования, того такой фигнёй не испугать.
                      Ответить
                      • > зигзаг после DCT

                        Самый ёбнутый зигзаг вроде в форматах с интерлейсингом?
                        Ответить
                  • Хех, не получается пофиксить этот код. Заебало. Пусть будет так:
                    void sort(int32_t data[4])
                    {
                        __m128i a = _mm_loadu_si128((const __m128i*)data);
                    
                        __m128i s1 = _mm_shuffle_epi32(a, 0xB1);
                        __m128i x1 = _mm_max_epi32(a, s1);
                        __m128i y1 = _mm_min_epi32(a, s1);
                        a = _mm_castps_si128(_mm_blend_ps(_mm_castsi128_ps(x1), _mm_castsi128_ps(y1), 0x09));
                    
                        __m128i s2 = _mm_shuffle_epi32(a, 0x4E);
                        __m128i x2 = _mm_max_epi32(a, s2);
                        __m128i y2 = _mm_min_epi32(a, s2);
                        a = _mm_castps_si128(_mm_blend_ps(_mm_castsi128_ps(x2), _mm_castsi128_ps(y2), 0x03));
                    
                        __m128i s3 = _mm_shuffle_epi32(a, 0xB1);
                        __m128i x3 = _mm_max_epi32(a, s3);
                        __m128i y3 = _mm_min_epi32(a, s3);
                        a = _mm_castps_si128(_mm_blend_ps(_mm_castsi128_ps(x3), _mm_castsi128_ps(y3), 0x05));
                    
                        _mm_store_si128((__m128i*)data, a);
                    }
                    Вдвое быстрее чем std::sort().
                    Ответить
                    • А как он работает, если в массиве есть неуникальные значения?
                      Ответить
                      • Нормально, на этот раз я полным покрытием тестировал. Ну и это обычная бетонная сортирующая сеть.
                        Ответить
                        • >> бетонная

                          А ещё мне нравится, что «concrete» с английского переводится как «цемент».
                          Ответить
                  • > _mm_shuffle_epi32

                    О, я как раз искал шаффлы.
                    В принципе уже можно и на AVX-2 хуйнуть. Чтобы по 256 бит.
                    Ответить
    • Инновационная вставка элемента в массив:
      void insert3(uint32_t in[static 3], uint32_t value, uint32_t out[static 4])
      {
        /*                  0      1      2      3      4      5      6      7      8      9      10     11     12    */
        uint32_t tmp[13] = {value, in[0], in[1], in[2], value, in[0], in[1], value, in[2], in[0], value, in[1], in[2]};
        uint8_t bits = ((value <= in[0]) << 2 ) | ((value <= in[1]) << 1) | (value <= in[2]);
        static const uint8_t b[] =
        {
          [0b000] = 1,
          [0b001] = 5,
          [0b010] = 255,
          [0b011] = 9,
          [0b100] = 255,
          [0b101] = 255,
          [0b110] = 255,
          [0b111] = 0
        };
        if (b[bits] > sizeof(tmp)/sizeof(uint32_t)) {
          printf("Kakoj bagor )))\n");
          exit(-1);
        }
        memcpy(out, tmp + b[bits], 4*sizeof(uint32_t));
      }


      https://ideone.com/cgnvBp
      Ответить
    • void sort3(uint32_t a[static 3])
      {
        const uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
        static const uint8_t b2[][3] = 
        {
          {2, 1, 0}, {2, 0, 0}, {1, 2, 0},
          {}, {},
          {0, 2, 1}, {1, 0, 2}, {0, 1, 2}
        };
        const uint32_t out[3] = {a[b2[bits][0]], a[b2[bits][1]], a[b2[bits][2]]};
        memcpy(a, out, sizeof(out));
      }
      Ответить
      • Фикс
        static const uint8_t b2[][3] = 
        {
          {2, 1, 0}, {2, 0, 1}, {1, 2, 0},
          {}, {},
          {0, 2, 1}, {1, 0, 2}, {0, 1, 2}
        };
        Ответить
      • Ну это уже слишком понятно выглядит.
        Ответить
        • void sort3(uint32_t a[static 3])
          {
            const uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
            static const uint8_t b2[] = 
            {
              0x24, 0x21, 0x18,
              {}, {},
              0x09, 0x12, 0x06
            };
            const uint32_t out[3] = {a[(b2[bits]>>4)%4], a[(b2[bits]>>2)%4], a[b2[bits]%4]};
            memcpy(a, out, sizeof(out));
          }

          А так?
          Ответить
          • void sort3(uint32_t a[static 3])
            {
              const uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
              static const uint64_t b2 = 0x0612090000182124;
              };
              uint8_t tmp = b2 >> (bits<<3);
              const uint32_t out[3] = {a[(tmp>>4)%4], a[(tmp>>2)%4], a[tmp%4]};
              memcpy(a, out, sizeof(out));
            }
            Ответить
            • void sort3(uint32_t a[static 3])
              {
                const uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
                static const uint32_t b2 = 0x263008BC;
                uint8_t tmp = (b2 >> (bits*4))*3;
                const uint32_t out[3] = {a[(tmp>>4)%4], a[(tmp>>2)%4], a[tmp%4]};
                memcpy(a, out, sizeof(out));
              }
              Ответить
              • Ошибка вышла:
                uint8_t tmp = ((b2 >> (bits*4))%16)*3;

                Вот так работает.
                Ответить
                • Ещё вместо страшных (tmp>>4)%4 можно использовать битовые поля:
                  struct pituh {
                  char first: 2;
                  char second: 2;
                  char third: 2;
                  }


                  А вот битовых массивов в сишке, кажется, нет.
                  Ответить
                  • Переписал, тесты проходит:
                    typedef union {
                      uint8_t integral;
                      struct {unsigned char a2: 2, a1: 2, a0: 2, reserved: 2;} at;
                    } indices;
                    
                    void sort3(uint32_t a[static 3])
                    {
                      uint8_t bits = (a[0] <= a[1]) | ((a[1] <= a[2]) << 1) | ((a[0] <= a[2]) << 2);
                      static const uint32_t b2 = 0x263008BC;
                      indices index = {((b2 >> (bits*4))%16)*3};
                      uint32_t out[3] = {a[index.at.a0], a[index.at.a1], a[index.at.a2]};
                      memcpy(a, out, 3*sizeof(uint32_t));
                    }
                    Ответить
                    • Для сортировки четырёх элементов битоёбский вариант уже не годится: там константа b2 займёт в 8 раз больше места. Можно решить библиотекой «GMP», либо перевести на «Фрипаскаль»/«Дельфи» и записать такую длинную константу через множества.
                      Ответить
                      • 4 SSE регистра хватит под таблицу. Вечером набросаю прототип.
                        Ответить
                      • Вот такая херь получилась:
                        const uint32_t p[] = {
                            0x04040404, 0x01210d00, 0x0f1a0308, 0x0a3f0a0c,
                            0x00a404a4, 0x00480c58, 0x001008cc, 0x00fc0030,
                            0x00003f00, 0x33200430, 0x21302120, 0x12101a10,
                            0x0020fca0, 0x0000a4f0, 0x00304840, 0x00101010,
                        };
                        
                        
                        void sort4_2(int32_t data[4])
                        {
                            __m128i a = _mm_loadu_si128((const __m128i*)data);
                        
                            int c1 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpgt_epi32(a, _mm_shuffle_epi32(a, 0xEE))));
                            int c2 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpgt_epi32(a, _mm_shuffle_epi32(a, 0x39))));
                        
                            __m128i m = _mm_srl_epi32(_mm_load_si128((const __m128i*)(p + c1 * 4)),
                                                      _mm_set_epi32(0, 0, 0, c2 * 2));
                            m = _mm_and_si128(m, _mm_set1_epi32(0x03));
                            m = _mm_mullo_epi32(m, _mm_set1_epi32(0x04040404));
                            m = _mm_add_epi32(m, _mm_set1_epi32(0x03020100));
                        
                            a = _mm_shuffle_epi8(a, m);
                        
                            _mm_store_si128((__m128i*)data, a);
                        }
                        Но она даже медленнее std::sort'а... Походу лучше той бетонки через min/max я ничего не запилю ;(
                        Ответить
        • Для четырёх элементов:
          typedef union {
            uint8_t integral;
            struct {unsigned char a3: 2, a2: 2, a1: 2, a0: 2;} at;
          } indices;
          
          void sort4(uint32_t a[static 4])
          {
            uint8_t bits = ((a[0] <= a[1])     ) | ((a[1] <= a[2]) << 1) | ((a[2] <= a[3]) << 2)
                         | ((a[0] <= a[2]) << 3) | ((a[1] <= a[3]) << 4) | ((a[0] <= a[3]) << 5);
            static const char b2[] = "LKH><;@ABCFBORMAND(-4-$-)&&&&&&&///////\x12\x12\x13\x12\x12\x0f\x0f\x0f\x0f\x0f-1-1-!!!!\x1a\n\x19\r\x19\t";
            indices index = {b2[bits]*3};
            uint32_t out[4] = {a[index.at.a0], a[index.at.a1], a[index.at.a2], a[index.at.a3]};
            memcpy(a, out, 4*sizeof(uint32_t));
          }


          https://ideone.com/MLwwdw
          Ответить
          • В константе b2 смысловую нагрузку несут 24 символа из 64, поэтому 40 символов я выбрал случайным образом.
            Ответить
            • Это очевидно.
              Ответить
              • Борманду это очевидно, а какой-нибудь пэхапэшник может и не догадаться.
                Ответить
                • Кстати, у меня в sse'шной версии получилось 29 из 64. Из-за того, что одно из сравнений вверх-ногами, походу. Иначе одинаковые числа криво сортировались.
                  Ответить
              • Охуеть, пять года прошло. А ведь почти как вчера было…
                Ответить
      • К слову, в sse можно получить bits за 3 инструкции (shuffle + cmpgt + movemask). Для 4 элементов - где-то за 6-8 инструкций. Ну и перестановка делается за один shuffle. Остается эффективно записать табличку, чтобы её легко было подать на вход shuffle...
        Ответить
        • Но походу против 15 инструкций бетонной сортировки (см. выше) сложно что-то придумать.
          Ответить
        • SSE-питушня это уже неуниверсальный алгоритм, который завязан на какие-то говноинструкции, доступные только в каких-то моделях процессоров, да и работать он будет только с какими-то определенными типами (какие-нибудь double и бигинты уже не отсортировать). Лучше пилить алгоритмы в общем виде, которые б работали тупо через сравнение. Ну а потом можно уже переписывать прямо на ассемблер для максимальной оптимизации, без всех этих полумер в виде интринсиков
          Ответить
          • показать все, что скрытоvanished
            Ответить
          • К примеру алгоритм сортировки подсчётом наверное самый неуниверсальный, но он работает за линейное время, и, кмк, для упорядочивания массива байт или 16-битных слов очень годный.
            Ответить
            • Я придумал кстати новый инновационный алгоритм сортировки. Сделаем моссив из простых чисел и единицы.
              uint16_t primes[] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41...}

              И вот если надо отсортировать массив {6, 5, 12} то берем и перемножаем
              primes[6] * primes[5] * primes[12]

              (можно даже перемножать через SSE для максимальной оптимизации)
              и потом осталось только факторизовать получившееся число. Можно сделать моссив из всех возможных вореций перемножения трех чисел из моссива primes и там двоичным поиском находить ответ за логарифмическое время - оптимизированно.
              Ответить
              • показать все, что скрытоvanished
                Ответить
              • показать все, что скрытоvanished
                Ответить
              • Единица лишняя, имхо. Из-за неё массивы с нулями не отсортируются.
                Ответить
                • Отсортированный массив с нулями это массив с нулями. Нули просто вперед вылазят все. Если массив только лишь из нулей состоит, он отсортируется в одни нули, и всё правильно. Если массив это "всюду нули и три единицы, ну типа" 1 1 1 0 0 0 0 0.... то будет у нас 2*2*2*1*1*1*1*1 .... и в итоге потом мы поймем что у нас только три единицы, остальное - нули. В общем это не мешает сортировке, и тут все норм
                  Ответить
                  • А откуда я знаю, сколько их там? Факторизация единички не выдаёт. А считать их на входе - пирфоманс упадёт.
                    Ответить
                    • Из общего кокококоличества элементов вычесть сумму степеней в fuck-торизации (кроме степени единицы, разумеется).
                      Ответить
                    • Чет я вообще не вижу проблемы. У тебя массив известной длинны, ну скажем 100 элементов. Ты его этим методом перемножаешь и факторизуешь - получаем 2^3 * 3^4 * 5^3. Это значит что у тебя 0, 0, 0, 0, ..... 1, 1, 1, 2, 2, 2, 2, 3, 3, 3
                      Ответить
                      • Дык это надо помнить, сколько было элементов. Потом еще нули приписывать. Хуйня какая-то нетривиальная.
                        Ответить
                  • Но в любом случае, это же костыль усложняющий алгоритм. А если начать последовательность с двойки, то никакие костыли не нужны, всё будет работать автоматически. Не надо будет помнить, сколько там элементов было на входе. Факторизация сразу даёт ответ.

                    З.Ы. Отрицательные числа можно интерливнуть с положительными, если они нужны.
                    Ответить
              • Меня терзают подозрения, что прожорливость алгоритма будет зависеть от области значений элементов не меньше, чем от их количества. Чтобы сортировать байты, нам потребуется табличка из 256 простых чисел (если единицу к последовательности не добавляем, то 256-е число равно 1619). Чтобы сортировать ворды, нам потребуется табличка из 65536 простых чисел (простое число № 65536 равно 821641). А чтобы сортировать дворды, нам потребуется четыре миллиарда простых чисел (мне уже страшно представить, чему будет равно это самое четырёхмиллиардное с чем-то число).

                А ведь их ещё нужно перемножать, а потом результат раскладывать на множители...

                Про сортировку кувордов этим методом, вероятно, придётся забыть.
                Ответить
              • > можно даже перемножать через SSE для максимальной оптимизации
                > и потом осталось только факторизовать получившееся число
                Какая оптимизация )))
                Ответить
                • > Какая оптимизация )))

                  Как превратить простую задачу в NP полную.
                  Ответить
                  • Сначала как превратить элементарную сортировку O(N*log N) в пирдольный поиск медианы через O(N²).

                    Потом улучшение до экспоненты для NP-факторизации.
                    Ответить
    • void sort4(uint8_t a[static 4])
      {
        uint32_t index;
        memcpy(&index, a, sizeof(index));
        static const uint8_t reordering[UINT32_MAX] = 
        {
          // тут таблица поиска на 4294967296 элементов (4 Гб)
          // в каждом элементе которой описывается то, куда что переставлять.
          // т.е. если мы сортируем массив 4, 3, 2, 1
          // то мы интерпретируем эти байтики как uint32_t число
          // а потом берем из этого массива элемент с таким индексом
          // и в элементе там будет 8-битный байтик типа (3 << 0) | (2 << 2) | (1 << 4) | (0 << 6)
          // это будет означать, что четверный элемент будет первым
          // третий вторым, второй третьим, первый четвертым
        };
        const uint8_t out[4] =
        {
          a[ (reordering[index] >> 0) & 0b11 ],
          a[ (reordering[index] >> 2) & 0b11 ],
          a[ (reordering[index] >> 4) & 0b11 ],
          a[ (reordering[index] >> 6) & 0b11 ], 
        }; // надо делать это, учитывая всякую там endian питушню
        // можно через битфилды заебенить, но как-то похуй
      
        memcpy(a, out, sizeof(out));
      }


      Это говно конечно же будет сосать из-за промахов кэша, но если кэш сделать достаточно большим, проблем не будет
      Ответить
      • Таблицу поиска можно ужать в два раза (с 4 Гб до 2 Гб)
        static const uint8_t reordering[UINT32_MAX >> 1] = 
        {
          // blah-blah-blah
        }
        
        if ((index >> 31) == 1)
        {
          index = ~index;
          const uint8_t out[4] =
          {
            a[ (reordering[index] >> 6) & 0b11 ],
            a[ (reordering[index] >> 4) & 0b11 ],
            a[ (reordering[index] >> 2) & 0b11 ],
            a[ (reordering[index] >> 0) & 0b11 ], 
          };
          memcpy(a, out, sizeof(out));
        }
        else
        {
          const uint8_t out[4] =
          {
            a[ (reordering[index] >> 0) & 0b11 ],
            a[ (reordering[index] >> 2) & 0b11 ],
            a[ (reordering[index] >> 4) & 0b11 ],
            a[ (reordering[index] >> 6) & 0b11 ], 
          };
          memcpy(a, out, sizeof(out));
        }
        Ответить
    • Статья о «тьюринг-полноте» инструкции «mov» с косвенной адресацией вдохновила меня на размышления о программировании без if:
      https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

      А ведь тогда и оператор присвоения для элементов массива оказывается полным по какому-то пидарасу.

      Возьмём пример:
      a[i] = false;
      a[j] = true; // если j == i, то текущее значение a[i] затрётся true
      k = a[i];
      Теперь в переменной k лежит результат сравнения i == j.

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

      Более сложный пример:
      tmp = a[i];
      a[N] = false;
      a[i] = true; // текущее значение a[N] затрётся true, если i == N
      j = a[N]; // теперь в j лежит результат сравнения i с N
      a[i] = tmp; // восстанавливаем значение ни в чём не повинного элемента


      Ещё пример. Допустим k –— переменная, хранящая булево значение:
      a[N] = i;
      a[N+1] = j;
      m = a[N + k]; // теперь в m будет лежать i, если k==0, и j, если k==1

      Получили эквивалент тернарного оператора: m = k ? j : i;

      Перевести остальную часть статьи с ассемблера на произвольный императивный ЯП с оператором присвоения предлагается читателю.
      Ответить
      • Там используется свойство x86 mov, которое позволяет реализовать jmp.
        А именно обработчик SIGSEGV при page fault.

        > оператор присвоения для элементов массива оказывается полным по какому-то пидарасу.
        Спец. оператор присвоения такого не умеет. И не может имитировать бесконечный цикл/рекурсию.

        Так и сишный копроцессор мог быть полным по Аналу Тьюринга, если бы умел в бесконечную рекурсию.
        Ответить
    • Охуеть, два года прошло. А ведь почти как вчера было…
      Ответить
      • 2 года ago
        Охуеть, два года прошло. А ведь почти как вчера было…
        Ответить
        • Охуеть, два года прошло. А ведь почти как вчера было…
          Ответить
      • Охуеть, четыре года прошло. А ведь почти как вчера было...
        Ответить
    • Кстати, этот принцип "сравнивания между собой элементов массива и биты результата сравниваний куда-то запихивать и по нему что-то находить" - можно еще на этом построить функцию нахождения медианы. Т.е. делаем таблицу поиска, где хранится индекс с медианой для каждой возможной битушни от сравнений, и потом по этому индексу тупо возвращаем значение медианы.

      Кто-то уже такое реализовывал?
      Ответить
      • Это уже построение индекса к массиву данных получается, как в СУБД.
        Ответить
    • #bormand_govno
      Ответить
    • Охуеть, шесть лет прошло. А ведь почти как вчера было...
      Ответить
      • Охуеть, было, было, было, но прошло.
        О-о-о, о-о-о!

        День может разбиться, как стекло.
        Кто же не знает?
        Кто же не знает?
        Но чтобы всё время не везло,
        Так не бывает,
        Так не бывает.
        Ответить

    Добавить комментарий