"Algoritmi in crescita" o un'introduzione indolore agli algoritmi
introduzione
Quasi tutti i posti vacanti di livello Junior hanno requisiti come "conoscenza di strutture dati e algoritmi". Per chi ha una formazione specialistica gli algoritmi sono inclusi nel corso generale e non dovrebbero esserci problemi. Ma cosa accadrebbe se lo sviluppo provenisse da altre steppe? Non resta che imparare da solo. Alla domanda “di chi è la colpa” c’è una risposta, ma alla domanda “cosa fare” la risposta va cercata. Diamo un'occhiata ai libri. E voglio parlarvene di uno.Algoritmi di Grok
Tra tutti i lavori, mi sono imbattuto in un libro come "Grocking Algorithms". Puoi saperne di più qui: " Il libro "Algoritmi in crescita. Una guida illustrata per programmatori e curiosi ". Ho notato il libro molto tempo fa, ma con l'ozono costava 680 rubli. Costoso o economico: ognuno decide da solo. Sto già acquistando il secondo libro su Avito a metà prezzo. Così l'ho trovato a San Pietroburgo, l'ho comprato e sono andato a grokkare. Questo è ciò che ho deciso di condividere con te. Sì, nel libro non c'è il codice Java, ma c'è... altro codice, ma ne parleremo più avanti.Introduzione agli algoritmi (ordinamento di selezione)
Quindi, in una forma facile di narrazione, raggiungiamo il primo ordinamento della nostra performance. Questo è l'ordinamento della selezione. La sua essenza è che esaminiamo gli elementi da sinistra a destra (dall'elemento 0 all'ultimo) e cerchiamo il più grande tra gli elementi rimanenti. Se lo troviamo, scambiamo l'elemento su cui ci troviamo ora con l'elemento più grande. Il modo più semplice per pensare innanzitutto a un array è: [5, 3, 6, 2, 10]. Prendiamo un pezzo di carta, una penna (il modo più semplice ed economico) e immagina come abbiamo un bordo sinistro (sinistra), un indice corrente (o bordo destro), c'è un indice dell'elemento minimo. E come lo utilizziamo. Per esempio:
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]))
Ora presentiamolo sotto forma di codice Java:
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;
}
}
}
Come puoi vedere, il codice è quasi lo stesso. Il primo codice è un esempio tratto dal libro. Il secondo è la mia esecuzione gratuita in codice Java.
Ricorsione
Successivamente ci viene detto che esiste qualcosa come la ricorsione. Innanzitutto, c’è il problema di un agricoltore che ha un campo di dimensioni AxB. È necessario dividere questo campo in “quadrati” uguali. E poi viene menzionato l'algoritmo di Euclide. Quello che non mi piace è che non abbiano provato a scriverne il codice. Ma l’algoritmo di Euclide è semplice ed efficace:
def euclidean(a, b):
if a == 0 : return b
if b == 0 : return a
return euclidean (b, a % b)
Scriviamo lo stesso codice in Java. Se lo si desidera, possiamo utilizzare il compilatore online :
public static int euclid(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
return euclid(b, a%b);
}
Anche il fattoriale è stato menzionato all'inizio del libro. Il fattoriale di un numero n (n!) è il prodotto dei numeri da 1 a n. Perché farlo? C'è un'applicazione pratica qui. Se abbiamo n oggetti (ad esempio n città), allora possiamo crearne n! Combinazioni. Puoi leggere ulteriori informazioni sulla ricorsione qui: " Ricorsione. Attività di formazione ". Confronto tra approcci iterativi e ricorsivi: " La ricorsione ".
Ordinamento rapido
L'ordinamento rapido è un algoritmo piuttosto interessante. Il libro non gli presta molta attenzione. Inoltre il codice viene fornito solo nel caso peggiore, quando viene selezionato il primo elemento. Tuttavia, forse per una prima conoscenza questo esempio sarà più facile da ricordare. Ed è meglio scrivere un cattivo quicksort piuttosto che non scriverne affatto. Ecco un esempio dal libro:
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)
Tutto qui è semplicissimo. Se abbiamo un array di 0 o 1 elemento, non è necessario ordinarlo. Se è maggiore, prendiamo il primo elemento dell'array e lo consideriamo “elemento pivot”. Creiamo 2 nuovi array: uno contiene elementi più grandi del pivot e il secondo contiene elementi più piccoli. E lo ripetiamo ricorsivamente. Non è l'opzione migliore, ma ancora una volta, ricordata meglio. Implementiamo questo algoritmo in Java, ma più correttamente. In questo ci aiuterà il materiale della recensione " Informatica in JavaScript: Quicksort " . E prima di scrivere il codice, disegniamo di nuovo per “sentire” l'algoritmo: Per prima cosa, disegniamo di nuovo su un pezzo di carta per capire l'algoritmo:
-
Dobbiamo essere in grado di scambiare elementi in un array:
private static void swap(int[] array, int firstIndex, int secondIndex) { int temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp; }
-
Abbiamo bisogno di un metodo che divida l'array nell'intervallo specificato in 3 parti
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; }
Dettagli al link sopra. In breve spostiamo il cursore sinistro finché l'elemento non risulta inferiore al pivot. Allo stesso modo, sposta il cursore destro dall'altra estremità. E facciamo uno scambio se i cursori non corrispondono. Continuiamo finché i cursori non convergono. Restituiamo un indice che divide l'ulteriore elaborazione in 2 parti.
-
C'è una separazione, abbiamo bisogno dell'ordinamento stesso:
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); } } }
Cioè, se l'array è composto da almeno due elementi, è già possibile ordinarli. Per prima cosa dividiamo l'intero array in due parti, elementi più piccoli del pivot ed elementi più grandi. Quindi eseguiamo azioni simili per ciascuna delle parti risultanti.
E per la prova:
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);
}
Determiniamo il centro e dividiamo l'array a metà. Per ogni metà facciamo lo stesso e così via. Condizione di arresto o caso base: dobbiamo avere più di un elemento, poiché non possiamo dividere un elemento in due. Ora dobbiamo implementare la fusione, ovvero unire:
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);
}
Non c'è molto da commentare qui. Dai nomi delle variabili println
tutto è chiaro. Bene, per verificare:
int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
Tabelle hash
Il libro tocca anche le tabelle hash. Non è necessario implementarlo da soli e l'essenza delle tabelle hash è abbastanza semplice. Dopotutto, Java ha anche un'implementazione di tabelle hash, java.util.HashTable. Se guardiamo il dispositivo HashTable, vedremo che al suo interno risiede l'array Entry. La voce è un record che è una combinazione di Chiave – Valore. HashTable ha la capacità iniziale, ovvero la dimensione iniziale. E loadFactor – fattore di carico. L'impostazione predefinita è 0,75. Questo numero indica a quale carico dell'array (numero di elementi/quantità totale) è necessario aumentare la dimensione. In Java aumenta di 2 volte. Il libro spiega che le tabelle Hash sono chiamate tabelle hash perché basate sulla funzione hash, la cella dell'array (cestino) in cui si trova il fileEntry
. Puoi anche leggere di più qui: Strutture dati nelle immagini. HashMap e LinkedHashMap . Puoi leggerlo anche nei libri. Ad esempio qui: " Nozioni di base su HashTable "
Grafici, ricerca prima in ampiezza (ricerca del percorso più breve)
Probabilmente uno degli argomenti più interessanti sono i grafici. E qui, a onor del vero, il libro presta molta attenzione a loro. Forse è per questo che vale la pena leggere questo libro. Anche se, forse, si sarebbe potuto dirlo in modo un po' più chiaro)) Ma abbiamo Internet e oltre al libro, puoi guardare questa playlist sulla teoria per “chi sente parlare di grafici per la prima volta . " Ebbene, naturalmente, all'inizio del librobreadth-first-search
viene fornito l'algoritmo di ricerca in ampiezza, noto anche come BFS. Il libro contiene il seguente grafico:
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;
}
Ora la ricerca stessa, basata su questi dati:
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;
}
Come puoi vedere, niente di complicato. Se lo confronti con il codice del libro, è quasi lo stesso.
Grafici, algoritmo di Dijkstra
Avendo più o meno compreso BFS, l'autore del libro ci invita a comprendere l'algoritmo Daysktra e i grafici ponderati. Per la soluzione si propone il seguente grafico: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;
}
E ora la logica stessa:
@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);
}
Il libro lo analizza passo dopo passo. Se aggiungi un articolo su Habré su Internet + guarda il codice, puoi ricordarlo. Ho trovato l'analisi passo passo un po' confusa. Ma per la natura stessa del passo dopo passo è un vantaggio. Nel complesso, ok, anche se avrebbe potuto essere migliore)
Algoritmi golosi
La sezione successiva è dedicata agli “algoritmi golosi”. Questa sezione è interessante perché utilizza i set (java.util.Set). Finalmente possiamo capire perché potrebbe essere necessario. Usiamo un elenco di stati come input:Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));
E anche un elenco di stazioni radio che coprono alcuni di questi stati:
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")));
Il libro prosegue sottolineando e spiegando l'algoritmo stesso:
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);
Programmazione dinamica
Nel libro vengono inoltre descritti i problemi ai quali viene applicato un approccio chiamato “programmazione dinamica”. Il compito è assegnato: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));
Ora l'algoritmo stesso:
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));
C'è anche un compito interessante per trovare le parole più simili. Interessante, vero? Maggiori dettagli qui: LongestCommonSubsequence.java
Cerca i vicini più vicini
Il libro parla anche molto chiaramente dell'algoritmo dei k-vicini più vicini:Linea di fondo
Il libro termina con un'interessante sezione "Cosa c'è dopo?", che fornisce una rapida panoramica di algoritmi interessanti. Ecco una breve descrizione del significato degli alberi e di altri algoritmi. Nel complesso, il libro mi è piaciuto. Non dovrebbe essere preso sul serio come una sorta di informazione completa. Dovrai cercare e capire da solo. Ma come informazione introduttiva per interessare e dare un’idea iniziale, è abbastanza buona. Sì, il codice nel libro è scritto in Python. Quindi tutti gli esempi sopra riportati sono compilabili) Spero che questa recensione ti aiuti a farti un'idea di cosa contiene il libro e se vale la pena acquistarlo.Inoltre
Puoi anche consultare le seguenti risorse su questo argomento:- EdX - Introduzione alla programmazione Java: strutture dati e algoritmi fondamentali
- LinkedIn - Introduzione alle strutture dati e agli algoritmi in Java (a pagamento)
- 27 siti con puzzle per affinare le tue capacità di programmazione
- Java CodingBat
- Compiti per programmatori, risposte a compiti di varia complessità
GO TO FULL VERSION