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

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

Почему методы сортировки Rust выделяют ресурсы? На мой взгляд, это не соответствует законопроекту "абстракция с нулевой стоимостью", рекламируемому здесь.


sorting rust dynamic-allocation
person kmky    schedule 07.10.2014    source источник
comment
sort_by, на который вы ссылаетесь, является стабильным, поэтому вам следует сравнить его с стабильной сортировкой cpp. , который выделяет память для снижения сложности.   -  person aochagavia    schedule 07.10.2014
comment
@aochagavia, О, я этого не знал (и не удосужился проверить). Значит, в стандартной библиотеке Rust есть нестабильная функция сортировки?   -  person kmky    schedule 07.10.2014
comment
Я не знаю :/... Я бы не удивился, если бы не было стандартной нестабильной сортировки, потому что язык еще не достиг версии 1.0. Может быть, вы могли бы представить PR!   -  person aochagavia    schedule 07.10.2014

Ответы (2)


arrow_upward
7
arrow_downward

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

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

person Fred Foo    schedule 07.10.2014

arrow_upward
7
arrow_downward

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

person terpstra    schedule 25.04.2015