Comments 18
Стоит заметить, что автор испугался далее повышать размер сортируемого массива (хотя на млрд. элементов в тестах замахивался), боясь получить отрицательные значения выгоды, и ненароком разорвать структуру пространства-бытия.
Да, речь же шла о супербольших объёмах, а тут все закончилось несчастным миллионом. Странно.
Как дилетант, интересуюсь - а нельзя ли сортировать такие массивы на каждом из сотен (тысяч?) маленьких процессоров GPU параллельно? Или так и делается уже?
Представьте общественности алгоритм сортировки на GPU составных объектов, физически размещаемых на файловых носителях. большинство авторов больше как сортировку натуральных чисел предложить не могут. даже сортировку строк никто не предложил. А все потому что при сортировке подобных данных вас необходимо работать с указателями. Т.е. вы фактически перемещаете указатели, а сами данные физически не сортируются. В этом проблема
Прошу меня простить за столь резкий комментарий. Вы не обязаны ничего представлять общественности, наоборот это я должен доказывать. Но проблемы сортировки на GPU что я озвучил выше - никуда не делись. И я действительно не встречал годные реализации сортировок на GPU для, например, использования СУБД
Гугл сходу такое выдаёт - в реальной жизни не работает?
Ничего не понял. В чем проблема перемещать сами объекты в файлах? Как напишешь, так и будет.
Да тут один человек сказал, что выигрыш мизерный . Даже если бы я представил измерения для 100ГБ элементов - вряд ли это бы повлияло на столь высокую оценку.
На основе представленных измерений тенденция видна. Как доказательство, что концепция верна .
Я специально для вас опубликую код и замеры на массиве из 1 миллиарда записей. Но чуть позже. Просто мне необходимо привести свой экспериментальный проект в божеский вид. А то в процессе экспериментов там лапша по-гуще ассамблера сейчас
Такой размер подойдёт? Сортируемые данные будут находить на диске в момент выполнения сортировки. В оперативную память моего старенького компьютера они не поместится. Поэтому сортироваться будут по факту индексы( указатели на json-записи).Сортируемые данные будут являться json-записями , ключом сортировки - будет текстовое поле объекта длиной до 16 символов.
Сделаем замеры скорости в операциях и по времени. Вас устроит такой вариант теста?
N(logN - log k)=NlogN - Nlogk
То есть даже теоретически с учётом размеров величин выигрыш мизерный
Я правильно понял что экономия 16 млн операций при сортировке 1млн объектов, для вас мизерная?
Это не считая возможности без проблем выполнить сортировку параллельно в 16 потоков.
N = миллиарды
K = тысячи
Посчитайте
Хорошо. Пусть N=10^9, k=1000,
Тогда Nlogk=10^9*10(примерно 10 - логарифма тут двоичный).
Итого почти 10 млд. Операций экономия. Среди этих операций-операции сравнения ключей, которые для составных ключей могут быть очень не быстрыми. Стоимость сравнения строк, например, O(n). Так что насчет мизерной выгоды нисколько не согласен.
Но если все кластеры сортировать параллельно, то по времени выигрыш должен получиться больше. Нет?
Кластеризация сама по себе понижает затраты и без параллельности. Проблема только в том, что она не всегда возможна.
Классически, можно поделить и петлями quick sort.
Плавная сортировка в худшем случае O(N (log(N)^2))
Параллельные сортировки больших массивов объектов и пути уменьшения асимптотической сложности лучших алгоритмов