Timsort

Поделись знанием:
Перейти к: навигация, поиск

Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. В настоящее время Timsort является стандартным алгоритмом[1] сортировки в Python, OpenJDK 7[2] и реализован в Android JDK 1.5[3]. Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки[4].





Основная идея алгоритма

  • По специальному алгоритму входной массив разделяется на подмассивы.
  • Каждый подмассив сортируется сортировкой вставками.
  • Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием.

Принципиальные особенности алгоритма в деталях, а именно в алгоритме разделения и модификации сортировки слиянием.

Алгоритм

К:Википедия:Статьи без источников (тип: не указан)

Используемые понятия

  • N — размер входного массива
  • run — упорядоченный подмассив во входном массиве. Причём упорядоченный либо нестрого по возрастанию, либо строго по убыванию. Т.е:
    • либо «<math>a_0 \leqslant a_1 \leqslant a_2 \leqslant ...</math>»,
    • либо «<math>a_0 > a_1 > a_2 > ...</math>»
  • minrun — как было сказано выше, на первом шаге алгоритма входной массив будет поделен на подмассивы. minrun — это минимальный размер такого подмассива. Это число рассчитывается по определённой логике из числа N.

Шаг 0. Вычисление minrun.

(1) Число minrun (минимальный размер упорядоченной последовательности) определяется на основе N исходя из следующих принципов: оно не должно быть слишком большим, поскольку к подмассиву размера minrun будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивах. (2) Оно не должно быть слишком маленьким, поскольку чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для N / minrun это степень числа 2 (или близким к нему). Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.

В этом месте автор алгоритма ссылается на собственные эксперименты, показавшие, что при minrun > 256 нарушается пункт (1), при minrun < 8 — пункт (2) и наиболее эффективно использовать значения из диапазона (32;65). Исключение — если N < 64, тогда minrun = N и timsort превращается в простую сортировку вставкой. В данный момент алгоритм расчёта minrun предельно прост: берутся старшие 6 бит из N и добавляется единица, если в оставшихся младших битах есть хотя бы один ненулевой. Псевдокод:

   int GetMinrun(int n)
   {
       int r = 0;           /* станет 1 если среди сдвинутых битов будет хотя бы 1 ненулевой */
       while (n >= 64) {
           r |= n & 1;
           n >>= 1;
       }
       return n + r;
   }

Шаг 1. Разбиение на подмассивы и их сортировка.

  • Указатель текущего элемента ставится в начало входного массива.
  • Начиная с текущего элемента, в этом массиве идёт поиск упорядоченного подмассива run. По определению, в run однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию — элементы переставляются так, чтобы они шли по возрастанию.
  • Если размер текущего run’а меньше, чем minrun — выбираются следующие за найденным run-ом элементы в количестве minrun — size(run). Таким образом, на выходе будет получен подмассив размером minrun или больше, часть которого (а в идеале — он весь) упорядочена.
  • К данному подмассиву применяется сортировка вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает быстро и эффективно.
  • Указатель текущего элемента ставится на следующий за подмассивом элемент.
  • Если конец входного массива не достигнут — переход к пункту 2, иначе — конец данного шага.

Шаг 2. Слияние.

Если данные входного массива были близки к случайным — размер упорядоченных подмассивов близок к minrun, если в данных были упорядоченные диапазоны — упорядоченные подмассивы имеют размер, превышающий minrun. Нужно объединить эти подмассивы для получения результирующего, полностью упорядоченного массива. Для достижения эффективности Объединение должно удовлетворять двум требованиям:

  • Объединять подмассивы примерно равного размера
  • Сохранить стабильность алгоритма — то есть не делать бессмысленных перестановок.

Алгоритм:

  • Создается пустой стек пар <индекс начала подмассива>-<размер подмассива>. Берётся первый упорядоченный подмассив.
  • В стек добавляется пара данных <индекс начала>-<размер> для текущего подмассива.
  • Определяется, нужно ли выполнять процедуру слияния текущего подмассива с предыдущими. Для этого проверяется выполнение двух правил (пусть X, Y и Z — размеры трёх верхних в стеке подмассивов):
   X > Y + Z
   Y > Z
  • Если одно из правил нарушается — массив Y сливается с меньшим из массивов X и Z. Повторяется до выполнения обоих правил или полного упорядочивания данных.
  • Если еще остались не рассмотренные подмассивы — берётся следующий и переходим к пункту 2. Иначе — конец.

Цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке справа, а значит, размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием. В идеальном случае: есть подмассивы размера 128, 64, 32, 16, 8, 4, 2, 2. В этом случае никакие слияния не выполнятся, пока не встретятся 2 последних подмассива, после чего будут выполнены 7 идеально сбалансированных слияний.

Процедура слияния подмассивов

  1. Создаётся временный массив в размере меньшего из соединяемых подмассивов.
  2. Меньший из подмассивов копируется во временный массив
  3. Указатели текущей позиции ставятся на первые элементы большего и временного массива.
  4. На каждом следующем шаге рассматривается значение текущих элементов в большем и временном массивах, берётся меньший из них и копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
  5. Пункт 4 повторяется, пока один из массивов не закончится.
  6. Все элементы оставшегося массива добавляются в конец нового массива.

Модификация процедуры слияния подмассивов (Galloping Mode)

Представим себе процедуру слияния следующих массивов:

A = {1, 2, 3,..., 9999, 10000}
B = { 20000, 20001, ...., 29999, 30000}

Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге 10000 сравнений и 10000 копирований. Алгоритм Timsort предлагает в этом месте модификацию, которую он называет «галоп». Алгоритм:

  • Начинается процедура слияния, как было показано выше.
  • На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.
  • Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из одного и того же массива — предполагается, что и дальше нам придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим «галопа», то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.
  • В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.

Режим галопа на примере:

Исходные массивы:
A = {1, 2, 3,..., 9999, 10000}
B = { 20000, 20001, ...., 29999, 30000}

Первые 7 итераций сравниваются числа 1, 2, 3, 4, 5, 6 и 7 из массива A с числом 20000, так как 20000 больше — элементы массива A копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим «галопа»: сравнивает с числом 20000 последовательно элементы 8, 10, 14, 22, 38, n+2^i, …, 10000 массива A. (~log2 N сравнений). После того как конец массива A достигнут и известно, что он весь меньше B, нужные данные из массива A копируются в результирующий.

Напишите отзыв о статье "Timsort"

Примечания

  1. [xakep.ru/2015/02/25/timsort-bug/ Некорректная работа функции сортировки в Android, Java и Python]. «Хакер». Проверено 5 декабря 2015.
  2. jjb [hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort]. Java Development Kit 7 Hg repo. Проверено 24 февраля 2011. [www.webcitation.org/6AQdENbYS Архивировано из первоисточника 4 сентября 2012].
  3. [www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort Class: java.util.TimSort<T>]. Android JDK 1.5 Documentation. Проверено 24 февраля 2011. [www.webcitation.org/6AQdF05Sq Архивировано из первоисточника 4 сентября 2012].
  4. Hetland, 2010.

Литература

  • Peter McIlroy "Optimistic Sorting and Information Theoretic Complexity", Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7, Chapter 53, pp 467-474, January 1993. [dl.acm.org/citation.cfm?id=313859]
  • Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с. — ISBN 978-1-4302-3237-7.

Ссылки

  • [bugs.python.org/file4451/timsort.txt Представление алгоритма от его создателя] (англ.). [www.webcitation.org/6AQdFVhcg Архивировано из первоисточника 4 сентября 2012].
  • [codespeak.net/pypy/dist/pypy/rlib/listsort.py Timsort, реализованный на Python для PyPy] (англ.) (py). [www.webcitation.org/6AQdFxx33 Архивировано из первоисточника 4 сентября 2012].
  • [corte.si/posts/code/timsort/index.html Визуализация алгоритма] (англ.). [www.webcitation.org/6AQdGPXFZ Архивировано из первоисточника 4 сентября 2012].


Отрывок, характеризующий Timsort

Он потрепал ее по плечу и сам запер за нею дверь.
Княжна Марья возвратилась в свою комнату с грустным, испуганным выражением, которое редко покидало ее и делало ее некрасивое, болезненное лицо еще более некрасивым, села за свой письменный стол, уставленный миниатюрными портретами и заваленный тетрадями и книгами. Княжна была столь же беспорядочная, как отец ее порядочен. Она положила тетрадь геометрии и нетерпеливо распечатала письмо. Письмо было от ближайшего с детства друга княжны; друг этот была та самая Жюли Карагина, которая была на именинах у Ростовых:
Жюли писала:
«Chere et excellente amie, quelle chose terrible et effrayante que l'absence! J'ai beau me dire que la moitie de mon existence et de mon bonheur est en vous, que malgre la distance qui nous separe, nos coeurs sont unis par des liens indissolubles; le mien se revolte contre la destinee, et je ne puis, malgre les plaisirs et les distractions qui m'entourent, vaincre une certaine tristesse cachee que je ressens au fond du coeur depuis notre separation. Pourquoi ne sommes nous pas reunies, comme cet ete dans votre grand cabinet sur le canape bleu, le canape a confidences? Pourquoi ne puis je, comme il y a trois mois, puiser de nouvelles forces morales dans votre regard si doux, si calme et si penetrant, regard que j'aimais tant et que je crois voir devant moi, quand je vous ecris».
[Милый и бесценный друг, какая страшная и ужасная вещь разлука! Сколько ни твержу себе, что половина моего существования и моего счастия в вас, что, несмотря на расстояние, которое нас разлучает, сердца наши соединены неразрывными узами, мое сердце возмущается против судьбы, и, несмотря на удовольствия и рассеяния, которые меня окружают, я не могу подавить некоторую скрытую грусть, которую испытываю в глубине сердца со времени нашей разлуки. Отчего мы не вместе, как в прошлое лето, в вашем большом кабинете, на голубом диване, на диване «признаний»? Отчего я не могу, как три месяца тому назад, почерпать новые нравственные силы в вашем взгляде, кротком, спокойном и проницательном, который я так любила и который я вижу перед собой в ту минуту, как пишу вам?]
Прочтя до этого места, княжна Марья вздохнула и оглянулась в трюмо, которое стояло направо от нее. Зеркало отразило некрасивое слабое тело и худое лицо. Глаза, всегда грустные, теперь особенно безнадежно смотрели на себя в зеркало. «Она мне льстит», подумала княжна, отвернулась и продолжала читать. Жюли, однако, не льстила своему другу: действительно, и глаза княжны, большие, глубокие и лучистые (как будто лучи теплого света иногда снопами выходили из них), были так хороши, что очень часто, несмотря на некрасивость всего лица, глаза эти делались привлекательнее красоты. Но княжна никогда не видала хорошего выражения своих глаз, того выражения, которое они принимали в те минуты, когда она не думала о себе. Как и у всех людей, лицо ее принимало натянуто неестественное, дурное выражение, как скоро она смотрелась в зеркало. Она продолжала читать: 211
«Tout Moscou ne parle que guerre. L'un de mes deux freres est deja a l'etranger, l'autre est avec la garde, qui se met en Marieche vers la frontiere. Notre cher еmpereur a quitte Petersbourg et, a ce qu'on pretend, compte lui meme exposer sa precieuse existence aux chances de la guerre. Du veuille que le monstre corsicain, qui detruit le repos de l'Europe, soit terrasse par l'ange que le Tout Рuissant, dans Sa misericorde, nous a donnee pour souverain. Sans parler de mes freres, cette guerre m'a privee d'une relation des plus cheres a mon coeur. Je parle du jeune Nicolas Rostoff, qui avec son enthousiasme n'a pu supporter l'inaction et a quitte l'universite pour aller s'enroler dans l'armee. Eh bien, chere Marieie, je vous avouerai, que, malgre son extreme jeunesse, son depart pour l'armee a ete un grand chagrin pour moi. Le jeune homme, dont je vous parlais cet ete, a tant de noblesse, de veritable jeunesse qu'on rencontre si rarement dans le siecle оu nous vivons parmi nos villards de vingt ans. Il a surtout tant de franchise et de coeur. Il est tellement pur et poetique, que mes relations avec lui, quelque passageres qu'elles fussent, ont ete l'une des plus douees jouissances de mon pauvre coeur, qui a deja tant souffert. Je vous raconterai un jour nos adieux et tout ce qui s'est dit en partant. Tout cela est encore trop frais. Ah! chere amie, vous etes heureuse de ne pas connaitre ces jouissances et ces peines si poignantes. Vous etes heureuse, puisque les derienieres sont ordinairement les plus fortes! Je sais fort bien, que le comte Nicolas est trop jeune pour pouvoir jamais devenir pour moi quelque chose de plus qu'un ami, mais cette douee amitie, ces relations si poetiques et si pures ont ete un besoin pour mon coeur. Mais n'en parlons plus. La grande nouvelle du jour qui occupe tout Moscou est la mort du vieux comte Безухой et son heritage. Figurez vous que les trois princesses n'ont recu que tres peu de chose, le prince Basile rien, est que c'est M. Pierre qui a tout herite, et qui par dessus le Marieche a ete reconnu pour fils legitime, par consequent comte Безухой est possesseur de la plus belle fortune de la Russie. On pretend que le prince Basile a joue un tres vilain role dans toute cette histoire et qu'il est reparti tout penaud pour Petersbourg.
«Je vous avoue, que je comprends tres peu toutes ces affaires de legs et de testament; ce que je sais, c'est que depuis que le jeune homme que nous connaissions tous sous le nom de M. Pierre les tout court est devenu comte Безухой et possesseur de l'une des plus grandes fortunes de la Russie, je m'amuse fort a observer les changements de ton et des manieres des mamans accablees de filles a Marieier et des demoiselles elles memes a l'egard de cet individu, qui, par parenthese, m'a paru toujours etre un pauvre, sire. Comme on s'amuse depuis deux ans a me donner des promis que je ne connais pas le plus souvent, la chronique matrimoniale de Moscou me fait comtesse Безухой. Mais vous sentez bien que je ne me souc nullement de le devenir. A propos de Marieiage, savez vous que tout derienierement la tante en general Анна Михайловна, m'a confie sous le sceau du plus grand secret un projet de Marieiage pour vous. Ce n'est ni plus, ni moins, que le fils du prince Basile, Anatole, qu'on voudrait ranger en le Marieiant a une personne riche et distinguee, et c'est sur vous qu'est tombe le choix des parents. Je ne sais comment vous envisagerez la chose, mais j'ai cru de mon devoir de vous en avertir. On le dit tres beau et tres mauvais sujet; c'est tout ce que j'ai pu savoir sur son compte.
«Mais assez de bavardage comme cela. Je finis mon second feuillet, et maman me fait chercher pour aller diner chez les Apraksines. Lisez le livre mystique que je vous envoie et qui fait fureur chez nous. Quoiqu'il y ait des choses dans ce livre difficiles a atteindre avec la faible conception humaine, c'est un livre admirable dont la lecture calme et eleve l'ame. Adieu. Mes respects a monsieur votre pere et mes compliments a m elle Bourienne. Je vous embrasse comme je vous aime. Julie».
«P.S.Donnez moi des nouvelles de votre frere et de sa charmante petite femme».
[Вся Москва только и говорит что о войне. Один из моих двух братьев уже за границей, другой с гвардией, которая выступает в поход к границе. Наш милый государь оставляет Петербург и, как предполагают, намерен сам подвергнуть свое драгоценное существование случайностям войны. Дай Бог, чтобы корсиканское чудовище, которое возмущает спокойствие Европы, было низвергнуто ангелом, которого Всемогущий в Своей благости поставил над нами повелителем. Не говоря уже о моих братьях, эта война лишила меня одного из отношений самых близких моему сердцу. Я говорю о молодом Николае Ростове; который, при своем энтузиазме, не мог переносить бездействия и оставил университет, чтобы поступить в армию. Признаюсь вам, милая Мари, что, несмотря на его чрезвычайную молодость, отъезд его в армию был для меня большим горем. В молодом человеке, о котором я говорила вам прошлым летом, столько благородства, истинной молодости, которую встречаешь так редко в наш век между двадцатилетними стариками! У него особенно так много откровенности и сердца. Он так чист и полон поэзии, что мои отношения к нему, при всей мимолетности своей, были одною из самых сладостных отрад моего бедного сердца, которое уже так много страдало. Я вам расскажу когда нибудь наше прощанье и всё, что говорилось при прощании. Всё это еще слишком свежо… Ах! милый друг, вы счастливы, что не знаете этих жгучих наслаждений, этих жгучих горестей. Вы счастливы, потому что последние обыкновенно сильнее первых. Я очень хорошо знаю, что граф Николай слишком молод для того, чтобы сделаться для меня чем нибудь кроме как другом. Но эта сладкая дружба, эти столь поэтические и столь чистые отношения были потребностью моего сердца. Но довольно об этом.