Timsort универсален или специфичен для Python?
Timsort is an adaptive, stable, natural mergesort. It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.
Вы видели использование Timsort вне CPython? Имеет ли это смысл?
Вы заметили: «Вы видели, что timsort используется вне CPython?» часть?
Я заметил это, и это до сих пор не дает нам контекста. что бы вы узнали из простого «нет» в качестве ответа?
"timsort" действительно очень специфичен, хотя для вас это не будет иметь большого значения, если вы не знаете, что такое timsort.
Ответы 7
Описание, которое вы связали, выглядит совершенно общим.
Да, но видели ли вы, что timsort используется вне CPython?
Это не выглядит особенно знакомым, но «умные» слияния довольно распространены в широком мире программного обеспечения.
Что касается того, имеет ли это смысл, это зависит от того, что вы сортируете, и относительной стоимости сравнений по сравнению с выделением памяти. Сортировка, требующая до 2 * N байтов дополнительной памяти, не будет хорошим выбором в среде с ограниченным объемом памяти.
Вы говорите о Тимсорте в своем последнем предложении? Не требуется 2 * N байтов дополнительной памяти.
Из связанного описания в исходном вопросе: «+ timsort может потребовать временный массив, содержащий до N // 2 указателей, что означает до 2 * N дополнительных байтов в 32-битных блоках».
Спасибо, что разъяснили. Поскольку вы предположили 32-битную арку в предложении в своем ответе, было бы неплохо прямо упомянуть об этом в нем.
Алгоритм довольно общий, но преимущества скорее зависят от Python. В отличие от большинства процедур сортировки, Python list.sort (который использует timsort) заботится об избежании ненужных сравнений, потому что обычно сравнения на много дороже, чем замена элементов (который всегда представляет собой просто набор копий указателя) или даже выделение некоторых из них. дополнительная память (потому что это всегда просто массив указателей, а накладные расходы небольшие по сравнению со средними накладными расходами в любой операции Python).
Если вы находитесь в аналогичных условиях, это может подойти. Я еще не видел другого случая, когда сравнения действительно были бы настолько дорогими :-)
Если сравнение стоит дорого, то алгоритм, ориентированный на данные, обычно работает лучше, чем алгоритм, основанный на сравнении.
Это хорошее наблюдение и, возможно, главная причина, по которой вы не увидите тимсорт или что-то подобное в дикой природе.
Преимущества зависят от нет Python. Такое же преимущество использования Timsort в Python для сортировки списка ссылок на объекты существует в любом языке программирования, который имеет указатели или ссылки на объекты. Например, Java SE 7+, Android и Swift используют Timsort для сортировки объектов.
Да, имеет смысл использовать timsort вне CPython, в частности, или Python в целом.
В настоящее время существует прилагаются усилия для замены "модифицированной сортировки слиянием" в Java на timsort, и первоначальные результаты весьма положительны.
Java SE 7 теперь использует Timsort в качестве алгоритма сортировки. См. docjar.com/docs/api/java/util/Collections.html#sort(List)
Ответил сейчас на Википедия: timsort будет использоваться в Java 7, который скопировал его с Android.
Timsort теперь также в Android: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
Timsort является специфичным для Python нет. Преимущества использования Timsort в Python для сортировки списка ссылок на объекты существуют на любом языке программирования, который имеет указатели или ссылки на объекты. Например, Java SE 7+, Android и Swift используют Timsort для сортировки объекты.
С другой стороны, некоторые варианты быстрой сортировки (например, внутренняя сортировка, быстрая сортировка с двумя поворотами) обычно сортируют примитивные типы быстрее из-за согласованности кеша, и поэтому обычно выбирают для этой задачи.
почему ты спрашиваешь? без дополнительного контекста на ваш вопрос невозможно ответить.