19.08.2023 02:49
barbalion 38 15000 Источник

И это не пузырьковая, а нечто гораздо более тупое.

Как-то после обеда, стоя в коридоре с чашечкой кофе, мне пришла в голову мысль. Что ведь для того, чтобы убедиться, что массив отсортирован, надо сделать всего n-1 сравнение. Например, для массива длины 4 таких сравнения будет 3:

if (a0 < a1 < a2 < a3)

А получив утвердительный ответ на этот вопрос, мы можем сразу вернуть готовый массив:

if (a0 < a1 && a1 < a2 && a2 < a3) return [a0, a1, a2, a3];

Клево! Теперь чтобы превратить это в сортировку 4 чисел осталось просто проверить все остальные комбинации максимально тупым образом:

def sort4(a0, a1, a2, a3) {
  if (a0 < a1 && a1 < a2 && a2 < a3) return [a0, a1, a2, a3];
  if (a0 < a1 && a1 < a2 && a3 < a2) return [a0, a1, a3, a2];
  if (a0 < a2 && a2 < a1 && a1 < a3) return [a0, a2, a1, a3];
  ...
}
Именно так выглядит "максимальная тупость" по мнению Kandinsky 2.2
Именно так выглядит "максимальная тупость" по мнению Kandinsky 2.2
Оговорка

Строго говоря для того чтобы наша сортировка была стабильной, везде надо писать "<=" (меньше или равно), но меня задолбало это это набирать, так что я буду везде писать только "<". Упражнение по превращению этого удовольствия в продакшен-код я оставляю читателю.

Сколько таких комбинаций? Ну это легко. Их ровно 4! = 24. Мы только что придумали алгоритм с вычислительной сложностью O(n*n!). Это гораздо хуже пузырьковой сортировки (с его квадратичной асимптотикой) не только из-за ужасающе долгой работы, но и еще в добавок нам для массива каждой длины надо писать отдельную функцию. Жуть.

А факториал растет очень быстро, значит наши функции будут становиться все длиннее, отнимая не только вычисления, но и память - ее нам тоже потребуется O(n!). Не для хранения данных (мы же их даже никуда не сохраняем), а для самого алгоритма. Для всех "обычных" алгоритмов размер кода фиксирован, то есть O(1), и мы его просто игнорируем при оценке асимптотики по памяти. Для нашей "тупой" сортировки такое не прокатит.

Но давайте немного поразмышляем. Видим, что первые 3 случая повторяются в части нескольких первых сравнений. А что, если...

if a0 < a1:
	if a1 < a2:
		if a2 < a3:
			return [a0, a1, a2, a3]
		else:
			if a1 < a3:
				return [a0, a1, a3, a2]
			else:
              ...
		else:
          ...
....

Хм. Давайте снова посчитаем вычислительную сложность. Кажется мы тут все наши возможные комбинации каждым сравнением делим примерно на 2. То есть вычислительная сложность сразу получает себе суперспособность логарифм: O(log(n!)).

O(\log n!) = O\Big(\sum_n \log i\Big) \approx O(n\cdot \log n)

То есть, если мы все правильно поняли, то мы только что придумали алгоритм, который сортированные списки обрабатывает за O(n) (самая первая ветка срабатывает за n-1 сравнение), а остальные случаи мы сортируем не хуже теоретически идеального случая. То есть как Quicksort, только без его "худшего" случая, когда он деградирует до "пузырька".

кажется, вечер перестает быть томным.
кажется, вечер перестает быть томным.

Расчехляем питон и пишем туда наш генератор тупых сортировок. Для начала возьмем и напишем функцию генерации перестановок:

def permutations(a: list[int]) -> list[list[int]]:
    if len(a) == 1:
        return [a]
    return [
        [a[i]] + recur
        for i in range(len(a))
        for recur in permutations(a[0:i] + a[i + 1:])
    ]

Потом выкинем ее, вспомнив, что уже есть itertools.permutation() который делает ровно то же самое.

Теперь пишем 2 функции генерации строк:

def gen_comp(indent: int, l: int, r: int, s_then: str, s_else: str):
    ind = "\t" * indent
    return ind + f"if a{l} < a{r}:\n{s_then}\n{ind}else:\n{s_else}"


def gen_return(indent: int, indice: list[int]):
    return "\t" * indent + f"return [" + ", ".join([f"a{i}" for i in indice]) + "]"

Ну и саму функцию строящую дерево сравнений (осторожно, говнокод):

def gen_sort_n(cases: list[list[int]], known: list[tuple[int, int]], indent):
    c = cases[0]
    if len(cases) == 1:
        return gen_return(indent, c)

    lss, gtr = [], []
    for l, r in list(zip(c, c[1:])):
        if l == r or (l, r) in known or (r, l) in known:
            continue
        for c in cases:
            (lss, gtr)[c.index(l) > c.index(r)].append(c)  # Хитрый трюк с заполнением двух массивов за раз.
        s_then = gen_sort_n(lss, known + [(l, r)], indent + 1)
        s_else = gen_sort_n(gtr, known + [(r, l)], indent + 1)
        return gen_comp(indent, l, r, s_then, s_else)

print(gen_sort_n(list(itertools.permutations(range(4))), [],0))

Она просто берет первую перестановку из переданных и сравнивает первую непроверенную пару элементов в ней. Потом все оставшиеся случаи раскидывает по подветкам true и false рекурсивно. Получаем на выходе код:

Много кода
if a0 < a1:
	if a1 < a2:
		if a2 < a3:
			return [a0, a1, a2, a3]
		else:
			if a1 < a3:
				return [a0, a1, a3, a2]
			else:
				if a0 < a3:
					return [a0, a3, a1, a2]
				else:
					return [a3, a0, a1, a2]
	else:
		if a0 < a2:
			if a1 < a3:
				return [a0, a2, a1, a3]
			else:
				if a2 < a3:
					return [a0, a2, a3, a1]
				else:
					if a0 < a3:
						return [a0, a3, a2, a1]
					else:
						return [a3, a0, a2, a1]
		else:
			if a1 < a3:
				return [a2, a0, a1, a3]
			else:
				if a0 < a3:
					return [a2, a0, a3, a1]
				else:
					if a2 < a3:
						return [a2, a3, a0, a1]
					else:
						return [a3, a2, a0, a1]
else:
	if a0 < a2:
		if a2 < a3:
			return [a1, a0, a2, a3]
		else:
			if a0 < a3:
				return [a1, a0, a3, a2]
			else:
				if a1 < a3:
					return [a1, a3, a0, a2]
				else:
					return [a3, a1, a0, a2]
	else:
		if a1 < a2:
			if a0 < a3:
				return [a1, a2, a0, a3]
			else:
				if a2 < a3:
					return [a1, a2, a3, a0]
				else:
					if a1 < a3:
						return [a1, a3, a2, a0]
					else:
						return [a3, a1, a2, a0]
		else:
			if a0 < a3:
				return [a2, a1, a0, a3]
			else:
				if a1 < a3:
					return [a2, a1, a3, a0]
				else:
					if a2 < a3:
						return [a2, a3, a1, a0]
					else:
						return [a3, a2, a1, a0]

Выглядит вроде неплохо. А давайте посчитаем, какая средняя глубина вложенности if-ов при увеличении n. Для этого для каждого вызова gen_return запомним ident и просто посчитаем среднее. Код я тут опускаю, потому что он скучный, а терпение читателя не резиновое.

n

n!

Avg(indent)

2

2

1.000

3

6

2.667

4

24

4.917

5

120

7.717

6

720

11.050

7

5040

14.907

8

40320

19.282

Давайте посмотрим, как эти числа ложатся на теорию.

Что-то тут не так. Минимальная глубина, как и ожидалось, очень приятная = n-1, но вот оранжевая линия (средняя глубина) выше наших ожиданий. Мы же хотели O(n*logn), а тут явно что-то другое. Давайте внимательнее посмотрим на сгенеренный код. Некоторые перестановки (например return [a0, a3, a2, a1]) возвращаются только после 6 сравнений, тогда как теория предсказывает что их должно быть не больше 5 (столько сделает mergesort в худшем случае сортировки массива из 4 элеменов). Видно что это происходит из-за того что наши деревья сравнений не сбалансированы. То есть они не всегда делят количество вариантов пополам. Иногда пропорции оказываются гораздо хуже: 1 к 3 или даже 1 к 7. Так не пойдет. Давайте дерево балансировать.

Для этого переберем разные сравнения из доступных и выберем то, которое делит все случаи наилучшим образом (в пропорции 1:1).

Секретные материалы

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

Статистика улучшилась, но опять не дотягивает до "идеальной". Еще немного поразмыслив, понимаем, что выбор "лучшего" доступного сравнения на данном шаге может привести к тому что, оставшиеся после деления варианты уже невозможно поделить поровну внутри рекурсивных вызовов.

Давайте тогда перепишем код чтобы он перебрал вообще все возможные последовательности проверок и вернул самую сбалансированную. Надо сказать, что такой перебор ужасно тормозит так как сложность такой генерации растет как квадрат факториала. Ради науки мы потерпим. Но только до n=5.

N

depth

2

[1, 1]

3

[2, 3, 3, 2, 3, 3]

4

[4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5]

5

[7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7]

Ну вот, совсем другое дело. Теперь взглянем на сгенеренный код для n=4.

if a0 < a1:                              # Ага...
	if a1 < a2:                          # ага...
		if a1 < a3:                      # Штоа?!?
			if a2 < a3:                  # а! вот оно чо.
				return [a0, a1, a2, a3]
			else:
				return [a0, a1, a3, a2]
		else:
			if a0 < a3:
				return [a0, a3, a1, a2]
			else:
				return [a3, a0, a1, a2]
	else:
      ...

Хм. Наша красивая первая "перестановка" теперь вместо 3 сравнений содержит 4. Причем "лишнее" сравнение (третье по счету) выглядит как-то совсем ненатурально. Однако статистика не врет - этот способ проверки самый лучший для среднего случая.

Но для среднего случая уже есть сортировка слиянием. Она гарантирует всегда близкое к идеальному количество сравнений. Лучше него только алгоритм слиянием-вставками и его вариации. Все они с фиксированным размером кода. Так нафига козе баян?

Дальше хуже

Для n=5 таких "ненужных" сравнений (для тривильного случая упорядоченнго массива) уже 7-4=3:

if a0 < a1:
	if a2 < a3:
		if a0 < a2:
			if a2 < a4:
				if a3 < a4:
					if a1 < a3:
						if a1 < a2:
							return [a0, a1, a2, a3, a4]
						else:
							return [a0, a2, a1, a3, a4]
					else:
						if a1 < a4:
							return [a0, a2, a3, a1, a4]
						else:
							return [a0, a2, a3, a4, a1]
				else:
...

Но можно подобрать параметры для оптимизации чтобы снизить это количество до 2.

И вот тут кажется мы можем нащупать какую-то пользу из нашего эксперимента. Мы получили действую модель оптимизации алгоритма под исходные данные. Если мы что-то знаем про частотность перестановок в исходных данных, мы можем подогнать под них алгоритм сортировки и получить гарантированно самую быструю сортировку. Быстрее теоретических чисел сортировки.

"Погодите-погодите" - скажет кто-то наивный - "ведь мы по прежнему имеем ужасную асимптотику по памяти и надо писать отдельную функцию для каждого n". На что мы имеем возразить:

  1. Во первых очевидно, что его можно использовать только для небольших n. Вероятно не больше 7-8. После чего сгенеренный код начнет занимать уже непрактично много места. А если мы ограничиваем размер массива, то код становится конечным и наше использование памяти возвращается в приятное O(1).

  2. Для больших n мы можем "сверху" на него надстроить обычную сортировку слиянием. Тем самым сильно ускорив сортировку для наших данных, а не сферических в вакууме.

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

В качестве дальнейшей оптимизации нашего "супер-алгоритма" можно предложить:

  1. Вместо возврата массивов генерить готовые операции in-place обмена элементов массива самым оптимальным образом (сдвигая подмассивы, где возможно, вместо перемещения поштучно). Либо делая идеальные циклические перестановки с единственным слотом: temp = a0; a0 = a3; a3 = a2; a2 = temp для варианта [a3, a1, a0, a2]) и т.п.

  2. Избавлять от ветвлений с помощью трюков branchless programming, переходя на векторные инструкции. Это должно дополнительно ускорять в разы и десятки раз.

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

Комментарии (38)


  1. Zara6502
    19.08.2023 03:41
    #25872658
    +5

    Браво. Читал с удовольствием.

    но меня задолбало это это набирать

    Ну есть же замена в редакторе, это быстро.


  1. Zara6502
    19.08.2023 03:41
    #25872706
    +12

    И вот тут кажется мы можем нащупать какую-то пользу из нашего эксперимента. Мы получили действую модель оптимизации алгоритма под исходные данные. Если мы что-то знаем про частотность перестановок в исходных данных, мы можем подогнать под них алгоритм сортировки и получить гарантированно самую быструю сортировку. Быстрее теоретических чисел сортировки.

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

    Но эти же люди продолжают пользоваться архиваторами видимо забывая как именно устроены ключи степени сжатия в самой программе и почему контекст важен.


    1. Tasta_Blud
      19.08.2023 03:41
      #25873634
      +2

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

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

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


      1. BugM
        19.08.2023 03:41
        #25874954
        +1

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

        Нет же. Они гонят все в gzip или те что более продвинутые в zstd. И не парятся.


        1. Zara6502
          19.08.2023 03:41
          #25875434

          не совсем так. тут вопрос скорее бизнес модели. но крупные компании типа амазона или гугла заморачиваются по поводу контекстного сжатия.

          кстати PNG по сути как раз сжимает данные в зависимости от контекста, а вот насколько хорошо, то уже зависит от реализации, поэтому я обычно за paint.net и photoshop еще файлы дожимаю с помощью Pingo. У меня на сетевом диске есть библиотека PNG файлов для рисования всякого, размер около 4 Гб, я прогнал как-то ее через Pingo и уменьшил размер до 3.2Гб.


          1. BugM
            19.08.2023 03:41
            #25876084

            Подобрать более подходящий алгоритм под паттерн данных на стадии проектирования можно. И так делают иногда. Хотя как правило все равно просто берут gzip или zstd.

            Это все равно безмерно далеко от анализа текущего потока и подбора чего-то под него. Один раз спроектировали, написали и оно крутится годами.

            PS: Правильная настройка словаря для zstd дает больше чем практически все остальное (работающее со сравнимой скоростью) на почти любом паттерне данных.


            1. Zara6502
              19.08.2023 03:41
              #25876844

              настройка словаря - это и есть контекстная настройка, каким методом вы решили задачу не так важно. я вам писал ответ на ваши "берут gzip и не парятся", а вы тут же пишете что "настраивают словарь", то есть заморочились таки.


              1. BugM
                19.08.2023 03:41
                #25876976

                В подавляющем большинстве случаев берут гзип и не парятся. Оно того не стоит. В остальных случаях стоит подумать о чем-то вроде настройки словаря zstd.

                И это все равно не "сначала смотрят тип данных для упаковки, а потом выбирают стратегию упаковки именно исходя из полученного анализа".


                1. Zara6502
                  19.08.2023 03:41
                  #25878768

                  То что кто-то не слишком умный это понятно, но мы же не такие, а значит выбор стратегии имеет место быть. Ну и разговор идёт об обычных архиваторах, а не о бизнес-моделях, а там zip/7z/rar где Deflate совсем не единственный метод, скорее уж вы попадёте на LZMA.

                  Лично я для себя пользуюсь zpaq (m5) и 7zip(bzip2 или ppmd) и за 50 лет ни разу не пользовался ни gzip ни zstd.


      1. Zara6502
        19.08.2023 03:41
        #25875424

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

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

        zpaq
        zpaq


  1. vk6677
    19.08.2023 03:41
    #25872708
    +7

    Пример тупой сортировки (не стоит её повторять):

    #include

    #define N 10

    int main()
    {
    int vec[N] = {1, 7, 3, -7, -1, 7, 9, -2, 5, 8};
    for (auto i = 0; i < N - 1; ++i)
    if ((vec[i] > vec[i + 1])) {
    std::swap(vec[i], vec[i + 1]); i = -1;
    }
    for (auto i = 0; i < N; ++i) std::cout << vec[i] << "\t";
    return EXIT_SUCCESS;
    }


    1. Wan-Derer
      19.08.2023 03:41
      #25872720

      --


    1. haqreu
      19.08.2023 03:41
      #25874024
      +2

      Никак не пойму, зачем писать auto i =0? int и на один символ короче, и нагляднее...


  1. Chuvi
    19.08.2023 03:41
    #25872836
    +12

    https://ru.m.wikipedia.org/wiki/Bogosort


    1. NeoNN
      19.08.2023 03:41
      #25872876
      +1

      Согласен, это победитель)


      1. barbalion Автор
        19.08.2023 03:41
        #25873444

        По сложности он идентичен самому первую варианту в статье. Так что они тут делят первое место по тупости :)


    1. Dartess
      19.08.2023 03:41
      #25873070
      +1

      Ох, насколько же приятно выглядит мобильная википедия на десктопе!


      1. Chuvi
        19.08.2023 03:41
        #25873766

        Ой. Простите. Копипастил ссылку с телефона, забыл .m. убрать.

        Редактировать коммент уже не могу. Надеюсь это не проблема? Вот ссылка на не мобильную версию вики.

        https://ru.wikipedia.org/wiki/Bogosort


    1. TimKostenok
      19.08.2023 03:41
      #25874018

      https://ru.wikipedia.org/wiki/Лас-Вегас_(алгоритм) из этой серии)


    1. dyadyaSerezha
      19.08.2023 03:41
      #25874102

      Блин, как начал читать статью, тут же подумал об этом алгоритме, но оказалось, что его уже придумали (


    1. NooneAtAll3
      19.08.2023 03:41
      #25875780

      Я больше SlowSort предпочитаю


      никакого рандома
      экспоненциальная сложность


  1. Wan-Derer
    19.08.2023 03:41
    #25872848

    Моя номинация на самую тупую сортировку:

    Java
    import java.util.Arrays;

public class Test {

  public static void main(String[] args) {

    final int[] arr = {1, 7, 3, -7, -1, 7, 9, -2, 5, 8};
    final int[] sorted = naiveSort(arr);

    System.out.println(Arrays.toString(arr));
    System.out.println(testSorted(arr));
    System.out.println(Arrays.toString(sorted));
    System.out.println(testSorted(sorted));

  }

  private static int[] naiveSort(int[] arr) {

    final int[] sorted = new int[arr.length];
    final boolean[] checked = new boolean[arr.length];
    Arrays.fill(checked, false);

    for (int i = 0; i < arr.length; i++) {
      sorted[i] = findMin(arr, checked);
    }

    return sorted;
  }

  private static int findMin(int[] arr, boolean[] checked) {
    int min = Integer.MAX_VALUE;
    int minInd = 0;

    for (int i = 0; i < arr.length; i++) {
      if (!checked[i] && arr[i] <= min) {
        min = arr[i];
        minInd = i;
      }
    }

    checked[minInd] = true;
    return min;
  }

  private static String testSorted(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        return  "Array is not sorted";
      }
    }

    return "Array is sorted";
  }

}

    Хотя это скорее не тупая, а "наивная". Т.е. если бы я ничего не знал о программировании (ну, кроме синтаксиса), я бы написал именно так. Даже то что можно просто поменять местами два элемента - это какая-то иезуитская хитрость :) Я бы наверно сам не допёр, по крайней мере, не сразу.


    1. alexxisr
      19.08.2023 03:41
      #25872910
      +1

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

      Но это самый естественный способ сортировать, по-моему все кто еще не знает алгоритмы сортировки делают что-то наподобие этого.


      1. Wan-Derer
        19.08.2023 03:41
        #25872926

        это ж по сути сортировка выбором

        :)


    1. barbalion Автор
      19.08.2023 03:41
      #25873428
      +1

      Это сортировка выбором (selection sort). Добавить немного улучшений в часть findMin и сразу получите heapsort.


  1. Sergey1124
    19.08.2023 03:41
    #25873082
    +4

    У меня самый простой вариант:

        public void sort(List<Integer> list) {
        while (!isSorted(list)) {
            Collections.shuffle(list);
        }
    }

    private boolean isSorted(List<Integer> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1))
                return false;
        }

        return true;
    }


  1. JekaMas
    19.08.2023 03:41
    #25873172
    +2

    Отличный вариант! Но персонально останусь верен O(n) StalinSort https://github.com/gustavo-depaula/stalin-sort


    1. sci_nov
      19.08.2023 03:41
      #25874262

      А есть Stalin Encryption? ????


  1. redfox0
    19.08.2023 03:41
    #25873434
    +2

    Конечно, это юмористическая статья, но подобная сортировка оптимизированная под размер массива (4-9 элементов) существует в прод-коде. Если не изменяет память, разработчики гугла применили такое в одной из библиотек и увеличили скорость сортировки внутри sql-запросов до 30 %.

    Реализация libcxx обрабатывала несколько конкретных случаев особым образом. Коллекции длиной 5 или меньше сортировались при помощи специальных самописных сортировок на основе сравнений.
    https://habr.com/ru/articles/662181/


    1. barbalion Автор
      19.08.2023 03:41
      #25873436

      Вероятно вы правы. Не удивительно. Идея же лежит на поверхности.


      1. uszer
        19.08.2023 03:41
        #25882646

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


  1. gchebanov
    19.08.2023 03:41
    #25873484
    +2

    который я где-то пролюбил

    fixed. Вот среднее число сравнений если каждый раз выбирать индексы жадно (максимизируя min(len(lss), len(gtr)). Было бы хорошо если бы обновили график.

    ссылка на код

    [1.0, 2.6666666666666665, 4.666666666666667, 6.933333333333334, 9.577777777777778, 12.39047619047619, 15.406795634920634]

    более тупое

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

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


  1. Vitaly48
    19.08.2023 03:41
    #25873982
    +14

    Подержите моё пиво


    1. commanderxo
      19.08.2023 03:41
      #25874880
      +4

      Гениально! В то время как лучшие умы человечества пытаются превзойти n log n, этот код при сортировке отрицательных чисел должен выдать ответ ещё до вызова!


    1. alexxz
      19.08.2023 03:41
      #25879220

      Также известно как delay sort


  1. sci_nov
    19.08.2023 03:41
    #25874266

    Автор чем-то пьян. Пьян идеей ????


  1. Mad__Max
    19.08.2023 03:41
    #25874816
    +2

    О, когда весной изучал работу нового поколения псевдоразумных нейросетей архитектуры трансформера (GPT3 / GPT 4 и их многочисленные аналоги), в частности остановился на том, как они сортируют списки или занимаются простым счетом если задать им такую задачу в чистом виде или как часть более общей.
    В частности что они без проблем справляются с короткими списками, но начинают ошибаться и сильно тупить (даже если указывать им на ошибки и пытаться помочь/подсказать) если список становится длиннее (в зависимости от конкретной реализации и "размера" сети = количества ее "параметров"/весов, это происходит где-то в диапазоне от 7-10 элементов и до нескольких десятков)
    И пришел к выводу, что нейросети в процессе "тренировки" самостоятельно сформировали внутри себя очень специфические алгоритмы. Которые скорее всего представляют что-то очень похожее на описанное вами! Конкретно для случая сортировки.


    Вот тут про это немного писал в комментариях:
    https://habr.com/ru/companies/ods/articles/716918/comments/#comment_25509482
    https://habr.com/articles/729966/#comment_25509056 (тут 1й пример, где прошу нейросеть на базе GPT-4 отсортировать буквы по алфавиту)


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


    Из-за того, что такие нейросети класса "большая текстовая модель", в частности Трансформер имеют очень жесткие исходные(архитектурные) ограничения: они не рекуррентные (т.е. прямые циклы или даже их иналоги в их внутренних алгоритмах просто невозможны, но зато возможны множественные и очень сложные ветвления и проверки условий!), у них нет "рабочей памяти" для хранения переменных(память и слежение за контекстом разговора чат-ботов на основе таких сетей реализуется внешними алгоритмами, подающими часть истории разговора на вход нейросети заново при каждом следующем сообщении/запросе).


    То при достаточном уровне тренировки и размере сети (количестве параметров представляющих собой аналог объема кода) в ней рождаются вот такие вот "тупые" алгоритмы. В частности для сортировки и подсчета элементов. Не по принципу "тупости", а "жить захочешь, еще не так раскорячишься" (с).


    Вот представьте, что вы программируете, но у вас в распоряжении есть только один очень дурацкий язык программирования, в котором ВООБЩЕ отсутствуют циклы и нет доступа к оперативной памяти для хранения переменных(зато констант прямо в код нафигачить можно почти неограниченно) и даже встроенных базовых математический операций(сложение, умножение и т.д.) в языке нет. Но зато if… then… else и их аналоги (Case, Select и т.д.) можно фигачить в код тоже почти в неограниченных количествах.
    И вам вот с таким "инструментарием" нужно отсортировать массив, или сосчитать количество элементов в некотором множестве или выполнять математические операции и т.д.


    И вот тогда, подобные "тупые" алгоритмы, окажутся далеко неплохим вариантом, а вероятно одним из лучшим (из возможных в конкртеных ограниченных условиях). А вот это:


    А факториал растет очень быстро, значит наши функции будут становиться все длиннее, отнимая не только вычисления, но и память — ее нам тоже потребуется O(n!). Не для хранения данных (мы же их даже никуда не сохраняем), а для самого алгоритма.

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


  1. wataru
    19.08.2023 03:41
    #25880884

    Самая крутая сортировка — квантовая. Имея квантовый источник случайного шума, можно за O(n) получить случайную перестановку массива. Потом, опять же за O(n), можно, как верно заметил автор, проверить, а не отсортирован ли массив. Если нет, то надо, всего-лишь уничтожить вселенную. В результате (если принять многомировую интерпретацию квантовой физики) останется хотя бы одна вселенная, в которой массив отсортирован за O(n). Вот, мы и изобрели линейный алгоритм сортировки!