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

Question

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

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

Answer 1

Да, имеет смысл использовать timsort вне CPython, в частности, или Python, в целом.

В настоящее время предпринимается попытка заменить «измененную сортировку слиянием» Java на timsort, и первоначальные результаты весьма положительны.

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

Timsort теперь и в Android: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort

Answer 6

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