Сколько времени занимает сортировка 2,5 миллионов чисел с помощью HeapSort?

У меня есть 2,5 миллиона записей/чисел, которые я использую HeapSort для их сортировки путем вставки в отсортированную кучу. Но это занимает вечность .. Я знаю, что время работы heapsort составляет O (nlogn), но в реальной жизни, на обычном компьютере, о каком времени мы здесь говорим? У меня 8 Гб. ОЗУ на моем компьютере с Windows, но у меня есть Ubuntu с двойной загрузкой, которая, как я полагаю, выбрана для работы с 1 ГБ ОЗУ.

На 15 000 номеров ушло менее 15 секунд. пропорционально говоря, это займет около 40 минут?


sorting algorithm heapsort
person razshan    schedule 22.03.2014    source источник
comment
На ваш вопрос нельзя ответить без точного знания языка выполнения, типа элементов (ну, числа могут быть плоскими ячейками памяти или заключенными в объекты), функции сравнения и т. д., а результирующий коэффициент может различаться во много сотен раз. Пожалуйста, укажите более подробную информацию. OTOH Я думаю, что 15 секунд для 15000 чисел определенно слишком много, даже если каждое число является отдельным объектом в Visual Basic :), поэтому что-то не так в вашем алгоритме или настройке.   -  person Netch    schedule 22.03.2014
comment
Это не лучший способ сортировки в куче, но трудно понять, какие у вас есть альтернативы, поскольку вы даже не упоминаете, какой язык используете. Обычно для heapsort используется что-то вроде en.cppreference.com/w/cpp/algorithm/ make_heap (это быстро), а затем удаляйте элементы по порядку по одному. (Если вы всегда помещаете удаленный элемент в конец кучи, которая становится на единицу короче с каждым удалением, то вы получите отсортированный вектор.)   -  person rici    schedule 22.03.2014
comment
пожалуйста, опубликуйте код.   -  person anonymous    schedule 22.03.2014
comment
С чисто математической точки зрения, при прочих равных условиях, для обработки 2,5 миллионов чисел требуется около 65 минут, если обработка 15 000 чисел занимает 15 секунд.   -  person aroth    schedule 22.03.2014
comment
Сортировка 2,5 миллионов элементов с использованием пирамидальной сортировки должна занять ... около секунды (или, может быть, несколько). Вероятно, что-то серьезно не так с вашим алгоритмом, если сортировка всего 15k занимает 15 секунд.   -  person Bernhard Barker    schedule 22.03.2014
comment
2^14=16384 > 15000 so n log n (15 000) ‹ 210 000, и выполнение такого количества сравнений должно занимать намного меньше 15 секунд на машине с тактовой частотой ГГц.   -  person mcdowella    schedule 22.03.2014

Ответы (2)


arrow_upward
3
arrow_downward

Для грубой оценки, при условии отсутствия дополнительных накладных расходов, связанных с памятью, при масштабировании с 15 тыс. strong>64 минуты

person aha    schedule 22.03.2014

arrow_upward
0
arrow_downward

Я не знаю о сортировке кучей, и мои глаза вылезают, когда я смотрю на исходный запрос, сортирующий 15 секунд для 15 000 чисел, или на принятый ответ, который объясняет это, но по умолчанию С++ STL сортирует вектор 2,5M целые числа занимают у меня ‹ 100 мс. Скомпилировано с -O3, если конечно нет: ‹ 700мс.

person Íhor Mé    schedule 16.08.2020