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

    0

    1. 001
    2. 002
    3. 003
    4. 004
    5. 005
    6. 006
    7. 007
    8. 008
    9. 009
    10. 010
    11. 011
    12. 012
    13. 013
    14. 014
    15. 015
    16. 016
    17. 017
    18. 018
    19. 019
    20. 020
    21. 021
    22. 022
    23. 023
    24. 024
    25. 025
    26. 026
    27. 027
    28. 028
    29. 029
    30. 030
    31. 031
    32. 032
    33. 033
    34. 034
    35. 035
    36. 036
    37. 037
    38. 038
    39. 039
    40. 040
    41. 041
    42. 042
    43. 043
    44. 044
    45. 045
    46. 046
    47. 047
    48. 048
    49. 049
    50. 050
    51. 051
    52. 052
    53. 053
    54. 054
    55. 055
    56. 056
    57. 057
    58. 058
    59. 059
    60. 060
    61. 061
    62. 062
    63. 063
    64. 064
    65. 065
    66. 066
    67. 067
    68. 068
    69. 069
    70. 070
    71. 071
    72. 072
    73. 073
    74. 074
    75. 075
    76. 076
    77. 077
    78. 078
    79. 079
    80. 080
    81. 081
    82. 082
    83. 083
    84. 084
    85. 085
    86. 086
    87. 087
    88. 088
    89. 089
    90. 090
    91. 091
    92. 092
    93. 093
    94. 094
    95. 095
    96. 096
    97. 097
    98. 098
    99. 099
    100. 100
    #include <stdio.h>
    #include <stdlib.h>
    #include <inttypes.h>
    #include <stdbool.h>
    
    struct two_val
    {
      const int32_t a[2];
    };
    
    struct two_val_and_status
    {
      const bool is_swap;
      const struct two_val t_v;
    };
    
    struct array
    {
      const int32_t a[10];
    };
    
    struct array_and_status
    {
      const bool is_swap;
      const size_t pos;
      const struct array arr;
    };
    
    // Эта суперфункцональная функция сортировки двух элементов не просто сортирует два элемента
    // но и еще сообщает о том, нужно ли было для этого обменивать два значения
    struct two_val_and_status sort2(const struct two_val a)
    {
      return (a.a[0] > a.a[1]) ? (struct two_val_and_status){true, {{a.a[1], a.a[0]}}} : (struct two_val_and_status){false, a};
    }
    
    struct two_val read_two_val(const struct array arr, const size_t pos)
    {
      return (struct two_val){{arr.a[pos], arr.a[pos+1]}};
    }
    
    struct array store_val(const struct array arr, const int32_t val, size_t pos)
    {
      return (struct array) // Царский анролл
      {{
        pos != 0 ? arr.a[0] : val,
        pos != 1 ? arr.a[1] : val,
        pos != 2 ? arr.a[2] : val,
        pos != 3 ? arr.a[3] : val,
        pos != 4 ? arr.a[4] : val,
        pos != 5 ? arr.a[5] : val,
        pos != 6 ? arr.a[6] : val,
        pos != 7 ? arr.a[7] : val,
        pos != 8 ? arr.a[8] : val,
        pos != 9 ? arr.a[9] : val
      }};
    }
    
    struct array store_two_val(const struct array arr, const struct two_val val, const size_t pos)
    {
      return store_val(store_val(arr,val.a[0],pos),val.a[1],pos+1);
    }
    
    // суперохуительная рекурсивная функция сортировки пузырьком
    struct array_and_status bubble_sort_rec(struct array_and_status state) 
    {
      if (state.pos == 9)
      {
        if (state.is_swap == false) // Ура! Сортировка пузырьком завершена!
        {
          return state;
        }
        else
        { // а иначе нам надо по-новой сортировать!
          return bubble_sort_rec((struct array_and_status){.is_swap = false, .pos=0, .arr = state.arr});
        }
      }
      else
      {
        const struct two_val_and_status tmp = sort2(read_two_val(state.arr, state.pos));
        return bubble_sort_rec(
          (struct array_and_status)
          {
            .is_swap = tmp.is_swap || state.is_swap,
            .pos=state.pos+1,
            .arr = store_two_val(state.arr, tmp.t_v, state.pos)
          }
        );
      }
    }
    
    int main(void)
    {
      const struct array_and_status a = {.is_swap = false, .pos = 0, .arr = {{8,2,4,1,3,5,7,0,6,9}} };
      const struct array_and_status a_sort = bubble_sort_rec(a);
      for(size_t i = 0; i < 10; i++) // ох уж это убогое императивное программирование!!!
      {
        printf("%" PRIu32 ", ", a_sort.arr.a[i]);
      }
      return EXIT_SUCCESS;
    }

    Функциональная сортировка пузырьком
    https://wandbox.org/permlink/dGyvo82lgQGInD0Y

    Запостил: j123123, 19 Декабря 2021

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

    • Можно переписать на хаскель еще
      Ответить
      • ... или переписать на Coq и формально доказать
        Ответить
        • Ну как, переписал?
          Ответить
        • > формально доказать

          Мне почему-то кажется, что пузырёк самый сложный в этом плане. Очень неочевидный алгоритм.
          Ответить
          • > Очень неочевидный алгоритм
            Достаточно доказать, что после одного прохода один элемент гарантированно встанет на своё место и что при применении его на массив с одним элементом он будет отсортирован.
            Дальше — индукция.
            Ответить
            • Кстати, очень здравая идея. Максимум в массиве вроде же всегда всплывает за один проход?
              Ответить
              • Всплывает то, куда идёшь. Если сортируешь по возрастанию и идёшь с начала в конец — всплывёт максимум, если из конца в начало — минимум.
                Ответить
                • Чтоб не всплывало, надо к камню привязать.
                  Ответить
                • Можно сделать бустрофедон: на нечётных шагах идти вправо, на чётных — влево. Тогда за два первых шага найдём максимум и минимум.
                  Ответить
              • На этом факте основана оптимизация метода пузырька: на каждом шаге можно подрезать правую границу, пока не останется единственный элемент, который сортировать не нужно.
                Ответить
                • Молодец, сэкономил байт в 2021.
                  Ответить
                • Кстати, на Википедии в качестве пузырька вовсе презентуют не квадрат, а прямоугольник. В разделе реализации вовсе показывают только трапецию.

                  > или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны
                  >
                  ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1
                    F=0
                    ЦИКЛ ДЛЯ I=0 ДО N-1-J ШАГ 1
                      ЕСЛИ A[i] > A[I+1] ТО ОБМЕН A[i],A[I+1]:F=1
                    СЛЕДУЮЩЕЕ I
                    ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА
                  СЛЕДУЮЩЕЕ J


                  ttps://ru.wikipedia.org/wiki/Сортировка_пузырьком
                  Ответить
                  • Переменное количество итераций снижает криптобезопасность, делает возможной тайм-атаку, поэтому я говорил о квадрате и треугольнике.
                    Ответить
                  • Вообще мне понравилась трапеция. Сразу две меры сокращения количества сравнений:

                    1. Отрезаем уже отсортированный хвост.
                    2. Если массив уже отсортирован полностью, досрочно выходим.

                    Удобно для частично отсортированных массивов.
                    Ответить
                    • Надо трапецию с петушейкером, чтобы быстро обрабатывать почти отсортированные массивы.
                      Ответить
          • Обычное формальное доказательство опубликовала Полина: https://govnokod.ru/27435#comment629624 .

            Или ты про конкретное доказательство на «Coq»?
            Ответить
            • > на coq

              Угу. Тут ещё рекурсия неопределённой длины. Придётся пруфать,что она остановится за N проходов.
              Ответить
              • > Придётся пруфать,что она остановится за N проходов.
                Лучше применить well-founded recursion [1]. В качестве well-founded relation взять количество неупорядоченных элементов, например.

                [1] http://adam.chlipala.net/cpdt/html/Cpdt.GeneralRec.html
                Ответить
            • Надо для начала дать ма-те-ма-тическое определение, что такое "сортировка". И записать это определение на Coq. Ну типа сортировка это когда у нас функция, которая на вход принимает "массив" (надо дать определение слову "массив") и на выходе "массив", и над элементами "массива" определена бинарная операция "<=" которая возвращает "true" или "false", и для любых произвольных элементов массива справедливо, что если "(a <= b) && (b < c)" то тогда "a <= c", и что вот сортировка это такая "перестановка" (надо дать определения слову "перестановка"), при которой для элемента массива по индексу n и для элемента массива по индексу n+x где x больше или равно 1 справедливо, что "arr[n] <= arr[n+x]"... как-то так
              Ответить
              • Такое уже было на хабре.
                Ответить
              • >надо дать определения слову "перестановка"

                А то, если забыть, можно будет просто забить выходной массив нулями и сказать "я отсортироваль"
                Ответить
              • Всё придумали до нас:
                https://coq.inria.fr/library/Coq.Sorting.Sorted.html
                https://coq.inria.fr/library/Coq.Sorting.Permutation.html
                Ответить
          • Самый сложный — bogosort. Он может вообще никогда не сойтись.
            Ответить
            • Я за sleepsort: для него время можно определить точно, а не асимптотически. Отличное свойство для real-time систем.
              Ответить
            • >sort
              хуёрт
              Ответить
            • > Самый сложный — bogosort. Он может вообще никогда не сойтись.

              На дешманских питух-машинах возможно.

              А на царской машине с оракулом сортировка Бога гарантировано отрабатывает за O(n).

              Царской машине — царский алгоритм. Питухи пишут целые томы про сортировку, дрочат на O(log N *N).

              А пацаны решают задачу за O(N) простым однострочником
              while (!sorted(array)) shuffle (array);
              Ответить
              • Intelligent Design Sort лучше. Он отрабатывает за O(0), потому что у тебя массив уже в нужном порядке. Ты можешь этого не понимать, но пути господни неисповедимы, и это тот самый порядок, который приведёт тебя к просветлению.
                Ответить
                • Есть супрематический кубик Рубика, у которого все грани одного цвета. Он всегда собран.
                  Ответить
                  • А ещё есть 1х1х1 как базис индукции.
                    Ответить
                  • По аналологии представил компьютер, в котором существует один вид сигнала.
                    Ответить
                • > отрабатывает за O(0)
                  > потому что у тебя массив уже в нужном порядке

                  Кстати я уже размышлял на эту тему
                  https://govnokod.ru/26433#comment526710

                  * Если компилятор смог доказать, что ранее отсортированный массив, во время исполнения не изменился до момента сортировки. Он будет отсортирован за O(0).
                  * Bead sort
                  Ответить
    • Си -- функциональный язык. В нём есть функции.
      Ответить
    • // суперохуительная рекурсивная функция сортировки пузырьком
      struct array_and_status bubble_sort_rec(struct array_and_status state) 
      {
        return
        (state.pos == 9) ?
        (
          (state.is_swap == false) ? 
            state // Ура! Сортировка пузырьком завершена!
            :
            bubble_sort_rec((struct array_and_status){.is_swap = false, .pos=0, .arr = state.arr}) // а иначе нам надо по-новой сортировать!
        )
        :
        bubble_sort_rec
        (
          (struct array_and_status)
          {
            .is_swap = sort2(read_two_val(state.arr, state.pos)).is_swap || state.is_swap,
            .pos=state.pos+1,
            .arr = store_two_val(state.arr, sort2(read_two_val(state.arr, state.pos)).t_v, state.pos)
          }
        );
      }


      Избавился от вонючих императивных ифов, оставив лишь чисто функциональные тернарники

      https://wandbox.org/permlink/BUon7nyVppRUvXYz
      Ответить
      • Фу, императивщина.

        Напиши функцию реализующую ветвление.
        Ответить
        • Массив.
          Ответить
          • Фу, императивщина.

            Напиши функцию, реализующую массив.
            Ответить
            • > функцию, реализующую массив

              Кстати, попадалась недавно работа, где чуваки массив (не список) на лямбда-исчислении пилили.
              Ответить
            • А как в Си реализовать такую функцию?
              https://web.archive.org/web/20170705090734/http://smt2012.loria.fr/paper1.pdf

              Вот тут например описывается на 98 стр. такая функциональная хуй-ня

              read : array × index → element
              write : array × index × element → array

              Т.е. функция чтения должна принимать константный массив по значению и индекс, возвращая при этом значение по индексу:
              element_t read_arr(const array_t arr, const index_t i)
              {
                ...
              }


              а функция записи в массив принимает на вход массив, индекс и записываемое значение, возвращает новый массив с записанной хуйней:

              array_t write_arr(const array_t arr, const index_t i, const element_t elm)
              {
                ...
              }


              Притом массивы тут бесконечные, функции никаких ошибок не возвращают и никаких побочных эффектов не имеют. И как по-вашему это реализуется в Си? Очевидно, что никак, и даже во всяких там хаскелях это на самом-то деле никак не реализуется т.к. память у ЭВМ конечна. ФП это наёбка.
              Ответить
              • Если передавать размер массива или передавать массив по указателю (чтобы латать его на месте без копирования) или если «массив» не является plain old data, а читается как файл (т. е. может вернуть EOF), то можно даже состряпать что-то работающее.

                Увы, «бесконечный» массив без ленивости и без генераторов не поддержать.
                Ответить
                • можно как-то так реализовать

                  #include <stdio.h>
                  #include <stdlib.h>
                  #include <inttypes.h>
                  
                  typedef struct array_node
                  {
                    struct array_node *prev;
                    size_t i;
                    uint32_t elm;
                  } array_node;
                  
                  // Добавляем транзакцию в односвязный список
                  array_node *write_arr(array_node *arr, const size_t i, const uint32_t elm)
                  {
                    array_node *n = malloc(sizeof(array_node));
                    if (n == NULL) exit(EXIT_FAILURE);
                    *n = (array_node){arr, i, elm};
                    return n;
                  }
                  
                  // Пролистываем односвязный список до первого совпадения или пока не дойдем до NULL
                  uint32_t read_arr(array_node *arr, const size_t i)
                  {
                    if (arr == NULL) return 0;
                    if (arr->i == i) return arr->elm;
                    return read_arr(arr->prev, i);
                  }
                  
                  int main(void)
                  {
                    array_node *a = NULL; // NULL тут считается бесконечным массивом, заполненным нулями
                    a = write_arr(NULL, 0, 5);
                    a = write_arr(a, 1, 10);
                    a = write_arr(a, 2, 100500);
                    a = write_arr(a, 2, 20);  // элемент по адресу 2 был какбы перезаписан
                    a = write_arr(a, 3, 40);
                    printf("%" PRIu32 "\n", read_arr(a, 2)); // выведет 20
                    return EXIT_SUCCESS;
                  }


                  Но это конечно недостаточно функционально.
                  Можно еще сделать фукнцию, которая ищет в таком связном списке "перезаписывание" и удаляет лишнее
                  Ответить
                  • И вообще, посмотрите как тут экономится память! Вот если надо сделать дубликат обычного массива с одним измененным элементом, в обычных анскильных массивах вы потратите столько же памяти, сколько занимал оригинальный массив, а тут можно всего лишь хранить "diff".
                    Ответить
                    • А последний элемент можно просто изменять и получать новые массивы
                      Ответить
                      • Классическая функцианальная мапа.
                        Ответить
                        • А если сюда добавить контрольных сумм(добавленная транзакция содержит контрольную сумму от предыдущей и от того, что добавили), получится блокчейн
                          Ответить
                          • можно еще делать форки/бранчи как в моем любимом ZFS, например. Или как в GIT
                            Ответить
                  • Получение n-го элемента за O(n) )))

                    Вместо нула нужно сделать undefined, получится жопаскрипт
                    Ответить
                    • За O(m), которое зависит от количества вставок/удалений, а не от размера "массива"...
                      Ответить
                  • > перезаписан
                    Течёт ручей, бежит ручей...
                    Ответить
              • У «бесконечных» массивов в императивных языках возникает проблема: все элементы должны быть определены до очередной «точки следования», затрагивающей их. Заранее, до «точки следования» мы не можем знать, сколько элементов нам понадобится.
                Ответить
        • Можно посчитать обе ветки параллельно, а потом замультиплексить перед следующим тактом... А ну да, тут же про обычное программирование.
          Ответить
          • А можно посчитать параллельно с условием?
            Ответить
            • Можно посчитать параллельно, а потом результаты сложить с весами. Просто у каких-то ветвей вес нулевым окажется.
              Ответить
            • Вай нот?
              Ответить
          • Только вот одна из таких веток у тебя будет считаться бесконечно.
            Ответить
            • Почему? У тебя тут код в подхвостовую рекурсию оформлен и вполне готов к разбиению на такты.

              Или я какой-то из вызовов не вижу?
              Ответить
              • Ну вот например в функции ты вычислишь ветку с bubble_sort_rec(), но чтоб ее вычислить, нужно вычислить внутри тоже ветку с bubble_sort_rec(), т.е. вычислить это не выйдет, стек порвется.
                struct array_and_status bubble_sort_rec(struct array_and_status state) 
                {
                  const struct array_and_status arr[4] =
                  {
                    // (state.pos == 9) is true
                    // (state.is_swap == false) is true
                    [0b11] = state,// Ура! Сортировка пузырьком завершена!
                    
                    // (state.pos == 9) is true
                    // (state.is_swap == false) is false
                    // вот тут багор будет
                    [0b01] = bubble_sort_rec((struct array_and_status){.is_swap = false, .pos=0, .arr = state.arr}), // а иначе нам надо по-новой сортировать!
                    
                    [0b00] = (struct array_and_status)
                      {
                        .is_swap = sort2(read_two_val(state.arr, state.pos)).is_swap || state.is_swap,
                        .pos=state.pos+1,
                        .arr = store_two_val(state.arr, sort2(read_two_val(state.arr, state.pos)).t_v, state.pos)
                      },
                    [0b10] = (struct array_and_status)
                      {
                        .is_swap = sort2(read_two_val(state.arr, state.pos)).is_swap || state.is_swap,
                        .pos=state.pos+1,
                        .arr = store_two_val(state.arr, sort2(read_two_val(state.arr, state.pos)).t_v, state.pos)
                      }
                  };
                  return arr[(state.pos == 9) | ((state.is_swap == false) << 1)];
                }
                Ответить
                • > нужно вычислить внутри тоже ветку с bubble_sort_rec

                  А это уже на следующем такте.

                  > стек порвётся

                  Ну хвостовая рекурсия же, зачем тут стек? У тебя функция или останавливается и возвращает стейт или готовит новый стейт и идёт на следующий такт.
                  Ответить
                  • > Ну хвостовая рекурсия же, зачем тут стек?

                    Компилятор этого может не понять
                    Ответить
                  • Кстати, не хочешь сортировку пузырьком на циклоняше написать?
                    Ответить
                    • За O(n) по времени и O(n) по кристаллу?

                      З.Ы. Или я гоню и нельзя каждый слой сортировки параллелить внутри: 01 23 45, потом 0 12 34 5, потом 01 23 45?
                      Ответить
                      • А что-нибудь промежуточное можно?
                        Ответить
                        • Это как?
                          Ответить
                          • Частично наанроллить, частично зациклить.
                            Ответить
                            • Вообще, ПЛИСина конечно хуево подходит под пузырек, битонная сортировка намного лучше, и работает известно какое количество тактов.
                              Ответить
                              • Х.з., возможно пузырёк бОльшими блоками (по 4-8 элементов сразу, к примеру), чтобы скрыть задержки памяти?

                                Но не проебутся ли нужные пузырьку свойства от такой модификации?
                                Ответить
                                • Хотя после сортировки блоков логичнее уже merge sort на потоках из DRAM гонять, наверное, а не с пузырьком пердолиться?
                                  Ответить
                • Можно кстати массив из указателей на функции сделать, которым передавать state
                  Ответить

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