Является ли timsort универсальным или специфичным для Python?
https://stackoverflow.com/questions/154504
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Тимскорт - это адаптивный, стабильный, естественный смеситель.Он обладает сверхъестественной производительностью во многих видах частично упорядоченных массивов (меньше, чем требуется сравнения LG (N!), И всего лишь N-1), но так же быстро, как предыдущий высоко настроенный гибрид Samplesort Python на случайных массивах.
Ты видел Тимсорт используется вне CPython?Имеет ли это смысл?
Решение
Да, имеет смысл использовать timsort вне CPython в частности или Python в целом.
В настоящее время существует предпринимаются усилия заменить «модифицированную сортировку слиянием» Java на timsort, и первоначальные результаты весьма положительные.
Другие советы
Алгоритм довольно общий, но преимущества скорее специфичны для Python.В отличие от большинства процедур сортировки, Python list.sort (который использует timsort) заботится о том, чтобы избежать ненужных сравнений, поскольку обычно сравнения — это много дороже, чем замена элементов (которая всегда представляет собой просто набор копий указателей) или даже выделение некоторой дополнительной памяти (потому что это всегда просто массив указателей, а накладные расходы невелики по сравнению со средними накладными расходами в любой операции Python.)
Если у вас аналогичные ограничения, то это может подойти.Однако я еще не видел ни одного случая, когда сравнения действительно были бы настолько дорогими :-)
Это не выглядит особенно знакомым, но «умные» сортировки слиянием довольно распространены в широком мире программного обеспечения.
Что касается того, имеет ли это смысл, это зависит от того, что вы сортируете, и относительной стоимости сравнений по сравнению с другими.выделение памяти.Сортировка, требующая до 2*N байт дополнительной памяти, не будет хорошим выбором в среде с ограниченной памятью.
Ответил сейчас на Википедия:timsort будет использоваться в Java 7, которая скопировала его из Android.
Timsort теперь и в Android: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
Описание, которое вы привели, выглядит совершенно общим.
