Защо Java 6 Arrays#sort(Object[]) се променя от mergesort на insertionsort за малки масиви?

Реализацията на сортиране чрез сливане на Java 6 в Arrays.java използва сортиране чрез вмъкване, ако дължината на масива е по-малка от някакъв праг. Тази стойност е твърдо кодирана на 7. Тъй като алгоритъмът е рекурсивен, това в крайна сметка се случва много пъти за голям масив. Каноничният алгоритъм за сортиране чрез сливане не прави това, а просто използва сортиране чрез сливане докрай надолу, докато остане само 1 елемент в списъка.

Това оптимизация ли е? Ако е така, как би трябвало да помогне? И защо 7? Сортирането чрез вмъкване (дори на <=7 неща) увеличава драстично броя на сравненията, необходими за сортиране на голям масив - така че ще добави разходи за сортиране, при което compareTo() извикванията са бавни.

размер на масив срещу #-на-сравнения за различни стойности на INSERTIONSORT_THRESHOLD

(оста x е size of array, оста y е # of comparisons, за различни стойности на INSERTIONSORT_THRESHOLD)


java algorithm mergesort
person Matthew Gilliard    schedule 11.07.2011    source източник
comment
Какъв е източникът на тази графика? Изглежда, че го представяте без коментар   -  person matt b    schedule 11.07.2011
comment
Направих тази графика чрез сортиране на масив от обекти, които отчитат колко пъти compareTo е извикано и променяйки INSERTIONSORT_THRESHOLD.   -  person Matthew Gilliard    schedule 11.07.2011
comment
Струва си да се отбележи, че Java7 също има Timsort, което е хибридно вмъкване на сливане, разработено от Tim Peters за python. download.java. net/jdk7/docs/api/java/util/   -  person Tremmors    schedule 11.07.2011

Отговори (3)


arrow_upward
18
arrow_downward

Да, това е умишлено. Въпреки че Big-O на mergesort е по-малък от този на квадратичните сортирания като сортиране чрез вмъкване, операциите, които извършва, са по-сложни и следователно по-бавни.

Помислете за сортиране на масив с дължина 8. Сортирането чрез сливане прави ~14 рекурсивни извиквания към себе си в допълнение към 7 операции по сливане. Всяко рекурсивно повикване допринася за някои нетривиални разходи за времето на изпълнение. Всяка операция по сливане включва цикъл, в който индексните променливи трябва да се инициализират, увеличават и сравняват, временните масиви трябва да се копират и т.н. Като цяло можете да очаквате над 300 "прости" операции.

От друга страна, сортирането чрез вмъкване е по своята същност просто и използва около 8^2=64 операции, което е много по-бързо.

Помислете за това по този начин. Когато сортирате списък от 10 числа на ръка, използвате ли сортиране чрез сливане? Не, защото мозъкът ви е много по-добър в извършването на прости неща като сортиране чрез вмъкване. Но ако ви дам една година да сортирате списък от 100 000 числа, може да сте по-склонни да го сортирате чрез сливане.

Що се отнася до магическото число 7, то е емпирично изведено като оптимално.

РЕДАКТИРАНЕ: При стандартно вмъкване от 8 елемента най-лошият сценарий води до ~36 сравнения. При канонично сортиране чрез сливане имате ~24 сравнения. Добавяйки режийните разходи от извикванията на методите и сложността на операциите, сортирането при вмъкване трябва да бъде по-бързо. Освен това, ако погледнете средния случай, сортирането чрез вмъкване ще направи много по-малко сравнения от 36.

person tskuzzy    schedule 11.07.2011
comment
Това обяснение на сложността има много смисъл интуитивно - въпреки че не успях да докажа никакво предимство на 7 конкретно, ›25 имаше значение. - person Matthew Gilliard; 11.07.2011
comment
Редактира отговора ми. Не съм 100% сигурен какво показват вашите бенчмаркове, тъй като вашите оси не са наистина етикетирани. - person tskuzzy; 11.07.2011
comment
+1 това прави много голяма разлика, ако например трябва да сортирате много малки масиви. Усетил съм това на собствената си кожа. - person Gabi Purcaru; 11.07.2011

arrow_upward
4
arrow_downward

Сортирането чрез вмъкване е n(n-1)/2 и сортирането чрез сливане е n*(log n с основа 2).

като се има предвид това -

  1. За масив с дължина 5 => сортиране чрез вмъкване = 10 и сортиране чрез сливане е 11,609
  2. За масив с дължина 6 => сортиране чрез вмъкване = 15 и сортиране чрез сливане е 15,509
  3. За масив с дължина 7 => сортиране чрез вмъкване = 21 и сортиране чрез сливане е 19,651
  4. За масив с дължина 8 => сортиране чрез вмъкване = 28 и сортиране чрез сливане е 24

От горните данни е ясно, че до дължина 6 сортирането чрез вмъкване е по-бързо и след 7 сортирането чрез сливане е ефективно.

Това обяснява защо се използва 7.

person user1289117    schedule 21.02.2013

arrow_upward
3
arrow_downward

Разбирам, че това е емпирично получена стойност, при която времето, необходимо за сортиране чрез вмъкване, всъщност е по-малко, въпреки (възможно) по-голям брой необходими сравнения. Това е така, защото близо до края на сортирането чрез сливане данните вероятно ще бъдат почти сортирани, което прави сортирането чрез вмъкване да работи добре.

person dlev    schedule 11.07.2011
comment
И аз така предположих. Но когато пуснах някои бенчмаркове, установих, че не е така. За евтини операции compareTo всяко число, по-малко от около 20, е приблизително еквивалентно, а за скъпи compareTo времето за сравнение доминира. - person Matthew Gilliard; 11.07.2011
comment
Матю: Обърнете внимание, че скъпите compareTo реализации вероятно не са най-честият случай (не забравяйте, че библиотеката на базовия клас на Java е с доста общо предназначение и не е специално обслужвана точно за вашия случай на употреба) и като използвате сортиране чрез вмъкване в малки подсписъци, можете също да спестите допълнителни разходи за многократно прилагане на алгоритъма D&C или сортиране чрез сливане. - person Joey; 11.07.2011
comment
@Matthew Joey е прав за общата цел на Java BCL. Друг момент, който трябва да се отбележи, е, че наистина скъпите compareTo() методи вероятно трябва да бъдат коригирани, тъй като сравняването на два обекта не трябва да отнема много време. Ако няма начин да се избегне това (може би защото обектите наистина са толкова сложни), може да си струва да сортирате набор от прокси обекти по съответните критерии (тъй като рядко всеки аспект на обект ще бъде взети предвид при сортирането.) - person dlev; 11.07.2011
comment
Разбирам – нямам проблем от реалния живот, който това се опитва да реши ;) Но този алгоритъм се използва само за сортиране на общи обекти – примитивните масиви се обработват по различен начин – така че неизвестна сложността на сравненията трябва да бъде съображение, нали? - person Matthew Gilliard; 11.07.2011
comment
Как се почти сортират данните при извикване на сортирането чрез вмъкване? Mergesort сортира само във фазата на сливане, а извикването за рекурсивно сортиране чрез вмъкване се извършва преди това. - person Paŭlo Ebermann; 11.07.2011