- 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));
}
j123123 15.07.2018 09:59 # +1
HoBorogHuu_nemyx 07.01.2019 13:56 # 0
gost 07.01.2019 14:24 # +1
HoBorogHuu_nemyx 08.01.2019 06:39 # +1
guest6 05.07.2024 23:55 # 0
guest8 15.07.2018 11:30 # −999
j123123 15.07.2018 11:45 # +1
https://en.cppreference.com/w/cpp/language/integer_literal
3.14159265 01.08.2022 04:40 # 0
guest8 15.07.2018 11:31 # −999
j123123 15.07.2018 11:49 # 0
http://govnokod.ru/20309 еще есть
guest8 15.07.2018 12:39 # −999
vistefan 15.07.2018 14:49 # +1
> … а потом удивляешься, почему не компилируется.
Это ещё хорошо, что не компилируется. Вот если бы было 0о, то в каком-нибудь шрифте ты был бы твёрдо уверен, что пишешь десятичные нули, и всё бы компилировалось. И лови потом баги.
Уже и так есть long с l на конце, который путают с единицей.
guest8 15.07.2018 14:59 # −999
j123123 15.07.2018 15:58 # +1
guest8 15.07.2018 16:03 # −999
j123123 15.07.2018 16:04 # +1
bormand 15.07.2018 15:38 # 0
guest8 15.07.2018 16:18 # −999
666_N33D135 15.07.2018 17:47 # +1
Спасибо, я кончел.
666_N33D135 15.07.2018 18:00 # 0
https://ideone.com/3xysnu
666_N33D135 15.07.2018 18:59 # 0
guest8 15.07.2018 19:06 # −999
666_N33D135 15.07.2018 19:23 # 0
guest8 15.07.2018 19:35 # −999
kamanalnadzor 15.07.2018 20:38 # 0
666_N33D135 15.07.2018 21:12 # 0
Кстати, форт-система очень просто реализуется - всё уже спроектировано, нужно только реализовать, и состоит она из множества небольших определений - удобно тестировать. Я когда ещё на 2-м курсе учился, после пары месяцев изучения асма уже мог её реализовать (.COM, 3.5 Кб, набор слов не полный, и не всё по стандарту, но уже вполне можно было расширять форт из самого форта)
666_N33D135 15.07.2018 19:33 # 0
vistefan 15.07.2018 22:57 # +1
А что это за нотация? Я такого никогда не видел.
Я вообще за то, чтобы было так:
int a = 100_8;
int b = AFF_16;
double c = 1010101.01010_2;
И чтобы основание системы счисления могло быть более-менее любым (например, покуда хватает латинского алфавита). Компилятору всё равно это несложно преобразовать.
bormand 16.07.2018 00:03 # +1
Verilog. <количество бит>'<основание><число>. Там иногда нужны числа с кривой разрядностью, к примеру 5 или 9 бит. Поэтому такой странный синтаксис.
j123123 01.01.2019 18:09 # 0
bormand 01.01.2019 18:10 # +1
j123123 01.01.2019 18:11 # +1
guest8 16.07.2018 00:31 # −999
guest8 16.07.2018 00:35 # −999
guest8 15.07.2018 11:32 # −999
HoBorogHuu_nemyx 01.01.2019 16:45 # 0
HoBorogHuu_nemyx 01.01.2019 17:46 # +1
Но всё равно он мне не нравится.
gost 01.01.2019 19:27 # +1
https://ideone.com/1RvRS7
j123123 05.01.2019 12:48 # +2
Попробуй лучше на крестах сделать в компилтайме через говношаблоны и кококонстэкпры нахождение самой короткой (какую-нибудь из самых коротких) строки, в которой будут все возможные кобенации для N разных элементов. Вот например для массива из трех элементов будет 6! кобенаций
И вот такая зожатая короткая строка, в которой все эти кобенации есть:
А теперь попробуй на кококонстэкспрах и говношаблонах сделать обобщенный генератор сортировок для произвольной длинны моссива с зожатыми кобенациями всех массивов в один массив
bootcamp_dropout 05.01.2019 14:26 # 0
https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery
Референс для желающих.
j123123 05.01.2019 19:57 # 0
https://en.wikipedia.org/wiki/Superpermutation
bootcamp_dropout 05.01.2019 19:58 # 0
HoBorogHuu_nemyx 06.01.2019 01:35 # 0
j123123 08.01.2019 08:09 # +3
> 4chan
> anime
Вот к чему ваше онимэ и борды приводят.
Пока ты свое аниме сортируешь в оптимальном порядке, успешные программисты повращали матрицы на хакирране и работают в гугле. Должность - Senior Matrix Rotator
roman-kashitsyn 08.01.2019 10:46 # +1
Senior TENSOR Rotator!
bootcamp_dropout 05.01.2019 21:26 # +3
Но получается нечестно: вместо хитрой генерации индекса в суперпермутации, который даст отсортированный массив я выбираю нужную пермутацию перебором.
Так же есть сопутствующая проблема: на определенном размере(больше 4) длина суперпермутации становится длиннее количества всех пермутаций. Так, для 4 длина суперпермутации 33(30 возможных вариантов), а количество пермутаций - 24.
Если кто-то может придумать как генерировать правила для нахождения индекса - подскажите.
HoBorogHuu_nemyx 07.01.2019 03:18 # +1
https://ideone.com/OTt0wH
HoBorogHuu_nemyx 07.01.2019 09:06 # +1
https://ideone.com/sy4XWH
HoBorogHuu_nemyx 07.01.2019 11:06 # +5
Описание массива b занимает почти две тысячи символов, так что придётся публиковать отдельным комментарием.
Ну почему в сишке нет типа uint1820_t?
bormand 07.01.2019 11:11 # +2
HoBorogHuu_nemyx 07.01.2019 11:13 # +4
bormand 07.01.2019 11:21 # +3
К слову, там этот алгоритм не выглядит настолько бесполезным, как его сишная версия.
HoBorogHuu_nemyx 07.01.2019 11:36 # +2
Можно подключить GMP, но тогда весь пирфоманс потеряется:
К слову: https://en.wikipedia.org/wiki/512-bit
Можно отказаться от сдвигов и хранить константу в неупакованном виде, как в первом комментарии j123123:
http://govnokod.ru/24496#comment421387
Тогда она займёт 154 байта, что всего лишь в ≈ 2,7 раза больше упакованной.
HoBorogHuu_nemyx 08.01.2019 10:57 # 0
AVX-512 позволяет использовать 512-битный регистр только как массив 32-битных или 64-битных чисел. 512-битных целых питухов у него нет, так что 460-битную константу за один раз не сдвинешь даже на таком процессоре.
bormand 08.01.2019 11:02 # +2
Можно сдвинуть вправо на 0..31 бита чтобы получить low половинки и влево на 31..0 бита чтобы получить high половинки. Затем грубый сдвиг с 32-битным шагом через shuffle. И совместить половинки через or.
bormand 08.01.2019 11:06 # +2
HoBorogHuu_nemyx 08.01.2019 11:45 # 0
HoBorogHuu_nemyx 07.01.2019 12:26 # +1
https://ideone.com/Co824j
HoBorogHuu_nemyx 07.01.2019 15:05 # +4
https://ideone.com/L4ImJg
gpyrou_nemyx 07.01.2019 15:11 # +1
HoBorogHuu_nemyx 07.01.2019 16:05 # +3
На самом деле я написал генератор генераторов генераторов констант.
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.
HoBorogHuu_nemyx 07.01.2019 16:24 # +2
https://github.com/tigertv/superpermutation
j123123 07.01.2019 19:26 # +1
j123123 07.01.2019 19:26 # +3
Теперь кокомпутер сайентисты говнококода ломают голову над тем, скоколько поебени на крестошаблонах и кококонстэкспрах нужно, чтобы это сделать в кокомпилтайме на крестоговне.
1024-- 07.01.2019 19:43 # 0
bootcamp_dropout 07.01.2019 19:45 # +1
HoBorogHuu_nemyx 08.01.2019 06:46 # +1
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.
HoBorogHuu_nemyx 08.01.2019 12:21 # +3
1. Лёгкий песец: O(n²) –— это количество сравнений.
2. Песец средней тяжести: O(n!) –— это минимальный размер таблицы возможных перестановок.
3. Песец чуть-чуть потяжелее: сумма прогрессии, состоящей из факториалов –— это длина суперпермутации.
4. Полный песец: O(2 в степени n²) –— это сколько на самом деле занимает таблица перестановок (включая неиспользуемые элементы), потому что у нас она представлена разреженным массивом.
Именно из-за последнего таблица перестановок для сортировки семи элементов будет весить 4 мегабайта, а для сортировки восьми элементов –— почти гигабайт.
Учитывая, что обращение к массиву b производится единственный раз, его можно представить ассоциативным массивом (потеряв некоторое время на поиск индекса). Тогда к гигабайту мы подберёмся при попытке отсортировать двенадцать элементов.
В общем, для большого количества элементов в чистом виде этот алгоритм может представлять лишь академический интерес.
HoBorogHuu_nemyx 09.01.2019 14:06 # +1
HoBorogHuu_nemyx 09.01.2019 14:16 # +2
HoBorogHuu_nemyx 09.01.2019 14:52 # 0
Определение массива b из функции sort7 стираем.
В самом начале функции main добавляем:
Больше ничего не менял.
Теперь экзешник весит жалких полмегабайта вместо четырёх с половиной.
Кстати, существует вменяемый способ инициализации такой карты, чтобы не писать 100500 операторов присваивания?
HoBorogHuu_nemyx 09.01.2019 15:19 # 0
bormand 09.01.2019 15:32 # +2
HoBorogHuu_nemyx 09.01.2019 15:52 # +2
У меня нехорошие предчувствия по поводу пирфоманса...
HoBorogHuu_nemyx 09.01.2019 16:08 # +1
HoBorogHuu_nemyx 09.01.2019 16:38 # +2
https://ru.wikipedia.org/wiki/Точка_Фейнмана
А вдруг нас обманывают и на самом деле число Пи рационально: 761-я цифра равна 5, а дальше идут нули? Шесть девяток подряд в плавающем питухе выглядят подозрительно.
1024-- 09.01.2019 18:32 # +1
Ещё чуть-чуть, и если Вы скажете "А я на самом деле пользователь _____", то ГК запомнит _____ как файку Новогоднего петуха.
1024-- 09.01.2019 18:30 # +1
HoBorogHuu_nemyx 09.01.2019 20:48 # 0
Экзешник полегчал: вместо 100500 вызовов перегруженных операторов [] и = теперь только массив пар и один вызов кокококонструктора. Итого теперь около 370 килобайт.
HoBorogHuu_nemyx 10.01.2019 01:53 # 0
Сортирует 8 элементов, брат жив. Экзешник весит 700 килобайт. С тупым сишным массивом он бы весил гигабайт.
1024-- 10.01.2019 02:29 # 0
Или это приведёт к нарушению пирфоманса из-за лишних ветвлений?
Нет ли хотя бы битовых хаков для восстановления результатов сравнений элементов из имеющихся O(NlogN) битов?
1024-- 10.01.2019 02:38 # +1
HoBorogHuu_nemyx 10.01.2019 03:31 # +1
При N=8 «инновационный алгоритм» требует 8*7/2 = 28 сравнений, но слой один. Классическая битонная сеть требует 24 сравнения, но у неё 6 слоёв. Если на первом этапе использовать два параллельно работающих «инновационных алгоритма» для сравнения 4 элементов, то количество слоёв можно сократить до 4 (первые три слоя утопчутся в один).
HoBorogHuu_nemyx 10.01.2019 02:50 # 0
HoBorogHuu_nemyx 10.01.2019 02:55 # 0
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].
HoBorogHuu_nemyx 10.01.2019 03:21 # 0
CHayT 07.01.2019 20:30 # +2
HoBorogHuu_nemyx 08.01.2019 06:36 # 0
1. Реализовали бы генерацию суперпермутации для произвольного количества элементов.
2. Функция принимала бы на вход массив элементов произвольного типа (например, через крестошаблоны или генерики какого-нибудь языка). В идеале функция должна сортировать массив структур по ключу (ключ выделяет коллбек-функция, либо это сделано через перегрузку оператора сравнения).
3. Суперпермутация занимала бы меньше места. У меня модифицированный алгоритм: вместо представления суперпермутации как массива целых я использовал зожатие в битовое поле и сдвиг для выделения нужной пермутации. По этой причине используются не все элементы суперпермутации. Гипотетически её можно перепаковать, убрав неиспользуемые биты.
4. Массив b занимал бы меньше места. Однако, боюсь, что если его зожму, то потеряю пирфоманс. Вопрос об оптимальном представлении этого массива остаётся открытым.
5. Было бы больше примеров на других ЯП.
HoBorogHuu_nemyx 08.01.2019 07:26 # 0
HoBorogHuu_nemyx 08.01.2019 08:17 # +1
HoBorogHuu_nemyx 08.01.2019 08:18 # +1
HoBorogHuu_nemyx 08.01.2019 08:18 # 0
Нетто — это сколько элементов реально используются программой.
Выводы:
1. Реализовывать сортировку в таком виде для n > 6 практически бессмысленно. Придётся либо тратить гигабайты оперативки, либо хранить b как ассоциативный массив (но в последнем случае придётся тратить такты на поиск). Также b можно заменить функцией, но открыт вопрос об её эффективной реализации (не тупым же свитч-кейсом её делать).
2. При n > 4 зожатие суперпермутации в битовое поле вряд ли приведёт к заметной экономии памяти (для n=5 и n=8 это зожатие приводит к увеличению размера элемента массива b).
HoBorogHuu_nemyx 08.01.2019 08:44 # +1
bormand 08.01.2019 09:22 # 0
HoBorogHuu_nemyx 08.01.2019 09:36 # 0
А существуют ли интересные алгоритмы, использующие внутри себя сортировку массива из трёх или из четырёх элементов?
j123123 08.01.2019 09:38 # +1
HoBorogHuu_nemyx 08.01.2019 10:08 # 0
Посмотрел вот это:
https://ru.wikipedia.org/wiki/Сеть_сортировки
https://ru.wikipedia.org/wiki/Битонная_сортировка
На начальных этапах битонной сортировки можно использовать.
bormand 08.01.2019 10:41 # +3
Какой битон )))
У рассматриваемого в этом треде кода есть интересное преимущество - все сравнения можно сделать параллельно и дальше только мультиплексоры. А у сортирующих сетей сравнения обычно в каждом слое.
З.Ы. Кстати, можно же через SSE попробовать - составить маску для shuffle...
HoBorogHuu_nemyx 08.01.2019 11:08 # 0
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
У битонной параллелится всё, что на схеме внутри коричневых и розовых блоков.
>> Какой битон )))
У меня было желание написа́ть «битонная сартерофка». Ну чтобы было уж совсем ниграматна.
bormand 08.01.2019 11:23 # +2
Ну я поэтому и писал про слои. В каждом слое компаратор. Каждый слой "ждёт" пока стабилизируются предыдущие. А компараторы медленные по сравнению с мультиплексорами (причём чем больше бит - тем медленнее).
В битонной сети для 16 элементов получается 10 слоёв по 8 компараторов. По схеме из данного треда получится 120 компараторов, всего в 1.5 раза больше. Зато вместо десяти слоёв будет один.
HoBorogHuu_nemyx 08.01.2019 11:38 # +2
Тогда модифицированная битонная для 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
HoBorogHuu_nemyx 08.01.2019 15:53 # +1
https://ideone.com/Ayyl09
Я не случайно так отформатировал код: сортировки на каждой строчке можно выполнять параллельно.
P.S. Ideone выдаёт error 502 вместо кода, потому что он длинный (720 перестановок чисел), но сам код при этом работает. Хотя 20 килобайт кода — не так много. Они его там алгоритмом Шлемиля раскрашивают что ли?
HoBorogHuu_nemyx 08.01.2019 16:11 # 0
https://ideone.com/9I7048
HoBorogHuu_nemyx 08.01.2019 16:24 # 0
https://ideone.com/mQGhHY
bormand 08.01.2019 12:50 # +3
bormand 08.01.2019 12:58 # +1
HoBorogHuu_nemyx 08.01.2019 13:18 # +2
Даже Царь был против таких функций. Он считал, что нужно использовать обычные арифметические операции, а конпелятор должен уметь это оптимизировать за тебя. Для этого он пытался подобрать такой код, который гэцэцэшечке (а других вменяемых конпеляторов по мнению Царя не существует) было легче оптимизировать.
P.S. Я накосячил в последних строчках: там _mm_shuffle_epi8, а не _mm_shuffle_epi32, как мне показалось.
HoBorogHuu_nemyx 08.01.2019 13:25 # +1
В общем, 12 сравнений вместо шести, зато AssParallel.
HoBorogHuu_nemyx 08.01.2019 13:33 # 0
bormand 08.01.2019 13:36 # 0
HoBorogHuu_nemyx 08.01.2019 17:48 # 0
HoBorogHuu_nemyx 09.01.2019 23:52 # 0
bormand 10.01.2019 00:22 # 0
HoBorogHuu_nemyx 10.01.2019 00:30 # 0
В общем, тема для холивара.
bormand 10.01.2019 00:30 # 0
3.14159265 01.08.2022 06:28 # 0
> Для этого он пытался подобрать такой код, который гэцэцэшечке (а других вменяемых конпеляторов по мнению Царя не существует) было легче оптимизировать.
Именно поэтому я за «Царя».
HoBorogHuu_nemyx 08.01.2019 13:42 # +1
Зароллим ещё раз:
Нигде не ошибся?
bormand 08.01.2019 13:46 # 0
HoBorogHuu_nemyx 08.01.2019 13:51 # 0
Дано: {1, 2, 2, 3}
Единица ноль раз больше кого-нибудь => ставим её на место №0.
Двойка один раз больше единицы => ставим её на место №1.
Тройка три раза больше других элементов => ставим её на место №3.
Место №2 остаётся вакантным.
bormand 08.01.2019 13:58 # +1
HoBorogHuu_nemyx 08.01.2019 14:00 # 0
bormand 08.01.2019 14:02 # 0
HoBorogHuu_nemyx 08.01.2019 14:03 # 0
bormand 08.01.2019 14:35 # +1
bormand 08.01.2019 14:50 # +2
HoBorogHuu_nemyx 08.01.2019 14:53 # +3
hormand 01.08.2022 11:58 # 0
HoBorogHuu_nemyx 08.01.2019 14:07 # +3
3.14159265 01.08.2022 01:10 # 0
Кто видел как в AVX-512 регистрах шаффлят зигзаг после DCT и квантования, того такой фигнёй не испугать.
bormand 01.08.2022 11:47 # 0
Самый ёбнутый зигзаг вроде в форматах с интерлейсингом?
bormand 08.01.2019 17:50 # +4
HoBorogHuu_nemyx 08.01.2019 18:33 # 0
bormand 08.01.2019 18:34 # +1
HoBorogHuu_nemyx 09.01.2019 09:42 # +1
А ещё мне нравится, что «concrete» с английского переводится как «цемент».
3.14159265 01.08.2022 01:09 # 0
О, я как раз искал шаффлы.
В принципе уже можно и на AVX-2 хуйнуть. Чтобы по 256 бит.
HoBorogHuu_nemyx 08.01.2019 09:32 # 0
https://ideone.com/cgnvBp
j123123 10.01.2019 05:32 # +1
j123123 10.01.2019 05:44 # 0
bormand 10.01.2019 07:41 # +1
HoBorogHuu_nemyx 10.01.2019 10:08 # +1
А так?
HoBorogHuu_nemyx 10.01.2019 10:11 # 0
HoBorogHuu_nemyx 10.01.2019 10:35 # +1
HoBorogHuu_nemyx 10.01.2019 10:41 # +1
Вот так работает.
HoBorogHuu_nemyx 10.01.2019 10:48 # 0
А вот битовых массивов в сишке, кажется, нет.
HoBorogHuu_nemyx 10.01.2019 13:55 # 0
HoBorogHuu_nemyx 10.01.2019 15:36 # 0
bormand 10.01.2019 16:18 # 0
bormand 10.01.2019 21:38 # +1
Goh 11.01.2019 00:21 # 0
guest8 11.01.2019 01:41 # −999
HoBorogHuu_nemyx 11.01.2019 10:40 # 0
«Наступление науки год от года подвергает испытанию нашу веру и, как кажется, предвещает начало периода, когда улучшения должны закончиться.»
guest8 11.01.2019 19:57 # −999
HoBorogHuu_nemyx 10.01.2019 16:18 # +1
https://ideone.com/MLwwdw
HoBorogHuu_nemyx 10.01.2019 17:02 # 0
bormand 10.01.2019 18:09 # +1
HoBorogHuu_nemyx 10.01.2019 19:08 # +3
bormand 11.01.2019 09:38 # 0
guest6 05.07.2024 23:55 # 0
bormand 10.01.2019 08:12 # 0
bormand 10.01.2019 09:44 # 0
j123123 11.01.2019 19:53 # +1
guest8 11.01.2019 19:53 # −999
gpyrou_nemyx 11.01.2019 20:14 # 0
j123123 11.01.2019 20:34 # +3
И вот если надо отсортировать массив {6, 5, 12} то берем и перемножаем
(можно даже перемножать через SSE для максимальной оптимизации)
и потом осталось только факторизовать получившееся число. Можно сделать моссив из всех возможных вореций перемножения трех чисел из моссива primes и там двоичным поиском находить ответ за логарифмическое время - оптимизированно.
guest8 11.01.2019 21:04 # −999
gpyrou_nemyx 11.01.2019 21:24 # 0
guest8 11.01.2019 21:54 # −999
guest8 11.01.2019 21:04 # −999
guest8 25.07.2020 00:27 # −999
bormand 11.01.2019 22:10 # 0
j123123 12.01.2019 00:09 # 0
bormand 12.01.2019 00:12 # 0
HoBorogHuu_nemyx 12.01.2019 00:14 # 0
bormand 12.01.2019 00:14 # 0
j123123 12.01.2019 00:17 # 0
bormand 12.01.2019 00:19 # 0
bormand 12.01.2019 00:17 # 0
З.Ы. Отрицательные числа можно интерливнуть с положительными, если они нужны.
HoBorogHuu_nemyx 12.01.2019 18:03 # 0
А ведь их ещё нужно перемножать, а потом результат раскладывать на множители...
Про сортировку кувордов этим методом, вероятно, придётся забыть.
gost 25.07.2020 00:30 # +1
> и потом осталось только факторизовать получившееся число
Какая оптимизация )))
bormand 25.07.2020 01:11 # +2
Как превратить простую задачу в NP полную.
3.14159265 01.08.2022 02:00 # 0
Потом улучшение до экспоненты для NP-факторизации.
j123123 13.01.2019 05:05 # +1
Это говно конечно же будет сосать из-за промахов кэша, но если кэш сделать достаточно большим, проблем не будет
j123123 13.01.2019 05:20 # 0
Kakou-mo_nemyx 14.02.2019 21:19 # +2
https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
А ведь тогда и оператор присвоения для элементов массива оказывается полным по какому-то пидарасу.
Возьмём пример: Теперь в переменной k лежит результат сравнения i == j.
Вместо чистых массивов можно даже использовать крестоблядский класс std::map, чтобы не тратить лишнюю память.
Более сложный пример:
Ещё пример. Допустим k –— переменная, хранящая булево значение:
Получили эквивалент тернарного оператора: m = k ? j : i;
Перевести остальную часть статьи с ассемблера на произвольный императивный ЯП с оператором присвоения предлагается читателю.
3.14159265 31.07.2022 23:10 # 0
А именно обработчик SIGSEGV при page fault.
> оператор присвоения для элементов массива оказывается полным по какому-то пидарасу.
Спец. оператор присвоения такого не умеет. И не может имитировать бесконечный цикл/рекурсию.
Так и сишный копроцессор мог быть полным по Аналу Тьюринга, если бы умел в бесконечную рекурсию.
gost 25.07.2020 00:24 # 0
guest6 31.07.2022 21:51 # +1
Охуеть, два года прошло. А ведь почти как вчера было…
npopa6 05.07.2024 23:47 # +1
guest6 05.07.2024 23:56 # +1
j123123 31.07.2022 21:47 # +1
Кто-то уже такое реализовывал?
bormand 31.07.2022 21:49 # 0
j123123 31.07.2022 22:55 # 0
Jlou_6JlblKAHAX 31.07.2022 23:57 # 0
guest6 05.07.2024 23:57 # 0
guest6 06.07.2024 00:43 # 0
О-о-о, о-о-о!
День может разбиться, как стекло.
Кто же не знает?
Кто же не знает?
Но чтобы всё время не везло,
Так не бывает,
Так не бывает.