Барраси ва санҷиши усулҳои ҷудокунӣ. Қисми I

Рӯзи дигар дар шарҳҳо дар ВКонтакте ман бо яке аз донишҷӯёни дигари лоиҳа баҳс кардам. Моҳияти баҳс ин буд, ки "кӣ ғолиб хоҳад шуд" - як усул sort()аз синф java.util.Arraysё худнависии алгоритмҳои оддӣ: ҳубобӣ , воридкунӣ , интихоб , ҷилди (алгоритми Shell). Барои баъзеҳо, ҷавоби ин савол шояд равшан бошад, аммо азбаски баҳс ба миён омад, сарфи назар аз он ки ҳар як тараф ба манфиати нуқтаи назари худ "манбаъҳои эҳтиром" доштанд, тасмим гирифта шуд, ки тадқиқот гузаронад, моддаи хокистариро дар раванд, татбиқи алгоритмҳои гуногун. TL; DR: java.util.Arrays.sort() он бечунучаро дар массивҳои 100,000 ё бештар аз он пешсаф аст; бо андозаи хурдтар, усули Shell баъзан метавонад бо он рақобат кунад. Боқимондаи алгоритмҳои баррасишаванда комилан холӣ мебошанд ва танҳо дар баъзе шароити экзотикӣ муфид буда метавонанд. Акнун биёед бубинем, ки массивҳо дар дастгоҳҳои uber-сorкони мо чӣ гуна ҷудо карда мешаванд.

Навъи интихоб. Ҷудокунӣ аз рӯи интихоб

Биёед бо усули соддатарин ва равшантарин оғоз кунем. Моҳияти онро Роберт Седгвик дар лексияи видеоии худ оид ба курсра ба мо комилан нишон додааст (ман аз он ҷо аниматсионӣ, ки ба gif сахт фишурда шудаам, иқтибос меорам): Намоиши давидан аз массив аз элементи аввал, дар ҳар як қадами мо унсури ҳадди ақалро дар тарафи рост ҷустуҷӯ кунед, ки мо бо он унсури ҷорӣро иваз мекунем. Дар натиҷа, мо versionи ниҳоии массивамонро дар шакли мураттабшуда нигоҳ медорем. Ин аст codeе, ки ин алгоритмро дар 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;
    }

Таҳлor алгоритм нишон медиҳад, ки дар ҳар як гузариш боқимондаи массивро шона кардан лозим аст, яъне ба мо маҳз N + (N-1) + (N-2) + ... + 1 = N^ лозим аст. 2/2 муқоисаҳо. Ҳамин тариқ, мураккабии алгоритм O(N^2) аст. Ин чӣ маъно дорад? Ин маънои онро дорад, ки бо 2 маротиба зиёд кардани шумораи элементҳои массив (N) мо вақти кори алгоритмро на 2, балки 2^2 = 4 маротиба зиёд мекунем. N-ро 10 баробар зиёд карда, вакти кор-ро 100 баробар зиёд мекунем ва гайра. Дар ноутбуки соли 2012 бо протсессори Core i3, ки Ubuntu 14.4 дорад, ман вақти кори зеринро гирифтам:

Навъи воридкунӣ. Навъи воридкунӣ

Дар ин ҷо идея каме дигар аст. Боз, биёед ба аниматсия аз Доктор Седгвик муроҷиат кунем: Он чизе ки дар пеш аст, то ҳол аз ҷониби мо дида нашудааст ва ҳама чизе, ки мо паси сар мегузорем, ҳамеша дар ҷои худ боқӣ мемонад. Гап дар он аст, ки мо ҳар як унсури нави массиви аслиро ба аввал "бармегардонем" то он даме, ки он дар як унсури хурдтар "истироҳат кунад". Ҳамин тариқ, мо боз N гузариш дорем (барои ҳар як элементи массиви аслӣ), аммо дар ҳар як гузариш, дар аксари ҳолатҳо, мо на ба тамоми боқимонда, балки танҳо як қисм назар мекунем. Яъне, мо варианти 1 + (N-1) + (N-2) + … + N = N^2/2 мегирем, агар мо бояд ҳар як элементи навбатиро ба ибтидо баргардонем, яъне дар ҳолате аз вуруди массиви "ба баръакс" мураттаб карда шудааст (бадбахт, бадбахт). Дар сурати массиви аллакай мураттабшуда (дар ин ҷо иқбол) ройгони пурра хоҳад буд - дар ҳар як гузариш танҳо як муқоиса мавҷуд аст ва элементро дар ҷои худ мегузорад, яъне алгоритм дар вақти мутаносиб ба N кор хоҳад кард. Мушкилот. аз алгоритми бадтарин ҳолати назариявӣ, яъне О( N^2) муайян карда мешавад. Ба хисоби миёна вакти кор ба N^2/4 мутаносиб мешавад, яъне назар ба алгоритми пештара ду баробар тезтар. Дар татбиқи ман, аз сабаби истифодаи ғайримуқаррарии ивазкунӣ, вақти кор аз вақти Интихоб дарозтар буд. Ман нақша дорам, ки ба зудӣ паёмро ислоҳ ва навсозӣ кунам. Ин аст code ва натиҷаи кори он дар ҳамон мошин:

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;
            }
        }
    }

Навъи қабз. Навъи қабз

Як бачаи доно, Доналд Шел дар соли 1959 пай бурд, ки гаронтарин ҳолатҳо дар алгоритми воридкунӣ вақтест, ки элемент ба оғози массив хеле дур бармегардад: дар баъзе гузариш мо элементро бо якчанд мавқеъ ба аввал бармегардонем. , ва дар дигар ағбаи қариб ба воситаи тамоми массиви ба ибтидо дур ва дароз аст. Оё мумкин аст, ки ин корро якбора, аз якчанд элемент гузаред? Ва ӯ чунин роҳе ёфт. Он аз иҷрои пайдарпай навъҳои махсуси қисман иборат аст, ки маъмулан d-sort ё ба гуфтаи Седгвик, h-сорт номида мешаванд (ман гумон мекунам, h маънои хопро дорад). 3-навъ, масалан, унсури мавриди назарро на бо унсури қаблӣ муқоиса мекунад, балки дуро мегузаронад ва бо як мавқеъи 3 қафо муқоиса мекунад. Агар тағир дода шавад, он бори дигар онро бо унсури 3 мавқеъи бозгашт муқоиса мекунад ва ғайра. Хулоса ин аст, ки массиви ҳосилшуда "3-тарафдор" мешавад, яъне мавқеъи нодурусти элементҳо аз 3 мавқеъ камтар хоҳад буд. Кор бо ин алгоритми воридкунӣ осон ва гуворо хоҳад буд. Воқеан, “1-сорт” танҳо як алгоритми воридкунӣ чизи дигаре нест =) Бо истифодаи пайдарпайи h-sort ба массив бо коҳиши қиматҳои h, мо метавонем массиви калонро тезтар ҷудо кунем. Ин аст, ки чӣ гуна ба назар мерасад: Намоиш Мушкилоти ин ҷо ин аст, ки чӣ тавр интихоб кардани пайдарпайии дурусти навъҳои қисм. Дар ниҳоят, иҷрои алгоритм аз ин вобаста аст. Аз ҳама маъмултарин пайдарпаии пешниҳодкардаи Доналд Кнут аст: h = h*3 + 1, яъне 1, 4, 13, 40, ... ва ғайра то 1/3 андозаи массив. Ин пайдарпаӣ иҷрои муносибро таъмин мекунад ва татбиқи он низ осон аст. Таҳлor алгоритм даҳҳо забонро талаб мекунад ва аз қобorяти ман берун аст. Васеъияти тахлил инчунин бо вариантхои зиёди пайдарпайии h муайян карда мешавад. Ба таври таҷрибавӣ мо метавонем бигӯем, ки суръати алгоритм хеле хуб аст - худатон бубинед: Як миллион элемент дар камтар аз як сония! Ва ин ҷо рамзи Java бо пайдарпаии Knut аст.

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;
            }
        }
    }

Навъи ҳубобӣ. Усули ҳубобӣ

Ин классикӣ аст! Қариб ҳар як барномасози навкор ин алгоритмро амалӣ мекунад. Ин чунон классикист, ки доктор Седгвик барои он ҳатто аниматсия надошт, бинобар ин ман маҷбур шудам, ки ин корро худам иҷро кунам. Дар ин ҷо бинед , дар ҳар як гузариш, мо массивро аз аввал то ба охир мегузарем ва элементҳои ҳамсояи корношоямро иваз мекунем. Дар натиҷа, элементҳои калонтарин то охири массив "шино мекунанд" (аз ин ҷо ном дорад). Мо ҳар як гузаришро бо умеди хушбинона оғоз мекунем, ки массив аллакай мураттаб шудааст ( sorted = true). Дар охири порча агар бинем, ки хато кардаем, порчаи навро сар мекунем. Мушкилот дар ин ҷо дар он аст, ки мо бори дигар (қариб) тамоми массивро дар ҳар як гузариш мегузарем. Муқоиса дар ҳар як қадам сурат мегирад, мубодила тақрибан дар ҳар қадам сурат мегирад, ки ин алгоритмро яке аз сусттаринҳо мекунад (агар мо алгоритмҳои оқилона иҷрошударо ба назар гирем, на "навъҳои ларзиш" ва ғайра). Ҷолиб он аст, ки мураккабии расмӣ дар ин ҷо низ ба O(N^2) баробар хоҳад буд, аммо коэффисиент нисбат ба воридкунӣ ва интихобҳо хеле баландтар аст. Рамзи алгоритм:

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;
        }
    }

Вақти кор: Фарқиятро ҳис кунед: зиёда аз ним соат дар як миллион элемент! Хулоса: Ҳеҷ гоҳ ин алгоритмро истифода набаред!!!

Хулосаи қисми якум

Дар натиҷа, ман тавсия медиҳам, ки ба ҷадвали умумии ин алгоритмҳо назар андозем. Шумо инчунин метавонед бо натиҷаҳои усули дарунсохт муқоиса кунед java.util.Arrays.sort(). Чунин ба назар мерасад, ки як намуди ҷодугарӣ - чӣ метавонад аз Shell тезтар бошад? Ман дар ин бора дар қисми оянда менависам. Дар он ҷо мо алгоритмҳои ба таври васеъ истифодашавандаи ҷудокунии зудро дида мебароем, инчунин навъбандиро якҷоя мекунем, дар бораи фарқияти усулҳои ҷудокунии массивҳо аз ибтидоӣ ва намудҳои истинод маълумот мегирем ва инчунин бо интерфейси хеле муҳим дар ин масъала шинос мешавем Comparable;) Дар зер шумо метавонед онро омӯзед. графике, ки дар миқёси логарифмӣ бо истифода аз ҷадвалҳои маълумот сохта шудааст. Чӣ қадаре ки сатр ҳамвортар бошад, алгоритм ҳамон қадар беҳтар мешавад =) Барои онҳое, ки мехоҳанд тамоми лоиҳаро зеркашӣ кунанд ва мустақилона санҷишҳо гузаронанд, истинодро нигоҳ доред: Java Дар қисми оянда дидан кунед! =)