- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 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));
}
Follow us!
https://en.cppreference.com/w/cpp/language/integer_literal
http://govnokod.ru/20309 еще есть
> … а потом удивляешься, почему не компилируется.
Это ещё хорошо, что не компилируется. Вот если бы было 0о, то в каком-нибудь шрифте ты был бы твёрдо уверен, что пишешь десятичные нули, и всё бы компилировалось. И лови потом баги.
Уже и так есть long с l на конце, который путают с единицей.
Спасибо, я кончел.
https://ideone.com/3xysnu
Кстати, форт-система очень просто реализуется - всё уже спроектировано, нужно только реализовать, и состоит она из множества небольших определений - удобно тестировать. Я когда ещё на 2-м курсе учился, после пары месяцев изучения асма уже мог её реализовать (.COM, 3.5 Кб, набор слов не полный, и не всё по стандарту, но уже вполне можно было расширять форт из самого форта)
А что это за нотация? Я такого никогда не видел.
Я вообще за то, чтобы было так:
int a = 100_8;
int b = AFF_16;
double c = 1010101.01010_2;
И чтобы основание системы счисления могло быть более-менее любым (например, покуда хватает латинского алфавита). Компилятору всё равно это несложно преобразовать.
Verilog. <количество бит>'<основание><число>. Там иногда нужны числа с кривой разрядностью, к примеру 5 или 9 бит. Поэтому такой странный синтаксис.
Но всё равно он мне не нравится.
https://ideone.com/1RvRS7
Попробуй лучше на крестах сделать в компилтайме через говношаблоны и кококонстэкпры нахождение самой короткой (какую-нибудь из самых коротких) строки, в которой будут все возможные кобенации для N разных элементов. Вот например для массива из трех элементов будет 6! кобенаций
И вот такая зожатая короткая строка, в которой все эти кобенации есть:
А теперь попробуй на кококонстэкспрах и говношаблонах сделать обобщенный генератор сортировок для произвольной длинны моссива с зожатыми кобенациями всех массивов в один массив
https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery
Референс для желающих.
https://en.wikipedia.org/wiki/Superpermutation
> 4chan
> anime
Вот к чему ваше онимэ и борды приводят.
Пока ты свое аниме сортируешь в оптимальном порядке, успешные программисты повращали матрицы на хакирране и работают в гугле. Должность - Senior Matrix Rotator
Senior TENSOR Rotator!
Но получается нечестно: вместо хитрой генерации индекса в суперпермутации, который даст отсортированный массив я выбираю нужную пермутацию перебором.
Так же есть сопутствующая проблема: на определенном размере(больше 4) длина суперпермутации становится длиннее количества всех пермутаций. Так, для 4 длина суперпермутации 33(30 возможных вариантов), а количество пермутаций - 24.
Если кто-то может придумать как генерировать правила для нахождения индекса - подскажите.
https://ideone.com/OTt0wH
https://ideone.com/sy4XWH
Описание массива b занимает почти две тысячи символов, так что придётся публиковать отдельным комментарием.
Ну почему в сишке нет типа uint1820_t?
К слову, там этот алгоритм не выглядит настолько бесполезным, как его сишная версия.
Можно подключить GMP, но тогда весь пирфоманс потеряется:
К слову: https://en.wikipedia.org/wiki/512-bit
Можно отказаться от сдвигов и хранить константу в неупакованном виде, как в первом комментарии j123123:
http://govnokod.ru/24496#comment421387
Тогда она займёт 154 байта, что всего лишь в ≈ 2,7 раза больше упакованной.
AVX-512 позволяет использовать 512-битный регистр только как массив 32-битных или 64-битных чисел. 512-битных целых питухов у него нет, так что 460-битную константу за один раз не сдвинешь даже на таком процессоре.
Можно сдвинуть вправо на 0..31 бита чтобы получить low половинки и влево на 31..0 бита чтобы получить high половинки. Затем грубый сдвиг с 32-битным шагом через shuffle. И совместить половинки через or.
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
Теперь кокомпутер сайентисты говнококода ломают голову над тем, скоколько поебени на крестошаблонах и кококонстэкспрах нужно, чтобы это сделать в кокомпилтайме на крестоговне.
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 производится единственный раз, его можно представить ассоциативным массивом (потеряв некоторое время на поиск индекса). Тогда к гигабайту мы подберёмся при попытке отсортировать двенадцать элементов.
В общем, для большого количества элементов в чистом виде этот алгоритм может представлять лишь академический интерес.
Определение массива b из функции sort7 стираем.
В самом начале функции main добавляем:
Больше ничего не менял.
Теперь экзешник весит жалких полмегабайта вместо четырёх с половиной.
Кстати, существует вменяемый способ инициализации такой карты, чтобы не писать 100500 операторов присваивания?
У меня нехорошие предчувствия по поводу пирфоманса...
https://ru.wikipedia.org/wiki/Точка_Фейнмана
А вдруг нас обманывают и на самом деле число Пи рационально: 761-я цифра равна 5, а дальше идут нули? Шесть девяток подряд в плавающем питухе выглядят подозрительно.
Ещё чуть-чуть, и если Вы скажете "А я на самом деле пользователь _____", то ГК запомнит _____ как файку Новогоднего петуха.
Экзешник полегчал: вместо 100500 вызовов перегруженных операторов [] и = теперь только массив пар и один вызов кокококонструктора. Итого теперь около 370 килобайт.
Сортирует 8 элементов, брат жив. Экзешник весит 700 килобайт. С тупым сишным массивом он бы весил гигабайт.
Или это приведёт к нарушению пирфоманса из-за лишних ветвлений?
Нет ли хотя бы битовых хаков для восстановления результатов сравнений элементов из имеющихся O(NlogN) битов?
При N=8 «инновационный алгоритм» требует 8*7/2 = 28 сравнений, но слой один. Классическая битонная сеть требует 24 сравнения, но у неё 6 слоёв. Если на первом этапе использовать два параллельно работающих «инновационных алгоритма» для сравнения 4 элементов, то количество слоёв можно сократить до 4 (первые три слоя утопчутся в один).
1. Воспользоваться ленивостью операторов || и &&.
2. Возвращать указатели функции (тут будут некоторые расходы на передачу управления).
Осталось дело за «малым»: придумать алгоритм.
Пусть
Тогда:
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].
1. Реализовали бы генерацию суперпермутации для произвольного количества элементов.
2. Функция принимала бы на вход массив элементов произвольного типа (например, через крестошаблоны или генерики какого-нибудь языка). В идеале функция должна сортировать массив структур по ключу (ключ выделяет коллбек-функция, либо это сделано через перегрузку оператора сравнения).
3. Суперпермутация занимала бы меньше места. У меня модифицированный алгоритм: вместо представления суперпермутации как массива целых я использовал зожатие в битовое поле и сдвиг для выделения нужной пермутации. По этой причине используются не все элементы суперпермутации. Гипотетически её можно перепаковать, убрав неиспользуемые биты.
4. Массив b занимал бы меньше места. Однако, боюсь, что если его зожму, то потеряю пирфоманс. Вопрос об оптимальном представлении этого массива остаётся открытым.
5. Было бы больше примеров на других ЯП.
Нетто — это сколько элементов реально используются программой.
Выводы:
1. Реализовывать сортировку в таком виде для n > 6 практически бессмысленно. Придётся либо тратить гигабайты оперативки, либо хранить b как ассоциативный массив (но в последнем случае придётся тратить такты на поиск). Также b можно заменить функцией, но открыт вопрос об её эффективной реализации (не тупым же свитч-кейсом её делать).
2. При n > 4 зожатие суперпермутации в битовое поле вряд ли приведёт к заметной экономии памяти (для n=5 и n=8 это зожатие приводит к увеличению размера элемента массива b).
А существуют ли интересные алгоритмы, использующие внутри себя сортировку массива из трёх или из четырёх элементов?
Посмотрел вот это:
https://ru.wikipedia.org/wiki/Сеть_сортировки
https://ru.wikipedia.org/wiki/Битонная_сортировка
На начальных этапах битонной сортировки можно использовать.
Какой битон )))
У рассматриваемого в этом треде кода есть интересное преимущество - все сравнения можно сделать параллельно и дальше только мультиплексоры. А у сортирующих сетей сравнения обычно в каждом слое.
З.Ы. Кстати, можно же через SSE попробовать - составить маску для shuffle...
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 раза больше. Зато вместо десяти слоёв будет один.
Тогда модифицированная битонная для 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
https://ideone.com/Ayyl09
Я не случайно так отформатировал код: сортировки на каждой строчке можно выполнять параллельно.
P.S. Ideone выдаёт error 502 вместо кода, потому что он длинный (720 перестановок чисел), но сам код при этом работает. Хотя 20 килобайт кода — не так много. Они его там алгоритмом Шлемиля раскрашивают что ли?
https://ideone.com/9I7048
https://ideone.com/mQGhHY
Даже Царь был против таких функций. Он считал, что нужно использовать обычные арифметические операции, а конпелятор должен уметь это оптимизировать за тебя. Для этого он пытался подобрать такой код, который гэцэцэшечке (а других вменяемых конпеляторов по мнению Царя не существует) было легче оптимизировать.
P.S. Я накосячил в последних строчках: там _mm_shuffle_epi8, а не _mm_shuffle_epi32, как мне показалось.
В общем, 12 сравнений вместо шести, зато AssParallel.
В общем, тема для холивара.
> Для этого он пытался подобрать такой код, который гэцэцэшечке (а других вменяемых конпеляторов по мнению Царя не существует) было легче оптимизировать.
Именно поэтому я за «Царя».
Зароллим ещё раз:
Нигде не ошибся?
Дано: {1, 2, 2, 3}
Единица ноль раз больше кого-нибудь => ставим её на место №0.
Двойка один раз больше единицы => ставим её на место №1.
Тройка три раза больше других элементов => ставим её на место №3.
Место №2 остаётся вакантным.
Кто видел как в AVX-512 регистрах шаффлят зигзаг после DCT и квантования, того такой фигнёй не испугать.
Самый ёбнутый зигзаг вроде в форматах с интерлейсингом?
А ещё мне нравится, что «concrete» с английского переводится как «цемент».
О, я как раз искал шаффлы.
В принципе уже можно и на AVX-2 хуйнуть. Чтобы по 256 бит.
https://ideone.com/cgnvBp
А так?
Вот так работает.
А вот битовых массивов в сишке, кажется, нет.
«Наступление науки год от года подвергает испытанию нашу веру и, как кажется, предвещает начало периода, когда улучшения должны закончиться.»
https://ideone.com/MLwwdw
И вот если надо отсортировать массив {6, 5, 12} то берем и перемножаем
(можно даже перемножать через SSE для максимальной оптимизации)
и потом осталось только факторизовать получившееся число. Можно сделать моссив из всех возможных вореций перемножения трех чисел из моссива primes и там двоичным поиском находить ответ за логарифмическое время - оптимизированно.
З.Ы. Отрицательные числа можно интерливнуть с положительными, если они нужны.
А ведь их ещё нужно перемножать, а потом результат раскладывать на множители...
Про сортировку кувордов этим методом, вероятно, придётся забыть.
> и потом осталось только факторизовать получившееся число
Какая оптимизация )))
Как превратить простую задачу в NP полную.
Потом улучшение до экспоненты для NP-факторизации.
Это говно конечно же будет сосать из-за промахов кэша, но если кэш сделать достаточно большим, проблем не будет
https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
А ведь тогда и оператор присвоения для элементов массива оказывается полным по какому-то пидарасу.
Возьмём пример: Теперь в переменной k лежит результат сравнения i == j.
Вместо чистых массивов можно даже использовать крестоблядский класс std::map, чтобы не тратить лишнюю память.
Более сложный пример:
Ещё пример. Допустим k –— переменная, хранящая булево значение:
Получили эквивалент тернарного оператора: m = k ? j : i;
Перевести остальную часть статьи с ассемблера на произвольный императивный ЯП с оператором присвоения предлагается читателю.
А именно обработчик SIGSEGV при page fault.
> оператор присвоения для элементов массива оказывается полным по какому-то пидарасу.
Спец. оператор присвоения такого не умеет. И не может имитировать бесконечный цикл/рекурсию.
Так и сишный копроцессор мог быть полным по Аналу Тьюринга, если бы умел в бесконечную рекурсию.
Охуеть, два года прошло. А ведь почти как вчера было…
Кто-то уже такое реализовывал?