Timsort является адаптивным, стабильным, естественным объединением. Она имеет сверхъестественную производительность многих видов частично упорядоченных массивов (менее Lg (N!) сравнения необходимо, а так же мало, как N-1), еще быстрее, чем предыдущий высокоупорядоченной samplesort гибрид Пайтона на случайных массивов ,Является ли timsort универсальным или специфичным для Python?
Вы видели timsort использовали вне CPython? Имеет ли это смысл?
Да, имеет смысл использовать timsort вне CPython, в частности, или Python, в общем.
В настоящее время существует effort underway, чтобы заменить «измененную сортировку слияния» Java на timsort, и исходные результаты являются довольно положительными.
Описание, которое вы указали, выглядит полностью общим.
Это не выглядит особенно знакомым, но «умные» слияния довольно распространены в широком мире программного обеспечения.
Что касается смысла, это зависит от того, что вы сортируете, и относительной стоимости сравнений и распределения памяти. Сорт, который требует до 2 * N байтов дополнительной памяти, не будет хорошим выбором в среде с ограничением памяти.
Алгоритм довольно общий, но преимущества скорее специфичны для Python. В отличие от большинства подпрограмм сортировки, что Python's list.sort (то, что использует timsort) заботится о том, чтобы избежать ненужных сравнений, потому что в целом сравнения являются лот дороже, чем подкачки (это всегда просто набор копий указателя) или даже выделяя некоторую дополнительную память (потому что это всегда просто массив указателей, а накладные расходы малы по сравнению со средними накладными расходами в любой операции Python.)
Если у вас одинаковые ограничения, то это может быть удобно. Я еще не видел другого случая, когда сравнения действительно такие дорогостоящие, хотя :-)
Отправлено сейчас на Wikipedia: timsort будет использоваться в Java 7, который скопировал его с Android.
Timsort также находится в Android сейчас: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
Почему вы спрашиваете? без дополнительного контекста, на ваш вопрос нельзя ответить. – hop 2008-09-30 19:31:28
Вы заметили: «Вы видели timsort, используемый вне CPython?» часть? – Constantin 2008-09-30 19:40:10
Я заметил это, и это все еще не дает нам никакого контекста. Что бы вы узнали из простого «нет» в качестве ответа? – hop 2008-09-30 20:12:56