AP
What's the fastest way to sort a jumbled array, given that the array has length N and contains the integers from 1 to N inclusive?
ничего смешного. просто вписать туда фором числа в один проход
Size: a a a
2020 January 15
VG
ну это и смешно
AK
Есть же разные подходы: я стремлюсь делать универсальные вещи, скажем так, больше, чем решать конкретную задачу.
И да, O-большое - это самый пессимистичный подход из всего, что я видел, и тем не менее на нём все помешаны, потому что он даёт мнимую ясность даже там, где ясности быть не может
И да, O-большое - это самый пессимистичный подход из всего, что я видел, и тем не менее на нём все помешаны, потому что он даёт мнимую ясность даже там, где ясности быть не может
AP
реальная оценка О полезна при "глобальных" алгоритмах, когда у тебя матрицы с размерностью в миллионы тому подобно. в остальных случаях бенчмаркать надо
AP
при том бенчмаркать именно в твоих вычислительных условиях с твоими датасетами. универсально ему подавай. хороший планировщик скл не всегда оставит один и тот же план выполнения для разных бинд-параметров
AK
ничего смешного. просто вписать туда фором числа в один проход
Кстати, интересно, есть алгоритмы сортировки, основанные на высокодискретном таймере? Это было бы забавно, но даже не представляю, как на реальных архитектурах сделать. Типа того, что значение push'ится в отсортированный массив через через N тиков таймера, где N - либо само значение, либо производная от него. На правах полного бреда, но... это было бы забавно.
AP
это был баш-скрипт такой
AP
получалось на экране отсортированно
AK
при том бенчмаркать именно в твоих вычислительных условиях с твоими датасетами. универсально ему подавай. хороший планировщик скл не всегда оставит один и тот же план выполнения для разных бинд-параметров
Ну, библиотеки-то всё же универсальны, и обычно для решения той самой "задачи" всё-таки не пишется весь код с нуля :)
IB
sleep sort это называется
AP
библиотеки умеют при старте компа выбирать свои нужные куски под архитектуру
AK
библиотеки умеют при старте компа выбирать свои нужные куски под архитектуру
Ну если не perl'овые библиотеки :)
AP
ладно, бенчмарки будут?
AK
sleep sort это называется
Интересно!.. Я думал, это плод моей больной фантазии :)
IB
вот еще один пример смешного способа отсортировать:
IB
while not
isInOrder(deck):
shuffle(deck)AP
а то я вроде не словом, а даже делом пытался помочь, но, кажется, напрасно
AK
а то я вроде не словом, а даже делом пытался помочь, но, кажется, напрасно
Мне не хочется xor, прямо совсем. Он используется тобой только по той причине, что реализован внутри сишным кодом.
Я думаю, ты не будешь возражать против того, что написанный на Си алгоритм сравнения тем же xor'ом, но side-by-side - всё ж таки пошустрее будет в общем случае?
Я думаю, ты не будешь возражать против того, что написанный на Си алгоритм сравнения тем же xor'ом, но side-by-side - всё ж таки пошустрее будет в общем случае?
AK
Ну т.е., повторюсь, если у тебя 1 символ в самом начале совпадает, а остальные пусть даже 250 не совпадают, то xor'ить всё - так себе затея-то
AP
я не буду против, но я хотел бенчмарки :)