Suriin at pagsubok ng mga paraan ng pag-uuri. Bahagi I

Noong isang araw, sa mga komento ng VKontakte, nakipagtalo ako sa isa sa iba pang mga mag-aaral ng proyekto. Ang kakanyahan ng hindi pagkakaunawaan ay "sino ang mananalo" - isang pamamaraan sort()mula sa isang klase java.util.Arrayso mga self-written na pagpapatupad ng mga simpleng algorithm: bubble , insertion , selection , shell (Shell algorithm). Para sa ilan, ang sagot sa tanong na ito ay maaaring halata, ngunit dahil lumitaw ang pagtatalo, sa kabila ng katotohanan na ang bawat panig ay may "ginagalang na mga mapagkukunan" na pabor sa pananaw nito, napagpasyahan na magsagawa ng isang pag-aaral, na pinalawak ang kulay-abo na bagay sa ang proseso, pagpapatupad ng iba't ibang mga algorithm. TL;DR: java.util.Arrays.sort() ito ay walang pasubali na nangunguna sa mga arrays ng 100,000 elemento o higit pa; na may mas maliit na sukat, minsan ay maaaring makipagkumpitensya dito ang paraan ng Shell. Ang natitirang bahagi ng isinasaalang-alang na mga algorithm ay ganap na walang laman at maaaring maging kapaki-pakinabang lamang sa ilalim ng ilang kakaibang kundisyon. Ngayon tingnan natin kung paano pinagsunod-sunod ang mga array sa aming mga uber-device na silicon.

Pag-uuri ng pagpili. Pag-uuri ayon sa pagpili

Magsimula tayo sa pinakasimple at pinaka-halatang paraan. Ang kakanyahan nito ay perpektong ipinakita sa amin ni Robert Sedgwick sa kanyang video lecture sa coursera (Sipiin ko ang animation mula doon na masama kong na-compress sa isang gif): View Running through the array from the first element, at every step we hanapin ang pinakamababang elemento sa kanang bahagi, kung saan pinapalitan namin ang kasalukuyang. Bilang resulta, inilalaan namin ang huling bersyon ng aming array sa pinagsunod-sunod na anyo. Narito ang code na nagpapatupad ng algorithm na ito sa Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

Ang pagtatasa ng algorithm ay nagpapakita na kinakailangang magsuklay sa natitirang bahagi ng array sa bawat pass, iyon ay, kakailanganin natin ng eksaktong N + (N-1) + (N-2) + ... + 1 = N^ 2/2 na paghahambing. Kaya, ang pagiging kumplikado ng algorithm ay O(N^2). Ano ang ibig sabihin nito? Nangangahulugan ito na sa pamamagitan ng pagtaas ng bilang ng mga elemento sa array (N) ng 2 beses, tataas natin ang oras ng pagpapatakbo ng algorithm hindi ng 2, ngunit ng 2^2 = 4 na beses. Sa pamamagitan ng pagtaas ng N ng 10 beses, tataas namin ang oras ng pagpapatakbo ng 100 beses, at iba pa. Sa aking 2012 na laptop na may Core i3 processor na tumatakbo sa Ubuntu 14.4, nakuha ko ang sumusunod na oras ng pag-up:

Pag-uuri ng pagpapasok. Pag-uuri ng pagpapasok

Narito ang ideya ay bahagyang naiiba. Muli, bumaling tayo sa animation mula sa Doctor Sedgwick: Tingnan kung ano ang nasa unahan ay hindi pa natin nakikita, at lahat ng iniiwan natin ay laging nananatiling maayos. Ang punto ay "ibinabalik" natin ang bawat bagong elemento ng orihinal na array sa simula hanggang sa ito ay "magpahinga" sa isang mas maliit na elemento. Kaya, mayroon kaming muli na N pass (para sa bawat elemento ng orihinal na array), ngunit sa bawat pass, sa karamihan ng mga kaso, hindi namin tinitingnan ang buong natitira, ngunit isang bahagi lamang. Iyon ay, makakakuha tayo ng opsyon 1 + (N-1) + (N-2) + … + N = N^2/2 lamang kung kailangan nating ibalik ang bawat susunod na elemento sa pinakasimula, iyon ay, sa kaso ng input na pinagsunod-sunod na "in reverse" array (malas, malas). Sa kaso ng isang nakaayos na array (narito ang swerte) magkakaroon ng isang kumpletong freebie - sa bawat pass mayroon lamang isang paghahambing at iniiwan ang elemento sa lugar, iyon ay, ang algorithm ay gagana sa isang oras na proporsyonal sa N. Ang pagiging kumplikado ng algorithm ay matutukoy ng pinakamasamang teoretikal na kaso, iyon ay, O(N^2). Sa karaniwan, ang oras ng pagpapatakbo ay magiging proporsyonal sa N^2/4, ibig sabihin, dalawang beses nang mas mabilis kaysa sa nakaraang algorithm. Sa aking pagpapatupad, dahil sa hindi pinakamainam na paggamit ng permutation, ang oras ng pagpapatakbo ay mas mahaba kaysa sa Selection. Plano kong itama at i-update ang post sa lalong madaling panahon. Narito ang code at ang resulta ng operasyon nito sa parehong makina:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Pag-uuri ng shell. Pag-uuri ng shell

Napansin ng isang matalinong tao, si Donald Schell, noong 1959 na ang pinakamahal na mga kaso sa algorithm para sa mga pagsingit ay kapag ang elemento ay bumalik nang napakalayo sa simula ng array: sa ilang mga pass, ibabalik natin ang elemento sa simula sa pamamagitan ng ilang posisyon. , at sa isa pang pass halos sa buong array hanggang sa simula ay malayo at mahaba. Posible bang gawin ito nang sabay-sabay, tumalon sa maraming elemento? At nakahanap siya ng paraan. Binubuo ito ng sunud-sunod na pagsasagawa ng mga espesyal na partial sort, karaniwang tinatawag na d-sort o, ayon kay Sedgwick, h-sort (hinala ko ang ibig sabihin ng h ay hop). Ang 3-sort, halimbawa, ay ihahambing ang elementong pinag-uusapan hindi sa nauna, ngunit lalaktawan ang dalawa at ihahambing sa isang 3 posisyon pabalik. Kung binago, ihahambing ito muli sa mga posisyon ng elemento 3 pabalik at iba pa. Ang ilalim na linya ay ang resultang array ay magiging "3-sorted", ibig sabihin, ang maling posisyon ng mga elemento ay magiging mas mababa sa 3 posisyon. Ang pagtatrabaho sa insertion algorithm na ito ay magiging madali at kaaya-aya. Sa pamamagitan ng paraan, ang "1-sort" ay hindi hihigit sa isang insertion algorithm =) Sa pamamagitan ng sunud-sunod na paglalapat ng h-sort sa array na may pagbaba ng h value, mas mabilis nating maaayos ang isang malaking array. Narito kung ano ang hitsura nito: Tingnan Ang hamon dito ay kung paano piliin ang tamang pagkakasunud-sunod ng mga bahagyang uri. Sa huli, ang pagganap ng algorithm ay nakasalalay dito. Ang pinakakaraniwan ay ang sequence na iminungkahi ni Donald Knuth: h = h*3 + 1, ibig sabihin, 1, 4, 13, 40, ... at iba pa hanggang 1/3 ng laki ng array. Ang pagkakasunud-sunod na ito ay nagbibigay ng disenteng pagganap at madali ding ipatupad. Ang pagsusuri sa algorithm ay nangangailangan ng maraming wika at lampas sa aking kakayahan. Ang lawak ng pagsusuri ay tinutukoy din ng maraming variant ng h sequence. Sa empirically, masasabi natin na ang bilis ng algorithm ay napakahusay - tingnan para sa iyong sarili: Isang milyong elemento sa wala pang isang segundo! At narito ang Java code na may Knut sequence.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Bubble sort. Paraan ng bubble

Ito ay isang klasiko! Halos bawat baguhan na programmer ay nagpapatupad ng algorithm na ito. Ito ay isang klasiko na si Dr. Sedgwick ay walang kahit isang animation para dito, kaya kailangan kong gawin ang trabaho sa aking sarili. Tingnan Dito, sa bawat pass, binabagtas namin ang array mula simula hanggang katapusan, pinapalitan ang mga kalapit na elemento na wala sa ayos. Bilang resulta, ang pinakamalaking elemento ay "lumulutang" (kaya ang pangalan) hanggang sa dulo ng array. Sinimulan namin ang bawat bagong pass na optimistically umaasa na ang array ay nakaayos na ( sorted = true). Sa dulo ng sipi, kung nakita nating nagkamali tayo, magsisimula tayo ng bagong sipi. Ang hirap dito, muli, binabagtas natin (halos) ang buong array sa bawat pass. Ang paghahambing ay nangyayari sa bawat hakbang, ang palitan ay nangyayari sa halos bawat hakbang, na ginagawang ang algorithm na ito ay isa sa pinakamabagal (kung isasaalang-alang namin ang mga makatwirang ipinatupad, at hindi "pag-uuri ng nanginginig" at iba pang katulad nito). Kapansin-pansin na pormal na ang pagiging kumplikado dito ay magiging katumbas din ng O(N^2), ngunit ang koepisyent ay mas mataas kaysa sa mga pagsingit at mga seleksyon. Algorithm code:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Oras ng pagpapatakbo: Pakiramdam ang pagkakaiba: higit sa kalahating oras sa isang milyong elemento! Konklusyon: Huwag kailanman gamitin ang algorithm na ito!!!

Buod ng unang bahagi

Bilang resulta, iminumungkahi kong tingnan ang pangkalahatang talahanayan para sa mga algorithm na ito. Maaari mo ring ihambing sa mga resulta para sa built-in na paraan java.util.Arrays.sort(). Mukhang isang uri ng magic - ano ang maaaring mas mabilis kaysa sa Shell? Isusulat ko ito sa susunod na bahagi. Doon ay titingnan natin ang malawakang ginagamit na mga algorithm ng mabilisang pag-uuri, pati na rin ang pagsasama-sama ng pag-uuri, alamin ang tungkol sa pagkakaiba sa mga pamamaraan para sa pag-uuri ng mga array mula sa mga primitive at uri ng sanggunian, at makilala din ang isang napakahalagang interface sa bagay na ito Comparable;) Sa ibaba maaari kang mag-aral isang graph na binuo sa isang logarithmic scale gamit ang mga talahanayan ng data. Kung mas flatter ang linya, mas maganda ang algorithm =) Para sa mga gustong mag-download ng buong proyekto at magpatakbo ng mga pagsubok nang mag-isa, panatilihin ang link: Java See you in the next part! =)