Войти
ФлеймФорумОбщее

Обогнал std::quicksort (2 стр)

Страницы: 1 2 3 Следующая »
#15
15:20, 31 июля 2021

Super_inoy

Ты хочешь денег? Спонсируй мою академию волшебства. Акции вырастут в цене многократно.


#16
15:23, 31 июля 2021

Олег_Дорожко
> Может запилим сайт внеконкурсных сортировок?
Не только саму сортировку, но уже и сайт такой запилили.
Вот она: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%8… 2%D0%BE%D0%BC

#17
15:25, 31 июля 2021

entryway

Сортировка подсчетом разве обгоняет самый быстрый алгоритм по википедии?

#18
(Правка: 15:31) 15:29, 31 июля 2021

Суть алгоритма:

void sort(std::vector<int> xs) {
    std::vector<int> ns(xs.size(), 0);
    for (int x: xs) {
        ns[x] += x;
    }
    size_t ptr = 0;
    for (int x = 0; x < ns.size(); ++x) {
        while (ns[x] != 0) {
            xs[ptr] = x;
            ns[x] -= x;
            ptr += 1;
        }
    }
}
Да, он ломается, если элементы массива выходят за пределы [1; xs.size()-1].
Да, он вместо количества элементов хранит их сумму.
Да, ns[0] всегда равен нулю.
Да, поэтому допустимый диапазон начинается не с нуля, а с единицы.
Нет, Олег ещё отдельно обрабатывает случаи нуля и одного элементов через ифы.
Нет, под результат Олег выделяет третий массив, старый не перезаписывается. Только поэтому, в примере Super_inoy в конце массива - потерянные нули, а не гарбаг.
Код крайне неопрятен, как будто это куча грязной посуды в тазике. И работает соответствующе.
Да, я знаю, что 95% посетивших этот тред смогут догадаться и сами. Я просто помогаю им сэкономить время.

#19
(Правка: 15:34) 15:30, 31 июля 2021

Delfigamer

Я поставлю статую в твою честь!!

P.S. Опровергни мой код пожалуйста. На своей машине.

Признаю, мой код на коленке сделан. Я двадцать лет не юзал с++
Признаю, что только положительные.

Там потом нули в начало еще перекинуть.

#20
16:10, 31 июля 2021

Олег_Дорожко
проблема сортировки подсчетом (это твой алгоритм) в том что если в массиве числа типа 100000000 и 23456789 то она сломается или потребует очень много памяти. Но в частном случае, когда числа не очень большие - да, она быстрее обычной сортировки.
Можно слегка доработать и получить Radix sort - вот https://gamedev.ru/flame/forum/?id=227644 FordPerfect некоторое время назад пытался сделать самый быстрый вариант.

#21
16:21, 31 июля 2021

kipar

В видео я использовал 50 млн. максимально. То есть, индекс промежуточного массива максимально например такой 34000000

быстрее обычной сортировки

Супер! Спасибо. Мне как раз это и надо. Есть у меня софтинка -  ей пригодится как раз такая сортировка. Где числа в исходном массиве небольшие.

#22
(Правка: 16:36) 16:30, 31 июля 2021

kipar

Я NUM последовательно (при прохождении по исходному массиву) нахожу и тыкаю прямо в результирующий массив вот так res_arr[NUM] += NUM

И получается самосортирование.

#23
(Правка: 17:09) 16:58, 31 июля 2021

Олег_Дорожко
> В видео я использовал 50 млн. максимально. То есть, индекс промежуточного
> массива максимально например такой 34000000
У тебя же там mingw, и RAND_MAX равен 32767, хватит массива размером 32768, вместо 50 млн.

#24
16:59, 31 июля 2021

Олег_Дорожко
> res_arr[NUM] += NUM
А почему не res_arr[NUM] += 1?

#25
(Правка: 19:23) 19:19, 31 июля 2021

Олег_Дорожко

тебе скока лет то ? :D кому надо быстро - те на GPGPU сортируют .. всякие Bitonic Sort | Radix Sort ..

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

#26
(Правка: 20:11) 19:30, 31 июля 2021

Delfigamer

А сам не хочешь понять?
Ответ от автора получить легко, но едва ли полезно для развития мозгов.
Так что, я тут в замешательстве - открывать тебе секрет или ты сам его откроешь.
В видео, в конце, если что, код.

#27
19:31, 31 июля 2021

xma

GPU ? а где оно в Lenovo v570c win10?

#28
(Правка: 19:31) 19:31, 31 июля 2021
res_arr[NUM] += NUM

Какой секретный секрет :)
#29
19:42, 31 июля 2021

Олег_Дорожко
> GPU ? а где оно в Lenovo v570c win10?

а да, у тебя на ноуте - нет opencl
https://www.techpowerup.com/gpu-specs/hd-graphics-2000.c1248

Страницы: 1 2 3 Следующая »
ФлеймФорумОбщее