Является ли timsort универсальным или специфичным для Python?

Timsort - это адаптивная, стабильная, естественный слияние. Это сверхъестественное производительность по многим видам частично упорядоченные массивы (меньше lg (N!) необходимых сравнений, и всего лишь N-1), но так же быстро, как предыдущий Python высоко настраиваемый гибрид образцов случайные массивы.

Вы видели timsort, используемый вне CPython? Имеет ли смысл?

Ответы

Ответ 1

Да, довольно разумно использовать timsort вне CPython, в частности, или Python вообще.

В настоящее время выполняется , чтобы заменить Java "модифицированный сортировка слияния" на timsort, и исходные результаты довольно положительные.

Ответ 2

Алгоритм довольно общий, но преимущества скорее специфичны для Python. В отличие от большинства процедур сортировки, что Python list.sort(то, что использует timsort) заботится о том, чтобы избежать ненужных сравнений, потому что в целом сравнения намного дороже, чем подкачки (которые всегда представляют собой набор копий указателя) или даже выделение некоторых дополнительная память (потому что это всегда просто массив указателей, а накладные расходы малы по сравнению со средними накладными расходами в любой операции Python.)

Если вы находитесь в одинаковых ограничениях, тогда это может быть удобно. Я еще не видел другого случая, когда сравнение действительно так дорого, хотя: -)

Ответ 3

Это не выглядит особенно знакомым, но "умные" слияния довольно распространены в широком мире программного обеспечения.

Что касается того, имеет ли это смысл, это зависит от того, что вы сортируете, и относительной стоимости сравнений и распределения памяти. Сорт, который требует до 2 * N байтов дополнительной памяти, не будет хорошим выбором в среде с ограничением памяти.

Ответ 4

Теперь ответ на Wikipedia: timsort будет использоваться в Java 7, который скопировал его с Android.

Ответ 6

Описание, которое вы связываете, выглядит полностью общим.