Алгоритмдерди ачуу же алгоритмдерге оорутпай киришүү

"Grocking Algorithms" китебине обзор. Бир аз жеке пикир, бир нече мисал. Бул карап чыгуу сизге бул китепти окугуңуз келеби же ал сиздин текчеңизден орун алабы же жокпу түшүнүүгө жардам берет деп ишенем. ЭСКЕРТҮҮ: Көптөгөн текст)

"Грокинг алгоритмдери" же Алгоритмдерге оорутпай киришүү

Киришүү

Юниор деңгээлиндеги дээрлик бардык вакансияларда "маалымат структураларын жана алгоритмдерди билүү" сыяктуу талаптар бар. Атайын бorми барлар үчүн алгоритмдер жалпы курска киргизилет жана эч кандай көйгөйлөр болбошу керек. Ал эми өнүгүү башка талаалардан алынып келинсечи? Болгону өз алдынча үйрөнүү гана калды. “Ким күнөөлүү” деген суроого жооп бар, бирок “эмне кылуу керек” деген суроого жооп издөө керек. Келгиле, китептерди карап көрөлү. Жана мен сизге бир нерсени айткым келет.

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ун жазууга аракет кылышкан жок. Бирок Евклид алгоритми жөнөкөй жана натыйжалуу: Чынын айтсам, бул видеодогу сыяктуу китепте кээ бир деталдарды сагындым: “ Информатика. Алгоритмдердин теориясы. Евклиддин алгоритми ». Мисалы, а бдан кичине болсо, анда биринчи чуркоодо b жана а орун алмашат, экинчи жолу чоңу кичинесине бөлүнөт. Ошондуктан, аргументтердин тартиби маанилүү эмес. Адаттагыдай эле, алгач биз алгоритмди кагаз бетинен “сезип” алабыз: Эми codeду карап көрөлү:

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

Келгиле, ошол эле codeду Java тorнде жазалы. Кааласак, биз онлайн компиляторду колдоно алабыз :

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 an object (мисалы, n шаар) болсо, анда биз алардын n санын жасай алабыз! Комбинациялар. Сиз бул жерден рекурсия тууралуу кененирээк окуй аласыз: " Рекурсия. Тренинг тапшырмалары ." Итеративдик жана рекурсивдүү ыкмаларды салыштыруу: « Рекурсия ».

Тез сорттоо

Ыкчам сорттоо - бул абдан кызыктуу алгоритм. Китепте ага көп көңүл бурулbyte. Анын үстүнө, 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деги компьютер orми: 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));

Хеш tableлары

Китепте хэш tableларга да токтолгон. Аны өзүңүз ишке ашыруунун кереги жок, жана хэш tableлардын маңызы абдан жөнөкөй. Анткени, Java да хэш tableларын ишке ашырууга ээ, java.util.HashTable. Эгер биз HashTable аппаратын карасак, анда Entry массивинин ичинде жашап жатканын көрөбүз. Киргизүү ачкыч – Нарктын айкалышы болгон жазуу. HashTable баштапкыCapacity бар, башкача айтканда, баштапкы өлчөмү. Жана loadFactor – жүктөө фактору. Демейки 0,75. Бул сан массивдин кандай жүктөмүндө (элементтердин саны/жалпы саны) өлчөмүн көбөйтүү керектигин айтып турат. Java тorнде ал 2 эсеге көбөйөт. Китепте хэш tableлары хэш tableлары деп аталаары түшүндүрүлөт, анткени хэш-функциянын негизинде массив уячасы (себет) Entry. Сиз дагы бул жерден окуй аласыз: Сүрөттөрдөгү маалымат структуралары. HashMap жана LinkedHashMap . Аны китептерден да окуса болот. Мисалы, бул жерде: " HashTable негиздери "

Графиктер, кеңдик биринчи издөө (эң кыска жол издөө)

Кыязы, эң кызыктуу темалардын бири – графиктер. Бул жерде, калыстык үчүн, китеп аларга көп көңүл бурат. Балким, ошондуктан бул китепти окуу керек. Бирок, балким, аны бир аз ачыкыраак айтса болмок)) Бирок, бизде Интернет бар жана китептен тышкары, сиз бул плейлистти теория боюнча карасаңыз болот " графиктерди биринчи жолу угуп жаткандар . . ” Албетте, китептин эң башында, breadth-first-searchBFS деп да белгилүү болгон биринчи издөө алгоритми берилген. Китепте төмөнкү график бар: Китепте кезек бизге жардам берет деп жазылган. Мындан тышкары, биз элементтерди аягына чейин кошуп, кезекти башынан иштете алабыз. Мындай кезектер эки тараптуу кезек же англисче Deque деп аталат. Китеп маалымат структурасын - хэш tableсын колдонууну сунуштайт. Атын жана кошуналарды салыштыруу. Номерленген чокулары менен сиз жөн гана массивди колдонсоңуз болот. Чокулардын бул сакталышы китепте айтылбаган "Жанашкан чокулардын тизмеси" деп аталат. Бул алар үчүн минус. Муну 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 аздыр-көптүр түшүнгөндүктөн, китептин автору бизди Daystra алгоритмин жана салмактуу графиктерди түшүнүүгө чакырат. Чечим үчүн төмөнкү график сунушталат: Биринчиден, биз графиктерибизди кантип көрсөтүү керектигин түшүнүшүбүз керек. Биз аны матрица катары көрсөтө алабыз. Habré жөнүндө макала бизге бул жерде жардам берет: Dijkstra алгоритми. Графикте оптималдуу маршруттарды табуу . Келгиле, чектеш матрицаны колдонолу:

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 тorнде жазылган. Ошентип, жогоруда келтирилген мисалдардын бардыгы түзүлөт) Бул карап чыгуу сизге китепте эмне бар жана аны сатып алууга татыктуубу жөнүндө түшүнүк алууга жардам берет деп үмүттөнөм.

Кошумча

Ошондой эле бул тема боюнча төмөнкү ресурстарды текшере аласыз:

1. EdX - Java программалоосуна киришүү: Фундаменталдык маалымат структуралары жана алгоритмдер
2. LinkedIn - Java'дагы маалымат структураларына жана алгоритмдерге киришүү (акы төлөнүүчү)
3. Программалоо жөндөмүңүздү өркүндөтүү үчүн пазлдары бар 27 сайт
4. Java CodingBat
5. Программисттер үчүн тапшырмалар, ар кандай татаалдыктагы тапшырмаларга жооптор

#Вячеслав