"Growing Algorithms" o isang Walang Sakit na Panimula sa Algorithms
Panimula
Halos anumang bakante sa antas ng Junior ay may mga kinakailangan tulad ng "kaalaman sa mga istruktura at algorithm ng data." Para sa mga may espesyal na edukasyon, ang mga algorithm ay kasama sa pangkalahatang kurso at dapat walang mga problema. Ngunit paano kung ang pag-unlad ay dinala mula sa iba pang mga steppes? Ang natitira na lang ay matuto nang mag-isa. May sagot sa tanong na "sino ang dapat sisihin", ngunit sa tanong na "ano ang gagawin" ang sagot ay dapat hanapin. Tingnan natin sa mga libro. At gusto kong sabihin sa iyo ang tungkol sa isa.Mga algorithm ng Grok
Sa lahat ng mga gawa, nakita ko ang isang libro tulad ng "Grocking Algorithms". Maaari mong malaman ang higit pa dito: " Ang aklat na "Growing Algorithms. Isang may larawang gabay para sa mga programmer at mga mausisa ." Napansin ko ang libro ng matagal na ang nakalipas, ngunit sa ozone nagkakahalaga ito ng 680 rubles. Mahal o mura - lahat ay nagpapasya para sa kanyang sarili. Bumibili na ako ng pangalawang libro sa Avito sa kalahati ng presyo. Kaya natagpuan ko ito sa St. Petersburg, binili ko ito, at nag-grokking. Na kung ano ang napagpasyahan kong ibahagi sa iyo. Oo, walang Java code sa aklat, ngunit mayroong... ibang code, ngunit higit pa tungkol doon sa ibang pagkakataon.Panimula sa Algorithms (Selection Sort)
Kaya, sa isang madaling paraan ng pagsasalaysay, naabot namin ang unang pag-uuri sa aming pagganap. Ito ay Selection Sort. Ang kakanyahan nito ay dumaan tayo sa mga elemento mula kaliwa hanggang kanan (mula 0 elemento hanggang sa huli), at hanapin ang pinakamalaki sa mga natitirang elemento. Kung nahanap natin ito, pagkatapos ay pinapalitan natin ang elemento kung saan tayo ngayon at ang pinakamalaking elemento. Ang pinakasimpleng paraan para mag-isip muna ng array ay: [5, 3, 6, 2, 10]. Kumuha ng isang piraso ng papel, isang panulat (ang pinakasimpleng at pinakamurang paraan) at isipin kung paano tayo may kaliwang hangganan (kaliwa), isang kasalukuyang index (o kanang hangganan), mayroong isang index ng pinakamababang elemento. At kung paano namin ito ginagawa. Halimbawa:
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]))
Ngayon, ipakita natin ito sa anyo ng 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;
}
}
}
Tulad ng nakikita mo, ang code ay halos pareho. Ang unang code ay isang halimbawa mula sa aklat. Ang pangalawa ay ang aking libreng pagpapatupad sa Java code.
Recursion
Susunod na sinabi sa amin na mayroong isang bagay tulad ng recursion. Una sa lahat, may problema tungkol sa isang magsasaka na may larangan ng laki ng AxB. Kinakailangan na hatiin ang patlang na ito sa pantay na "mga parisukat". At pagkatapos nito ay binanggit ang Euclid Algorithm. Ang hindi ko gusto ay hindi nila sinubukang isulat ang code nito. Ngunit ang Euclid algorithm ay simple at epektibo:
def euclidean(a, b):
if a == 0 : return b
if b == 0 : return a
return euclidean (b, a % b)
Isulat natin ang parehong code sa Java. Kung nais, maaari naming gamitin ang online compiler :
public static int euclid(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
return euclid(b, a%b);
}
Nabanggit din ang factorial sa simula ng libro. Ang factorial ng isang numero n (n!) ay ang produkto ng mga numero mula 1 hanggang n. Bakit gagawin ito? Mayroong isang praktikal na aplikasyon dito. Kung mayroon tayong n mga bagay (halimbawa, n mga lungsod), maaari tayong gumawa ng n sa kanila! Mga kumbinasyon. Maaari kang magbasa ng higit pa tungkol sa recursion dito: " Recursion. Mga gawain sa pagsasanay ." Paghahambing ng umuulit at recursive approach: " Recursion ".
Mabilis na pag-uuri
Ang mabilis na pag-uuri ay isang medyo kawili-wiling algorithm. Hindi siya masyadong pinapansin ng libro. Bukod dito, ibinibigay lamang ang code para sa pinakamasamang kaso, kapag napili ang unang elemento. Gayunpaman, marahil para sa isang unang kakilala ang halimbawang ito ay mas madaling matandaan. At mas mainam na magsulat ng isang masamang quicksort kaysa hindi magsulat ng isa. Narito ang isang halimbawa mula sa aklat:
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)
Lahat dito ay sobrang simple. Kung mayroon kaming isang array ng 0 o 1 elemento, hindi na kailangang ayusin ito. Kung ito ay mas malaki, kukunin namin ang unang elemento ng array at isaalang-alang itong "pivot element". Gumagawa kami ng 2 bagong array - ang isa ay naglalaman ng mga elementong mas malaki kaysa sa pivot, at ang pangalawa ay naglalaman ng mga elementong mas maliit. At inuulit namin nang paulit-ulit. Hindi ang pinakamahusay na pagpipilian, ngunit muli, mas mahusay na maalala. Ipatupad natin ang algorithm na ito sa Java, ngunit mas tama. Ang materyal mula sa pagsusuri na " Computer Science sa JavaScript: Quicksort " ay makakatulong sa amin dito . At bago isulat ang code, gumuhit tayo muli upang "maramdaman" ang algorithm: Una, gumuhit tayo muli sa isang piraso ng papel upang maunawaan ang algorithm:
-
Kailangan nating makapagpalit ng mga elemento sa isang array:
private static void swap(int[] array, int firstIndex, int secondIndex) { int temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp; }
-
Kailangan namin ng isang paraan na naghahati sa array sa tinukoy na agwat sa 3 bahagi
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; }
Mga detalye sa link sa itaas. Sa madaling salita, inililipat namin ang kaliwang cursor hanggang ang elemento ay mas mababa sa pivot. Katulad nito, ilipat ang kanang cursor mula sa kabilang dulo. At gagawa kami ng swap kung hindi magkatugma ang mga cursor. Nagpapatuloy kami hanggang sa magtagpo ang mga cursor. Nagbabalik kami ng index na naghahati sa karagdagang pagproseso sa 2 bahagi.
-
Mayroong isang paghihiwalay, kailangan namin ang pag-uuri mismo:
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); } } }
Iyon ay, kung ang array ay binubuo ng hindi bababa sa dalawang elemento, maaari na silang ayusin. Una, hinati namin ang buong array sa dalawang bahagi, mga elementong mas maliit kaysa sa pivot at mga elementong mas malaki. Pagkatapos ay nagsasagawa kami ng mga katulad na pagkilos para sa bawat isa sa mga resultang bahagi.
At para sa pagsubok:
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)); }
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);
}
Tinutukoy namin ang gitna at hatiin ang array sa kalahati. Para sa bawat kalahati ginagawa namin ang parehong at iba pa. Paghinto ng kundisyon o base case - dapat ay mayroon tayong higit sa isang elemento, dahil hindi natin mahahati ang isang elemento sa dalawa. Ngayon kailangan nating ipatupad ang pagsasama, iyon ay, pagsamahin:
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);
}
Walang gaanong maikomento dito. Mula sa mga pangalan ng mga variable println
ang lahat ay malinaw. Well, upang suriin:
int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
Hash table
Hinahawakan din ng libro ang mga hash table. Hindi mo kailangang ipatupad ito sa iyong sarili, at ang kakanyahan ng mga hash table ay medyo simple. Pagkatapos ng lahat, ang Java ay mayroon ding pagpapatupad ng mga hash table, java.util.HashTable. Kung titingnan natin ang HashTable device, makikita natin na ang Entry array ay nabubuhay sa loob. Ang entry ay isang talaan na kumbinasyon ng Key – Value. Ang HashTable ay may initialCapacity - iyon ay, ang paunang laki. At loadFactor – load factor. Ang default ay 0.75. Sinasabi sa iyo ng numerong ito kung anong load ng array (bilang ng mga elemento/kabuuang dami) ang kailangang dagdagan. Sa Java ito ay tumataas ng 2 beses. Ipinapaliwanag ng aklat na ang mga Hash table ay tinatawag na hash table dahil batay sa hash function, ang array cell (basket) kung saan angEntry
. Maaari ka ring magbasa ng higit pa dito: Mga istruktura ng data sa mga larawan. HashMap at LinkedHashMap . Mababasa mo rin ito sa mga libro. Halimbawa dito: " Mga pangunahing kaalaman sa HashTable "
Mga Graph, Breadth First Search (pinakamaikling paghahanap ng landas)
Marahil ang isa sa mga pinakakawili-wiling paksa ay ang mga graph. At dito, upang maging patas, ang libro ay nagbabayad ng maraming pansin sa kanila. Siguro kaya sulit na basahin ang librong ito. Bagaman, marahil, ito ay maaaring nasabi nang mas malinaw ng kaunti)) Ngunit, mayroon kaming Internet at bilang karagdagan sa aklat, maaari mong tingnan ang playlist na ito sa teorya para sa "mga taong nakakarinig tungkol sa mga graph sa unang pagkakataon . ” Well, natural, sa pinakadulo simula ng libro, ang breadth-first search algorithm,breadth-first-search
na kilala rin bilang BFS, ay ibinibigay. Ang aklat ay naglalaman ng sumusunod na graph:
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;
}
Ngayon ang paghahanap mismo, na binuo sa data na ito:
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;
}
Tulad ng nakikita mo, walang kumplikado. Kung ihahambing mo ito sa code mula sa aklat, halos pareho ito.
Mga Graph, Algorithm ni Dijkstra
Sa pagkakaroon ng higit pa o hindi gaanong naiintindihan ang BFS, iniimbitahan kami ng may-akda ng aklat na maunawaan ang algorithm ng Daysktra at mga weighted graph. Ang sumusunod na graph ay iminungkahi para sa solusyon: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;
}
At ngayon ang lohika mismo:
@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);
}
Ibinahagi ito ng libro nang sunud-sunod. Kung nagdagdag ka ng artikulo sa Habré sa Internet + tingnan ang code, maaalala mo ito. Nakita kong medyo kalat ang step-by-step analysis. Ngunit para sa step-by-step na kalikasan mismo ito ay isang plus. Sa pangkalahatan, ok, kahit na ito ay maaaring mas mahusay)
Mga sakim na algorithm
Ang susunod na seksyon ay nakatuon sa "matakaw na mga algorithm". Ang seksyong ito ay kawili-wili dahil gumagamit ito ng mga set (java.util.Set). Sa wakas makikita natin kung bakit maaaring kailanganin ito. Gumagamit kami ng listahan ng mga estado bilang input:Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));
At isang listahan din ng mga istasyon ng radyo na sumasaklaw sa ilan sa mga estadong ito:
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")));
Ang libro ay nagpatuloy upang ituro at ipaliwanag ang algorithm mismo:
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);
Dynamic na programming
Inilalarawan din ng aklat ang mga problema kung saan inilalapat ang isang diskarte na tinatawag na "dynamic programming". Ang gawain ay ibinigay: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));
Ngayon ang algorithm mismo:
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));
Mayroon ding isang kawili-wiling gawain upang mahanap ang pinakakatulad na mga salita. Kawili-wili, hindi ba? Higit pang mga detalye dito: LongestCommonSubsequence.java
Maghanap ng mga pinakamalapit na kapitbahay
Malinaw ding pinag-uusapan ng aklat ang tungkol sa algorithm ng k-pinakamalapit na mga kapitbahay:Bottom line
Nagtatapos ang aklat sa isang kawili-wiling seksyong "Ano ang Susunod?", na nagbibigay ng mabilis na pangkalahatang-ideya ng mga kawili-wiling algorithm. Narito ang isang maikling paglalarawan ng kung ano ang kahulugan ng mga puno at iba pang mga algorithm. Sa pangkalahatan, nagustuhan ko ang libro. Hindi ito dapat seryosohin bilang isang uri ng komprehensibong impormasyon. Kailangan mong maghanap at maunawaan para sa iyong sarili. Ngunit bilang panimulang impormasyon sa interes at nagbibigay ng paunang ideya, ito ay medyo maganda. Oo, ang code sa libro ay nakasulat sa Python. Kaya lahat ng mga halimbawa sa itaas ay compilable) Umaasa ako na ang pagsusuri na ito ay makakatulong sa iyo na magkaroon ng ideya kung ano ang nilalaman ng libro at kung ito ay nagkakahalaga ng pagbili.Bukod pa rito
Maaari mo ring tingnan ang mga sumusunod na mapagkukunan sa paksang ito:- EdX - Panimula sa Java Programming: Mga Pangunahing Istruktura ng Data at Algorithm
- LinkedIn - Panimula sa Mga Structure ng Data at Algorithm sa Java (bayad)
- 27 mga site na may mga puzzle upang patalasin ang iyong mga kasanayan sa programming
- Java CodingBat
- Mga gawain para sa mga programmer, mga sagot sa mga gawain na may iba't ibang kumplikado
GO TO FULL VERSION