「Grocking Algorithms」という本のレビュー。少し個人的な意見と例をいくつか。このレビューが、この本を読みたいかどうか、それとも本棚に置かなくてもよいかどうかを理解するのに役立つことを願っています。警告: 大量のテキスト)
![「Grocking Algorithms」または苦痛のないアルゴリズム入門 - 1]()
![「Grocking Algorithms」またはアルゴリズムへの苦痛のない入門 - 2]()
アルゴリズムは、Wikipedia などで擬似コードで説明されていることがよくあります。私たちのものは正確には擬似コードではありませんが、それについては後で詳しく説明します。とりあえず見てみましょう:
![「Grocking Algorithms」またはアルゴリズムへの苦痛のない入門 - 3]()
正直に言うと、このビデオのように、この本の詳細をいくつか見逃していました。アルゴリズムの理論。ユークリッドのアルゴリズム。」たとえば、a が b より小さい場合、最初の実行中に b と a の位置が変わり、2 回目では大きい方が小さい方で除算されます。したがって、引数の順序は重要ではありません。いつものように、まずアルゴリズムを紙の上で「感じて」みましょう。
![「Grocking Algorithms」またはアルゴリズムへの苦痛のない入門 - 4]()
次に、コードを見てみましょう。
![Java-университет]()
![「Grocking Algorithms」または苦痛のないアルゴリズム入門 - 5]()
最も危険な瞬間の一つは、問題を完全に解決してしまうことだと私には思えます。したがって、いくつかの小さなステップに分けて実装を実行します。
![「Grocking Algorithms」またはアルゴリズムの簡単な入門 - 6]()
残念な点 (つまり、私が気に入らなかった点) は、この本ではマージ ソートについて触れているものの、例やコードがまったく示されていないことです。詳細については、「情報学。検索および並べ替えアルゴリズム: マージ ソート」を参照してください。したがって、一貫性を保つために、自分で実行しましょう。もちろん、アルゴリズム自体は本質的にシンプルで簡単です。
![「Grocking Algorithms」またはアルゴリズムへの苦痛のない入門 - 7]()
本には、行列が役に立つと書かれています。さらに、要素を最後に追加してキューを最初から処理できるようにします。このようなキューは、英語では双方向キューまたは Deque と呼ばれます。この本では、データ構造、つまりハッシュ テーブルの使用を提案しています。名前と隣人を関連付けるため。番号付きの頂点を使用すると、単純に配列を使用できます。この頂点の保存は「隣接頂点のリスト」と呼ばれますが、本書では言及されていません。これは彼らにとってマイナスです。これを Java で実装してみましょう。
![「Grocking Algorithms」またはアルゴリズムへの苦痛のない入門 - 8]()
まず、グラフを表現する方法を理解する必要があります。それを行列として表すことができます。ハブレに関する記事「ダイクストラのアルゴリズム」が役に立ちます。グラフ上で最適なルートを見つける。隣接行列を使用してみましょう。
![「Grocking Algorithms」またはアルゴリズムの簡単な入門 - 9]()
私たちは4ポンドのバッグを持っています。特定の重量で最も収益性の高いアイテムを見つける必要があります。まず、項目のリストを作成しましょう。
![「Grocking Algorithms」またはアルゴリズムへの苦痛のない入門 - 10]()
そして、計算式は次のようになります。
![「Grocking Algorithms」またはアルゴリズムへの苦痛のない入門 - 11]()
「成長するアルゴリズム」またはアルゴリズムの簡単な入門
導入
ほぼすべてのジュニアレベルの求人には、「データ構造とアルゴリズムの知識」などの要件があります。専門教育を受けた人であれば、アルゴリズムは一般課程に含まれているので問題ありません。しかし、開発が他の草原から持ち込まれた場合はどうなるでしょうか? あとは自分で学ぶだけです。「誰のせいなのか」という問いには答えがありますが、「何をすべきか」という問いには答えを探さなければなりません。本で調べてみましょう。そして、一つお話ししたいと思います。Grok アルゴリズム
そんな中、『Grocking Algorithms』という本に出会いました。詳細については、「書籍『成長するアルゴリズム。プログラマーと好奇心旺盛な人のための図解ガイド』」を参照してください。私はずっと前にこの本に気づきましたが、オゾンでは680ルーブルかかりました。高いか安いか - 誰もが自分で決めます。私はすでに Avito の 2 冊目の本を半額で購入しています。それで私はサンクトペテルブルクでそれを見つけて購入し、グロッキングに行きました。それが私があなたと共有することにしたことです。はい、この本には Java コードはありませんが、他のコードはあります。詳細については後ほど説明します。アルゴリズムの概要 (選択ソート)
こうして、ナレーションというわかりやすい形式で、パフォーマンスの最初の分類に到達します。これが選択ソートです。その本質は、要素を左から右に (0 要素から最後の要素まで) 調べて、残りの要素の中で最大のものを探すことです。それが見つかったら、現在いる要素と最大の要素を交換します。最初に配列を考える最も簡単な方法は、[5, 3, 6, 2, 10] です。紙とペン (最もシンプルで費用対効果の高い方法) を用意し、左境界線、現在のインデックス (または右境界線)、および最小要素のインデックスがどのように作成されるかを想像してください。そして、それをどのように扱うか。例えば：
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]))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;
}
}
}再帰
次に、再帰というものがあることが説明されます。まず、A×Bの広さの畑を持つ農家の問題です。このフィールドを等しい「正方形」に分割する必要があります。そしてこの後、ユークリッドアルゴリズムについて言及します。私が気に入らないのは、彼らがそのコードを書こうとしていなかったことです。しかし、Euclid アルゴリズムはシンプルかつ効果的です。
def euclidean(a, b):
if a == 0 : return b
if b == 0 : return a
return euclidean (b, a % b)public static int euclid(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
return euclid(b, a%b);
}
クイックソート
クイックソートはかなり興味深いアルゴリズムです。この本は彼にあまり注目していない。さらに、コードは最初の要素が選択された場合の最悪の場合にのみ与えられます。ただし、おそらく、初めて知り合った人にとっては、この例の方が覚えやすいでしょう。そして、悪いクイックソートをまったく書かないよりも、書いたほうが良いでしょう。この本からの例は次のとおりです。
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)
-
配列内の要素を交換できる必要があります。
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); } } }つまり、配列が少なくとも 2 つの要素で構成されている場合、それらはすでに並べ替えることができます。まず、配列全体を、ピボットより小さい要素と大きい要素の 2 つの部分に分割します。次に、結果として得られる各パーツに対して同様のアクションを実行します。
そしてテストのために：
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);
}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 配列があることがわかります。エントリは、キーと値の組み合わせであるレコードです。HashTable には、initialCapacity、つまり初期サイズがあります。そして、loadFactor – 負荷係数。デフォルトは 0.75 です。この数値は、配列のどの程度の負荷 (要素数/総数) でサイズを増やす必要があるかを示します。Java では 2 倍になります。この本では、ハッシュ テーブルがハッシュ テーブルと呼ばれるのは、ハッシュ関数に基づいており、Entry. ここで詳細を読むこともできます: 画像のデータ構造。HashMapとLinkedHashMap。本でも読むことができます。例は次のとおりです:「HashTable の基本」
グラフ、幅優先検索（最短経路検索）
おそらく最も興味深いトピックの 1 つはグラフです。そしてここで、公平を期すために、この本はそれらに多くの注意を払っています。だからこそ、この本を読む価値があるのかもしれない。おそらく、もう少し明確に述べられたかもしれませんが））しかし、私たちはインターネットを持っており、本に加えて、「グラフについて初めて聞く人」のために理論に関するこのプレイリストを見ることができます。 」当然のことながら、この本の冒頭では、BFS としても知られる幅優先検索アルゴリズムがbreadth-first-search説明されています。この本には次のようなグラフが掲載されています。
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;
}グラフ、ダイクストラのアルゴリズム
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);
}貪欲なアルゴリズム
次のセクションでは、「貪欲なアルゴリズム」について説明します。このセクションはセット (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);動的プログラミング
本書では、「動的計画法」と呼ばれるアプローチが適用される問題についても説明されています。タスクは次のように与えられます。
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));最近傍を検索する
この本では、k 最近傍アルゴリズムについても非常に明確に説明しています。
GO TO FULL VERSION