Алгоритмдерді ашу немесе алгоритмдерге ауыртпалықсыз кіріспе

«Грокинг алгоритмдері» кітабына шолу. Кішкене жеке пікір, бірнеше мысал. Бұл шолу сізге осы кітапты оқығыңыз келе ме, әлде ол сіздің сөреңізден орын алмайтынын түсінуге көмектеседі деп үміттенемін. ЕСКЕРТУ: көп мәтін)

«Грокинг алгоритмдері» немесе алгоритмдерге ауыртпалықсыз кіріспе

Кіріспе

Кіші деңгейдегі кез келген дерлік бос орынға «деректер құрылымдары мен алгоритмдерін білу» сияқты талаптар қойылады. Арнайы білімі барлар үшін алгоритмдер жалпы курсқа енгізілген және ешқандай проблемалар болмауы керек. Ал егер игеру басқа далалардан әкелінсе ше? Өз бетінше үйрену ғана қалады. «Кім кінәлі» деген сұраққа жауап бар, бірақ «не істеу керек» деген сұраққа жауап іздеу керек. Кітаптарға қарайық. Ал мен сізге бір туралы айтқым келеді.

Grok алгоритмдері

Барлық жұмыстардың ішінде мен «Grocking Algorithms» сияқты кітапты кездестірдім. Қосымша ақпаратты мына жерден таба аласыз: « «Өсу алгоритмдері. Бағдарламашылар мен қызығушылық танытқандарға арналған иллюстрациялық нұсқаулық» кітабы . Мен кітапты бұрыннан байқадым, бірақ озон бойынша ол 680 рубль болды. Қымбат немесе арзан - әркім өзі шешеді. Мен Avito туралы екінші кітапты жарты бағаға сатып алып жатырмын. Сондықтан мен оны Санкт-Петербургтен тауып алып, сатып алдым да, қыдырдым. Міне, мен сіздермен бөлісуді жөн көрдім. Иә, кітапта Java codeы жоқ, бірақ... басқа code бар, бірақ бұл туралы кейінірек.

Алгоритмдерге кіріспе (таңдауды сұрыптау)

Сонымен, баяндаудың жеңіл түрінде біз орындауымызда бірінші сұрыптауға жетеміз. Бұл таңдау сұрыптауы. Оның мәні мынада: біз элементтерді солдан оңға қарай (0 элементтен соңғысына дейін) өтіп, қалған элементтердің ішінен ең үлкенін іздейміз. Егер біз оны тапсақ, онда біз қазір тұрған элемент пен ең үлкен элементті ауыстырамыз. Алдымен массив туралы ойлаудың ең қарапайым жолы: [5, 3, 6, 2, 10]. Қағаз парағын, қаламды (ең қарапайым және ең арзан әдіс) алыңыз және бізде сол жақтағы шекара (сол жақта), ағымдағы индекс (немесе оң жақта) бар екенін елестетіп көріңіз, минималды элементтің индексі бар. Және біз онымен қалай жұмыс істейміз. Мысалы: Алгоритмдер көбінесе псевдоcodeта сипатталады, мысалы, Уикипедияда. Біздікі дәл псевдоcode емес, бірақ бұл туралы кейінірек. Әзірге көрейік:

def selectionSort(array):
    for left in range(0, len(array)):
        minIndex = left
        for right in range (left+1, len(array)):
            if array[right] < array[minIndex]:
                minIndex = right
        if minIndex != left:
            temp = array[left]
            array[left] = array[minIndex]
            array[minIndex] = temp
    return array

print(selectionSort([5, 3, 6, 2, 10]))

Енді оны Java codeы түрінде көрсетейік:

public static void selectionSort(int[] array) {
        for (int left = 0; left < array.length; left++) {
            int minIndex = left;
            for (int right = left+1; right < array.length; right++) {
                if (array[right] < array[minIndex]) {
                    minIndex = right;
                }
            }
            if (minIndex != left) {
                int temp = array[left];
                array[left] = array[minIndex];
                array[minIndex] = temp;
            }
        }
}

Көріп отырғаныңыздай, code бірдей дерлік. Бірінші code - кітаптан алынған мысал. Екіншісі - менің Java codeындағы тегін орындауым.

Рекурсия

Бұдан кейін бізге рекурсия сияқты нәрсе бар екендігі айтылады. Ең алдымен, AxB көлеміндегі егістік алқабы бар шаруаға қатысты мәселе. Бұл өрісті тең «шаршыға» бөлу керек. Осыдан кейін Евклид алгоритмі айтылады. Маған ұнамайтыны – оның codeын жазуға тырыспағаны. Бірақ Евклид алгоритмі қарапайым және тиімді: Шынымды айтсам, мен кітаптағы кейбір мәліметтерді жіберіп алдым, мысалы, осы бейнеде: « Информатика. Алгоритм теориясы. Евклид алгоритмі ». Мысалы, егер a b-дан кіші болса, онда бірінші жүгіру кезінде b және a орындарын ауыстырады, ал екінші рет үлкені кішіге бөлінеді. Сондықтан аргументтердің реті маңызды емес. Әдеттегідей, алдымен қағаз парағында алгоритмді «сезуге» болады: Енді codeты қарастырайық:

def euclidean(a, b):
    if a == 0 : return b
    if b == 0 : return a
    return euclidean (b, a % b)

Сол codeты Java тілінде жазайық. Қаласаңыз, біз онлайн компиляторды пайдалана аламыз :

public static int euclid(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        return euclid(b, a%b);
}

Кітаптың басында факториалды да атап өтті. n (n!) санының факториалы 1-ден n-ге дейінгі сандардың көбейтіндісі болып табылады. Неліктен мұны істеу керек? Мұнда бір практикалық қолдану бар. Егер бізде n нысан болса (мысалы, n қала), онда біз олардың n-ін жасай аламыз! Комбинациялар. Рекурсия туралы толығырақ мына жерден оқи аласыз: " Рекурсия. Тренинг тапсырмалары ." Итеративті және рекурсивті тәсілдерді салыстыру: « Рекурсия ».

Жылдам сұрыптау

Жылдам сұрыптау - бұл өте қызықты алгоритм. Кітап оған көп көңіл бөлмейді. Оның үстіне, code бірінші элемент таңдалғанда ең нашар жағдайда ғана беріледі. Дегенмен, бірінші танысу үшін бұл мысалды есте сақтау оңайырақ болуы мүмкін. Мүлдем жазбағанша, жылдам сұрыптаудың нашар түрін жазған дұрыс. Міне, кітаптан мысал:

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

Мұнда бәрі өте қарапайым. Егер бізде 0 немесе 1 элемент массиві болса, оны сұрыптаудың қажеті жоқ. Егер ол үлкен болса, массивтің бірінші элементін алып, оны «бұрылғы элемент» деп санаймыз. Біз 2 жаңа массив жасаймыз - біреуінде бұрылыстан үлкенірек элементтер бар, ал екіншісінде кішірек элементтер бар. Және біз рекурсивті қайталаймыз. Ең жақсы нұсқа емес, бірақ тағы да жақсы есте қалды. Бұл алгоритмді Java тілінде жүзеге асырайық, бірақ дұрысырақ. Бұл бізге « JavaScript-тағы компьютерлік ғылым: Quicksort » шолуындағы материал көмектеседі . Ал, codeты жазбас бұрын, алгоритмді «сезіну» үшін қайтадан сурет салайық: Алдымен, алгоритмді түсіну үшін қағаз бетіне қайтадан сызып алайық: Менің ойымша, ең қауіпті сәттердің бірі - мәселелерді толығымен шешу. Сондықтан біз іске асыруды бірнеше шағын қадамдармен жүзеге асырамыз:

• Біз массивтегі элементтерді ауыстыра алуымыз керек:

  private static void swap(int[] array, int firstIndex, int secondIndex) {
          int temp = array[firstIndex];
          array[firstIndex] = array[secondIndex];
          array[secondIndex] = temp;
  }




• Көрсетілген интервалдағы массивті 3 бөлікке бөлетін әдіс қажет

  
  

  private static int partition(int[] array, int left, int right) {
          int pivot = array[(right + left) / 2];
          while (left <= right) {
              while (array[left] < pivot) {
                  left++;
              }
              while (array[right] > pivot) {
                  right--;
              }
              if (left <= right) {
                  swap(array, left, right);
                  left++;
                  right--;
              }
          }
          return left;
  }

  Толық ақпарат жоғарыдағы сілтемеде. Қысқаша айтқанда, сол жақ курсорды элемент айналудан аз болғанша жылжытамыз. Сол сияқты, оң жақ курсорды екінші жағынан жылжытыңыз. Ал курсорлар сәйкес келмесе, айырбас жасаймыз. Курсорлар жақындағанша жалғастырамыз. Біз одан әрі өңдеуді 2 бөлікке бөлетін индексті қайтарамыз.

• Бөлу бар, бізге сұрыптаудың өзі қажет:

  public static void quickSort(int[] array, int left, int right) {
          int index = 0;
          if (array.length > 1) {
              index = partition(array, left, right);
              if (left < index - 1) {
                  quickSort(array, left, index - 1);
              }
              if (index < right) {
                  quickSort(array, index, right);
              }
          }
  }

  Яғни, массив кем дегенде екі элементтен тұратын болса, онда оларды сұрыптауға болады. Біріншіден, біз бүкіл массивді екі бөлікке бөлеміз, элементтерді бұрылыстан кішірек және үлкенірек элементтер. Содан кейін алынған бөліктердің әрқайсысы үшін ұқсас әрекеттерді орындаймыз.

  Ал сынақ үшін:

  public static void main(String []args){
          int[] array = {8,9,3,7,6,7,1};
          quickSort(array, 0, array.length-1);
          System.out.println(Arrays.toString(array));
  }

Кітапта бұл алгоритм өңделген деректер жинағы әр уақытта екіге бөлінген кезде «Бөл және жең» деп аталатын алгоритмдерге жататынын айтады. Алгоритм күрделілігі: O(nLogn) Ең жаманы (яғни маған ұнамағаны) кітапта біріктіру сұрыптауы туралы айтылған, бірақ ешқандай мысал немесе code ұсынбайды. Толық ақпаратты мына жерден табуға болады: " Информатика. Іздеу және сұрыптау алгоритмдері: Біріктіру сұрыптау ". Сондықтан, жүйелілік үшін өзіміз жасайық. Алгоритмнің өзі, әрине, қарапайым және қарапайым:

public static void mergeSort(int[] source, int left, int right) {
    if ((right - left) > 1) {
        int middle = (right + left) / 2;
        mergeSort(source, left, middle);
        mergeSort(source, middle + 1, right);
    }
    merge(source, left, right);
}

Ортасын анықтап, массивті екіге бөлеміз. Әрбір жартысы үшін біз бірдей жасаймыз және т.б. Тоқтату шарты немесе негізгі жағдай - бізде бірден көп элемент болуы керек, өйткені біз бір элементті екіге бөле алмаймыз. Енді біріктіруді жүзеге асыруымыз керек, яғни біріктіру:

public static void merge(int[] array, int from, int to) {
    int middle = ((from + to) / 2) + 1;
    int left = from;
    int right = middle;
    int cursor = 0;

    int[] tmp = new int[to - from + 1];
    while (left < middle || right <= to) {
        if (left >= middle) {
            tmp[cursor] = array[right];
            System.out.println("Остаток справа: " + array[right]);
            right++;
        } else if (right > to) {
            tmp[cursor] = array[left];
            System.out.println("Остаток слева: " + array[left]);
            left++;
        } else if (array[left] <= array[right]) {
            tmp[cursor] = array[left];
            System.out.println("Слева меньше: " + array[left]);
            left++;
        } else if (array[right] < array[left]) {
            tmp[cursor] = array[right];
            System.out.println("Справа меньше: " + array[right]);
            right++;
        }
        cursor++;
    }
    System.arraycopy(tmp, 0, array, from, tmp.length);
}

Бұл жерде түсініктеме беретін көп нәрсе жоқ. Айнымалылардың атауларынан printlnбәрі түсінікті. Ал, тексеру үшін:

int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));

Хэш кестелері

Кітап хэш-кестелерге де қатысты. Оны өзіңіз орындаудың қажеті жоқ, ал хэш кестелерінің мәні өте қарапайым. Өйткені, Java-да java.util.HashTable хэш кестелерін іске асыру бар. Егер біз HashTable құрылғысына қарасақ, Entry массиві ішінде тұратынын көреміз. Жазба – Key – Value тіркесімі болып табылатын жазба. HashTable-де initialCapacity бар, яғни бастапқы өлшем. Ал loadFactor – жүктеме коэффициенті. Әдепкі – 0,75. Бұл сан массивтің қандай жүктемесінде (элементтер саны/жалпы сан) өлшемді ұлғайту керектігін көрсетеді. Java тілінде ол 2 есе артады. Кітап хэш кестелері хэш-кестелер деп аталатынын түсіндіреді, себебі хэш функциясына негізделген жиым ұяшығы (себет) Entry. Толығырақ мына жерден оқи аласыз: Суреттердегі деректер құрылымдары. HashMap және LinkedHashMap . Оны кітаптардан да оқуға болады. Мысалы, мұнда: " HashTable негіздері "

Графиктер, кеңдік бірінші іздеу (ең қысқа жолды іздеу)

Ең қызықты тақырыптардың бірі - графиктер. Ал бұл жерде, әділдік үшін, кітап оларға көп көңіл бөледі. Мүмкін сондықтан да бұл кітапты оқу керек шығар. Дегенмен, бәлкім, оны біршама анық айту мүмкін еді)) Бірақ, бізде Интернет бар және кітапқа қосымша, сіз бұл ойнату тізімін теория бойынша «графтар туралы бірінші рет естігендерге» қарай аласыз . » Әрине, кітаптың ең басында breadth-first-searchBFS деп те аталатын бірінші іздеу алгоритмі берілген. Кітапта келесі график бар: Кітапта кезек бізге көмектесетіні айтылған. Сонымен қатар, біз соңына элементтерді қосып, кезекті басынан өңдей аламыз. Мұндай кезектер екі жақты кезек немесе ағылшын тілінде Deque деп аталады. Кітап деректер құрылымын – хэш кестесін пайдалануды ұсынады. Атау мен көршілерді салыстыру. Нөмірленген шыңдар арқылы сіз жай ғана массивді пайдалана аласыз. Бұл төбелерді сақтау кітапта айтылмаған «Көршілес шыңдар тізімі» деп аталады. Бұл олар үшін минус. Мұны Java-да іске асырайық:

private Map<String, String[]> getGraph() {
    Map<String, String[]> map = new HashMap<>();
    map.put("you", new String[]{"alice", "bob", "claire"});
    map.put("bob", new String[]{"anuj", "peggy"});
    map.put("alice", new String[]{"peggy"});
    map.put("claire", new String[]{"thom", "jonny"});
    map.put("annuj", null);
    map.put("peggy", null);
    map.put("thom", null);
    map.put("johny", null);
    return map;
}

Енді осы деректерге негізделген іздеудің өзі:

private String search() {
    Map<String, String[]> graph = getGraph();
    Set<String> searched = new HashSet<>();
    Deque<String> searchQue = new ArrayDeque<>();
    searchQue.add("you");
    while (!searchQue.isEmpty()) {
        String person = searchQue.pollFirst();
        System.out.println(person);
        if (personIsSeller(person)) {
            return person;
        } else {
            String[] friends = graph.get(person);
            if (friends == null) continue;
            for (String friend : friends) {
                if (friend != null && !searched.contains(friend)) {
                    searchQue.addLast(friend);
                }
            }
        }
    }
    return null;
}

Көріп отырғаныңыздай, күрделі ештеңе жоқ. Егер сіз оны кітаптағы codeпен салыстырсаңыз, ол бірдей.

Графиктер, Дейкстра алгоритмі

BFS-ті азды-көпті түсінгендіктен, кітап авторы бізді Daysktra алгоритмі мен өлшенген графиктерді түсінуге шақырады. Шешім үшін келесі график ұсынылады: Біріншіден, біз графиктерді қалай көрсету керектігін түсінуіміз керек. Біз оны матрица ретінде көрсете аламыз. Хабре туралы мақала бізге мына жерде көмектеседі: Дийкстра алгоритмі. График бойынша оңтайлы жолдарды табу . Көршілестік матрицасын қолданайық:

public Integer[][] getGraphMatrix(int size) {
    Integer[][] matrix = new Integer[size][size];
    matrix[0][1] = 6;
    matrix[0][2] = 2;
    matrix[2][1] = 3;
    matrix[1][3] = 1;
    matrix[2][3] = 5;
    return matrix;
}

Ал енді логиканың өзі:

@Test
public void dijkstra() {
    Integer[][] graph = getGraphMatrix();           // Данные графа
    Integer[] costs = new Integer[graph.length];    // Стоимость перехода
    Integer[] parents = new Integer[graph.length];  // Родительский узел
    BitSet visited = new BitSet(graph.length);      // "Ферма" маркеров посещённости

    Integer w = 0;
    do {
        System.out.println("-> Рассматриваем вершину: " + w);
        Integer min = null;
        for (int i = 0; i < graph.length; i++) {    // Обрабатываем каждую дугу
            if (graph[w][i] == null) continue;      // Дуги нет - идём дальше
            if (min == null || (!visited.get(i) && graph[w][min] > graph[w][i])) {
                min = i;
            }
            if (costs[i] == null || costs[i] > costs[w] + graph[w][i]) {
                System.out.print("Меням вес с " + costs[i]);
                costs[i] = (costs[w] != null ? costs[w] : 0) + graph[w][i];
                System.out.println(" на " + costs[i] + " для вершины " + i);
                parents[i] = w;
            }
        }
        System.out.println("Вершина с минимальным весом: " + min);
        visited.set(w);
        w = min;
    } while (w != null);

    System.out.println(Arrays.toString(costs));
    printPath(parents, 3);
}

public void printPath(Integer[] parents, int target) {
    Integer parent = target;
    do {
        System.out.print(parent + " <- ");
        parent = parents[parent];
    } while (parent != null);
}

Кітап оны біртіндеп бөлшектейді. Интернетте Habré туралы мақала қоссаңыз + codeты қараңыз, оны есте сақтай аласыз. Мен қадамдық талдауды біраз ретсіз деп таптым. Бірақ қадамдық табиғаттың өзі үшін бұл плюс. Жалпы, жақсы, бірақ жақсырақ болуы мүмкін еді)

Ашкөз алгоритмдер

Келесі бөлім «ашкөз алгоритмдерге» арналған. Бұл бөлім қызықты, себебі ол жиындарды (java.util.Set) пайдаланады. Соңында біз оның не үшін қажет болуы мүмкін екенін көреміз. Кіріс ретінде күйлер тізімін қолданамыз:

Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));

Сондай-ақ осы мемлекеттердің кейбірін қамтитын радиостанциялардың тізімі:

Map<String, Set<String>> stations = new HashMap<>();
stations.put("kone", new HashSet(Arrays.asList("id", "nv", "ut")));
stations.put("ktwo", new HashSet(Arrays.asList("wa", "id", "mt")));
stations.put("kthree", new HashSet(Arrays.asList("or", "nv", "ca")));
stations.put("kfour", new HashSet(Arrays.asList("nv", "ut")));
stations.put("kfive", new HashSet(Arrays.asList("ca", "az")));

Кітап алгоритмнің өзін көрсетеді және түсіндіреді:

Set<String> finalStations = new HashSet();
while (!statesNeeded.isEmpty()) {
    String bestStation = null;
    Set<String> statesCovered = new HashSet();
    for (String station: stations.keySet()) {
        Set covered = new HashSet(statesNeeded);
        covered.retainAll(stations.get(station));
        if (covered.size() > statesCovered.size()) {
           bestStation = station;
           statesCovered = covered;
        }
    }
    statesNeeded.removeAll(statesCovered);
    finalStations.add(bestStation);
}
System.out.println(finalStations);

Динамикалық бағдарламалау

Кітап сонымен қатар «динамикалық бағдарламалау» деп аталатын тәсіл қолданылатын проблемаларды сипаттайды. Тапсырма беріледі: Бізде 4 фунт сөмке бар. Берілген салмақ үшін ең тиімді заттарды табу керек. Алдымен элементтердің тізімін жасайық:

List<Thing> things = new ArrayList<>();
things.add(new Thing("guitar", 1, 1500));
things.add(new Thing("tape recorder", 4, 3000));
things.add(new Thing("notebook", 3, 2000));

Енді алгоритмнің өзі:

int bagSize = 4;
int cell[][] = new int[things.size()][bagSize];
// Заполняем первую строку без условий
for (int i = 0; i < bagSize; i++) {
    cell[0][i] = things.get(0).cost;
}
// Заполняем оставшиеся
for (int i = 1; i < cell.length; i++) {
    for (int j = 0; j < cell[i].length; j++) {
        // Если вещь не влезает - берём прошлый максимум
        if (things.get(i).weight > j+1) {
            cell[i][j] = cell[i - 1][j];
        } else {
            // Иначе текущая стоимость + предыдущий максимум оставшегося размера
            cell[i][j] = things.get(i).cost;
            if (j + 1 - things.get(i).weight > 0) {
                cell[i][j] += cell[i-1][j + 1 - things.get(i).weight];
            }
        }
    }
}
System.out.println(Arrays.deepToString(cell));

Ең ұқсас сөздерді табу үшін де қызықты тапсырма бар. Қызық, солай емес пе? Қосымша мәліметтер мына жерде: LongestCommonSubsequence.java

Жақын көршілерді іздеңіз

Кітапта сонымен қатар k-ең жақын көршілер алгоритмі туралы өте анық айтылады: Ал есептеу формуласы берілген:

Төменгі сызық

Кітап қызықты алгоритмдерді жылдам шолуды қамтамасыз ететін қызықты «Келесі не?» бөлімімен аяқталады. Мұнда ағаштар мен басқа алгоритмдердің мағынасының қысқаша сипаттамасы берілген. Жалпы, маған кітап ұнады. Оны жан-жақты ақпарат ретінде қабылдауға болмайды. Сіз өзіңіз іздеп, түсінуіңіз керек. Бірақ қызықтыратын және бастапқы идея беретін кіріспе ақпарат ретінде бұл өте жақсы. Иә, кітаптағы code Python тілінде жазылған. Сондықтан жоғарыда келтірілген мысалдардың барлығы жинақталады) Бұл шолу сізге кітапта не бар екенін және оны сатып алуға тұрарлық екенін білуге ​​​​көмектеседі деп үміттенемін.

Қосымша

Сондай-ақ осы тақырып бойынша келесі ресурстарды тексеруге болады:

1. EdX - Java бағдарламалауға кіріспе: деректердің негізгі құрылымдары мен алгоритмдері
2. LinkedIn - Java тіліндегі деректер құрылымдары мен алгоритмдеріне кіріспе (ақылы)
3. Бағдарламалау дағдыларын шыңдау үшін басқатырғыштары бар 27 сайт
4. Java CodingBat
5. Бағдарламашыларға арналған тапсырмалар, әртүрлі күрделіліктегі тапсырмаларға жауаптар

#Вячеслав