Почему методы сортировки Rust выделяют память?

Методы, подобные sort_by по адресу std::slice::MutableSliceAllocating или sort_by по адресу collections::vec::Vec, задокументированы до «выделяют приблизительно 2 * n, где n - длина». Я не думаю, что хорошие реализации C++ std::sort выделяют (на кучу), и все же они выполняют ту же сложность O (n log n). Хотя методы сортировки ржавчины устойчивы в отличие от C++ std :: sort.Почему методы сортировки Rust выделяют память?

Почему методы сортировки ржавчины выделяются? Для меня это не соответствует «нулевая стоимость абстракции» выставлен счет here.

источник

2014-10-07 kmky

Ссылка на 'sort_by' стабильна, поэтому вы должны сравнить ее с [стабильной сортировкой cpp] (http://en.cppreference.com/w/cpp/algorithm/stable_sort), которая выделяет память для достижения более низкая сложность. – aochagavia

@aochagavia, О, я не знал этого (и не удосужился проверить). Есть ли неустойчивая функция сортировки в стандартной библиотеке Rust? – kmky

Я не знаю:/... Я не удивлюсь, если нет стандартного нестабильного сорта, потому что язык не достиг 1.0. Может быть, вы можете подать PR! – aochagavia

Как указано в комментарии, это стабильный вид, который требует выполнения O (n) пространства. Лучший устойчивый тип O (n log n), mergesort, требует около ½ временных элементов. (Я не знаком с Rust, поэтому я не знаю, зачем это нужно в четыре раза.)

Стабильный вид может быть достигнут в пространстве O (log n), но только на mergesort variant, который принимает O (n log² n) время.

источник

2014-10-07 13:19:37

Я понимаю, что это старый пост, но я нашел его на google и популярный ответ неправильный. Фактически можно выполнить стабильную сортировку на месте с использованием O (1) (даже журнальной) памяти и наихудшего времени O (nlogn). См. Например, GrailSort или WikiSort.

источник

2015-04-25 08:42:54 terpstra

Почему методы сортировки Rust выделяют память?

ответ

Смежные вопросы