1. Pascal / Говнокод #26433

    0

    1. 1
    https://pastebin.com/ABfdEgS5

    Выкладываю не глядя мой код примерно 12-го года.

    Запостил: vistefan, 10 Февраля 2020

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

    • Фу, Стертор.
      Ответить
    • Нормальный школьный код
      Ответить
    • Кстати, как правильно писать алгоритм питузовки питузырьком?

      Я помню, что в школе писал его так же, ну и на будущее после школы запомню. Стабильно квадратичный питух.
      А вот в Википедии в качестве питузырька указан вариант, который питуроверяет массив на питузованность, из-за чего вовремя останавливается и выдаёт линейную питушню в некоторых случаях.
      Какой питузырёк правильный? На Википедии расширенный неканон, или в школе изучаем зауженный никанон?
      Ответить
      • ты имеешь вввиду, что питузпедия для питузейшего случая питузее?
        Ответить
      • >Какой питузырёк правильный?

        Рекурсивный, им. Хоара.
        Ответить
        • Какой стёб над worst-case квиксорта )))
          Ответить
          • Рекурсивный питузырёк - анскильная питушня
            * Может переполнить стек
            * В лучшем случае логарифм, когда у википитузырька - линия
            * По памяти питушня (линия же?), когда у википитузырька - константа
            * Худший случай - квадрат что там, что там
            Ответить
            • Допустим, есть массив [1,1,1,1,1,1,1,...,1]. Очевидно, что он уже отсортирован.
              Питузырёк с вики его отпитузырит за линию (теоретический пердел).
              Рекококорсивный питузырёк его отпитузырит за кваквадрат!
              Какой анскил )))
              Ответить
              • > Очевидно, что он уже отсортирован.
                А вот и не очевидно:
                >>> def is_sorted(arr):
                ...     try:
                ...             return all((x <= y for x, y in zip(arr, arr[1:])))
                ...     except:
                ...             return False
                ...
                >>> is_sorted([1,2,3])
                True
                >>> is_sorted([1,3,2])
                False
                >>> is_sorted([1,1,1,1,1,1,1,...,1])
                False

                Именно поэтому я за «Python».
                Ответить
                • > print(is.unsorted(c(1,2,3)))
                  [1] FALSE
                  
                  > print(is.unsorted(c(1,3,2)))
                  [1] TRUE
                  
                  > print(is.unsorted(c(1,1,1,1,1,1,1,...,1)))
                  Error in is.unsorted(c(1, 1, 1, 1, 1, 1, 1, ..., 1)) : 
                    '...' used in an incorrect context
                  Calls: print -> is.unsorted
                  Execution halted

                  Именно поэтому я за "R".
                  Ответить
                • >Именно поэтому я за «Python»

                  Там кстати Timsort, который ищет частично отсортированные куски.
                  Потому я тоже за «Python».
                  Ответить
                • А для пустой последовательности False чтоли будет?
                  Ответить
              • >Рекококорсивный питузырёк его отпитузырит за кваквадрат!
                Потому я за while(!sorted(array)) shuffle(array);
                Ответить
                • Великолепно. Лучший случай - тоже линейчатый питузок!
                  Ответить
                  • Причём у такой сортировки даже название есть, называется «Bogosort».
                    Ответить
                    • То есть царские алгоритмы.

                      >Bogosort
                      А это сортировка Бога.
                      Ответить
              • >его отпитузырит за линию (теоретический пердел)
                Тоже кстати неочевидно.
                Думаю предел O(1).
                Ответить
                • Теоретический предел для сортировки сравнениями — O(NlogN): https://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_нижней_оценке_ для_сортировки_сравнениями. Предел лучшего случая — O(N), поскольку нам в любом случае придётся доказывать, что массив отсортированный, а этого сделать быстрее, чем сравнением каждого элемента с предыдущим, нельзя.
                  Ответить
                  • Если к данным присобачить небольшое число фактов, ограниченное сверху некоторой константой, то можно ограниченное сверху этой же константой количество алгоритмов проверки ужать до O(1).

                    sorted([1,1,1,1,...,1]) - O(N)
                    sorted({data: [1,1,1,1,...,1], sorted: true}) - O(N)
                    Ответить
                    • По дефолту массив инициализируется нулями.

                      То есть он отсортирован.

                      То есть возможен O(1).
                      Ответить
                      • Так на инициализацию массива нужно O(N) присваиваний.
                        Ответить
                        • https://en.wikipedia.org/wiki/Bead_sort

                          Забавную дрянь нашёл. Многопоточную


                          O(1): The beads are all moved simultaneously in the same time unit, as would be the case with the simple physical example above. This is an abstract complexity, and cannot be implemented in practice.
                          
                          O( \sqrt {n}): In a realistic physical model that uses gravity, the time it takes to let the beads fall is proportional to the square root of the maximum height, which is proportional to n.
                          Ответить
                          • Круто, прямо квантовый алгоритм.
                            Ответить
                  • Именно поэтому я за сотировку подсчётом.
                    Ответить
                • Это наверно если алгоритму известно, что отсортированный?
                  Но в общем случае алгоритм не обладает такими знаниями, если только не использовать зожатые массивы, для которых повторяющиеся питухи будут сворачиваться.
                  Ответить
                  • Ну допустим в языке с немутабельными типами, том же хаскеле, добавить флаг в момент инициализации массива: asc, desc, unsorted.

                    А когда призываем sort проверить его, если asc то возвращаем исходный массив, если desc возвращаем ленивый список наоборот. Тогда best-case будет O(1).

                    Ещё вариант, если у нас параллельная вычислительная машина (какая-то квантовая питушня). Тогда тоже можно проверить за константое время отсортирован ли массив.
                    Ответить
                    • Тогда это уже будет не сортировка массива, а сортировка какой-то другой структуры данных (массив с флагами). А для квантовой питушни использовать классические O-оценки некорректно.
                      Ответить
                      • int array[N] = {0};
                        sort(array, N, sizeof(int));

                        Если компилятор крайне умён он вообще выкинет sort.
                        Ответить
                        • А сложность чего мы измеряем? Если он выкинет sort — то сложность этого куска программы будет O(N), а у sort() вообще никакой сложности не будет, поскольку не будет самого вызова.
                          Ответить
                          • >у sort() вообще никакой сложности не будет, поскольку не будет самого вызова
                            Сортировка за O(0)
                            Ответить
                            • Константы можно выкидывать: сортировка за O().
                              Ответить
                              • Выходит даже в мутабельных языках, если компилятор смог доказать, что отсортированный массив, путешествуя по коду не изменился до момента сортировки.

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

                                  Любые оптимизации любых компиляторов основываются на генерации эквивалентного кода. Компилятор считает две программы эквивалентными, если эквивалентно их наблюдаемое поведение (в терминах сишки и крестов — «observable behavior»).

                                  Таким образом, для задачи измерения временно́й сложности некой функции, количество выполняемых элементарных операций становится наблюдаемым поведением. Однако ни один оптимизирующий компилятор не вносит это количество в наблюдаемое поведение. Следовательно, для задачи измерения временно́й сложности функции любой оптимизирующий компилятор генерирует неэквивалентный код, а потому любые рассуждения о сложности исходных функций на основе анализа скомпилированного кода некорректны.
                                  Ответить
                                  • Поскольку никакой код (кроме кода на языках коммандных оболочек) не выполняется без компиляции, мы не можем говорить о сложности того или иного алгоритма. Во всяком случае, если мы не отключим оптимизации компилятора явно.
                                    Ответить
                                    • А ещё есть unskill-sort.
                                      Я когда-то использовал и такой алгоритм.

                                      ListBox1.Sorted = True

                                      Установка свойства это же O(1)
                                      Ответить
                                      • Это типа при каждом добавлении пересортировывать?
                                        Ответить
                                    • Не совсем так. Для максимально точной оценки сложности обычно конструируют формальную машину, задают для неё набор элементарных операций и конструкций, после чего формулируют исходный алгоритм в терминах этих операций. Ну а потом уже всё просто — для каждой коньструкции известно количество выполняемых операций, посыпаем всё этой щепоткой матана — получаем наши best-, average- и worst-case.

                                      Кстати, приведу реальный пример некорректности оценки сложности по скомпилированному коду. Возьмём такую питушню:
                                      unsigned add(unsigned a, unsigned b) {
                                          while (b != 0) {
                                              a++;
                                              b--;
                                          }
                                          return a;
                                      }

                                      Если мы сконпелируем её с «-O0» — мы получим функцию, которая выполняется за время O(b). Если возьмём хороший конпелятор и поставим «-O3» — получим функцию со сложность O(1): https://gcc.godbolt.org/z/3zpFqD.
                                      Но ведь это совершенно не значит, что наш питушарский алгоритм внезапно меняет сложность с линейной на константную! Он как жрал O(b), так и продолжает жрать O(b) элементарных операций языка «C».
                                      А конпелятор — молодец, конечно.
                                      Ответить
                                      • Круче всего он поступил в -O1
                                        Он допер, что надо a+b (rdi+rsi), но зачем-то всё равно сложил b в edx, и уменьшал беднягу, пока тот не стал равен нулю

                                        Зачем? 3ачем?
                                        Ответить
                    • тогда инициализация массива будет O(N), иначе как этот флаг посчитать?
                      Ответить
                      • Да. Но это же инициализация.
                        Её в любом случае придётся делать, согласно логике программы.
                        Ответить
            • >Рекококорсивный питузырёк его отпитузырит за кваквадрат!

              Шутка про quicksort очевидно не была понята.
              Но я квадрата там в упор не вижу. Будет N*logN
              Ответить
              • Где — там? В кваксорте?
                Ответить
                • Ага.

                  Он же идеально поровну разделит куски.

                  На [1,1,1,1,1,1,1,...,1] будет фактически best-case.
                  Ответить
                  • А, ты про [1,1,1,...]… У кваксортов worst-case'ы зависят от способа выбора опорного элемента. Если анскилльно брать первый/последний элемент, то для такого массива на каждом вызове будет отщипываться по одному элементу, и в результате организуется дерево вызовов с глубиной N, причём на каждом вызове там будет O(N) сравнений. В итоге и образуется квадратичная питушня.
                    А если брать центральный элемент в качестве опорного — тогда да, будет идеальный NlogN (а квадрат образуется для очень хитро сформированных массивов — таких, что на каждой итерации будет выбираться минимальный/максимальный элемент).
                    Ответить
                    • >квадрат образуется для очень хитро сформированных массивов — таких, что на каждой итерации будет выбираться минимальный/максимальный элемент

                      Да.

                      >стёб над worst-case квиксорта )))

                      Изначально всё было правильно понятно. Ну и с практической точки зрения лучший пузырёк, это именно quicksort.
                      Ответить
                  • Погодите, он же питушит по чему-то вида (<), (>=), либо по (<=), (>)? Или там другое деление?

                    Если питушить по (<), (>=) или по (<=), (>), какую из единиц в качестве пива ни возьми, он пропитушит все единицы в один бок от неё (линия) и пойдёт питушить массив единиц без одной (линия раз по убывающей линии), в результате чего получится треугольная сложность как раз как у питузырька.
                    Ответить
                    • Так оно пополам бьёт (start+end)/2

                      Я хотел сказать что зависит от реализации.
                      Кстати вот quicksort (с википедии!), который отсортирует [1,1,1,1,1,1,1,...,1] за O(N)
                      public static ArrayList<Integer> quicksort(ArrayList<Integer> numbers) {
                              if (numbers.size() <= 1)
                                  return numbers;
                              int pivot = numbers.size() / 2;
                              ArrayList<Integer> lesser = new ArrayList<Integer>();
                              ArrayList<Integer> greater = new ArrayList<Integer>();
                              int sameAsPivot = 0;
                              for (int number : numbers) {
                                  if (number > numbers.get(pivot))
                                      greater.add(number);
                                  else if (number < numbers.get(pivot))
                                      lesser.add(number);
                                  else
                                      sameAsPivot++;
                              }
                              lesser = quicksort(lesser);
                              for (int i = 0; i < sameAsPivot; i++)
                                  lesser.add(numbers.get(pivot));
                              greater = quicksort(greater);
                              ArrayList<Integer> sorted = new ArrayList<Integer>();
                              for (int number : lesser)
                                  sorted.add(number);
                              for (int number: greater)
                                  sorted.add(number);
                              return sorted;
                          }
                      Ответить
                      • Блядь, смотрю я на эти «new ArrayList<Integer>», «greater = quicksort», «greater.add» — и страшно становится… Оно ж наверняка какое-нибудь O(N^3) в реальности!
                        Ответить
                        • да, там будет динамически расти массив (копированием небось) и еще будет боксинг в int

                          и по памяти тоже будет пиздец, бо будет указатель на инт храница

                          именно потому я за int[]
                          Ответить
                          • > по памяти тоже будет пиздец, бо будет указатель на инт храница
                            Так там же просто за счёт наличия этих питушень происходит эта питушня. А можно было и внутри массива всё заменить.
                            Ответить
                        • Ну если не ресайзить их внутри, может не так плохо.

                          А оно будет их постоянно ресайзить ибо ArrayList<Integer>() по дефолту 10 элементов.

                          А вот насчёт автобоксинга в inta Integer, это фигня просто константа у O(N) будет больше. Это ж джава.
                          Ответить
                      • А, то есть (<), (=), (>). Викитушня всех переиграла. Великолепно.

                        > пополам бьёт (start+end)/2
                        Питушня какая-то. Это число адекватно только когда элемент с таким номером - медианный.
                        Ответить
                        • >Викитушня всех переиграла. Великолепно.
                          Не совсем.

                          [1,2,3,4,5,6...]
                          Царский пузырёк и сортировка Бога O(N), а qsort O(N*logN).
                          Ответить
                          • если ваш олгоритм хуево работает с уже сортированными массивами, то начинайте сортировку с шафла
                            Ответить
                          • Какой анскилл )))
                            И ещё по памяти жрёт дофига.

                            А если попробовать сэкономить память и применять питушню Хоара для инплейсного питушения, чтобы не плодить временные питушни для хранения подпитушень сортируемой питушни, то сложность возрастёт до квадрата!
                            Ответить
                            • А можете написать сортировку за O(N!) ?
                              Вообще какую самую хуевую сортировку можете написать?
                              Ответить
                              • Тред не читай.

                                https://govnokod.ru/26433#comment526688

                                Кстати это моя любимая сортировка, поскольку она одновременно и самая тормозная и самая быстрая.
                                Ответить
                                • спасибо, ты победил
                                  Ответить
                                • Следующий этап: сортировка за O(A(N, N)), где A — функция Аккермана.
                                  Ответить
                                  • Какой багор!!!

                                    Число A(4,4) настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.
                                    Ответить
        • У тебя и собака рекурсивная.
          Ответить
    • https://vk.com/zhena_pituza
      Ответить

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