บทวิจารณ์หนังสือ "Grocking Algorithms" ความเห็นส่วนตัวเพียงเล็กน้อย ตัวอย่างบางส่วน ฉันหวังว่าบทวิจารณ์นี้จะช่วยให้คุณเข้าใจว่าคุณต้องการอ่านหนังสือเล่มนี้หรือไม่หรือจะไม่วางบนชั้นวางของคุณหรือไม่ คำเตือน: ข้อความจำนวนมาก)
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 1]()
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 2]()
อัลกอริทึมมักอธิบายไว้ในรหัสเทียม เช่น ในวิกิพีเดีย ของเราไม่ใช่รหัสเทียม แต่จะเพิ่มเติมในภายหลัง ตอนนี้เรามาดูกัน:
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริธึมที่ไม่เจ็บปวด - 3]()
พูดตามตรง ฉันพลาดรายละเอียดบางอย่างในหนังสือไป อย่างเช่นในวิดีโอนี้: “ สารสนเทศ ทฤษฎีอัลกอริธึม อัลกอริธึมของ Euclid ” ตัวอย่างเช่น ถ้า a น้อยกว่า b ดังนั้นในระหว่างการรันครั้งแรก b และ a จะเปลี่ยนตำแหน่ง และครั้งที่สองที่ใหญ่กว่าจะถูกหารด้วยอันที่เล็กกว่า ดังนั้นลำดับของการโต้แย้งจึงไม่สำคัญ ตามปกติ ก่อนอื่นเราสามารถ "สัมผัส" อัลกอริธึมบนกระดาษได้:
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 4]()
ตอนนี้เรามาดูโค้ดกัน:
![Java-университет]()
มาเขียนโค้ดเดียวกันใน Java กัน หากต้องการเราสามารถใช้คอมไพเลอร์ออนไลน์ได้ :
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริธึมที่ไม่เจ็บปวด - 5]()
สำหรับฉันดูเหมือนว่าช่วงเวลาที่อันตรายที่สุดช่วงหนึ่งคือการแก้ปัญหาโดยสิ้นเชิง ดังนั้นเราจะดำเนินการตามขั้นตอนเล็กๆ หลายประการ:
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 6]()
สิ่งที่ไม่ดี (นั่นคือสิ่งที่ฉันไม่ชอบ) ก็คือหนังสือเล่มนี้กล่าวถึงการเรียงลำดับแบบผสานในการส่งผ่าน แต่ไม่มีตัวอย่างหรือโค้ดใดๆ ดูรายละเอียดเพิ่มเติมได้ที่นี่: " สารสนเทศ อัลกอริธึมการค้นหาและการเรียงลำดับ: การเรียงลำดับแบบผสาน " ดังนั้นเพื่อความสม่ำเสมอเรามาทำเองกันดีกว่า แน่นอนว่าอัลกอริทึมนั้นเรียบง่ายและตรงไปตรงมาโดยเนื้อแท้:
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 7]()
หนังสือระบุว่าคิวจะช่วยเรา ยิ่งไปกว่านั้น ทำให้เราสามารถเพิ่มองค์ประกอบที่ส่วนท้ายและประมวลผลคิวตั้งแต่ต้นได้ คิวดังกล่าวเรียกว่าคิวสองทางหรือ Deque ในภาษาอังกฤษ หนังสือเล่มนี้แนะนำให้ใช้โครงสร้างข้อมูล - ตารางแฮช เพื่อเชื่อมโยงชื่อและเพื่อนบ้าน ด้วยจุดยอดที่มีตัวเลข คุณสามารถใช้อาร์เรย์ได้ การจัดเก็บจุดยอดนี้เรียกว่า "รายการจุดยอดที่อยู่ติดกัน" ซึ่งไม่ได้กล่าวถึงในหนังสือ นี่คือลบสำหรับพวกเขา ลองใช้สิ่งนี้ใน Java:
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 8]()
ขั้นแรก เราต้องเข้าใจวิธีการแสดงกราฟของเรา เราสามารถแสดงมันเป็นเมทริกซ์ได้ บทความเกี่ยวกับHabréจะช่วยเราได้ที่นี่: อัลกอริทึมของ Dijkstra การค้นหา เส้นทางที่เหมาะสมที่สุดบนกราฟ ลองใช้เมทริกซ์คำคุณศัพท์:
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 9]()
เรามีกระเป๋าขนาด 4 ปอนด์ คุณต้องค้นหาสินค้าที่ทำกำไรได้มากที่สุดตามน้ำหนักที่กำหนด ขั้นแรก เรามาสร้างรายการกันก่อน:
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด - 10]()
และให้สูตรการคำนวณดังนี้
![“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริธึมที่ไม่เจ็บปวด - 11]()
“อัลกอริธึม Grocking” หรือความรู้เบื้องต้นเกี่ยวกับอัลกอริทึมที่ไม่เจ็บปวด
การแนะนำ
ตำแหน่งงานว่างระดับจูเนียร์เกือบทุกตำแหน่งมีข้อกำหนดเช่น "ความรู้เกี่ยวกับโครงสร้างข้อมูลและอัลกอริธึม" สำหรับผู้ที่มีการศึกษาเฉพาะทางก็มีอัลกอริธึมรวมอยู่ในหลักสูตรทั่วไปแล้วไม่น่าจะมีปัญหาอะไร แต่จะเกิดอะไรขึ้นถ้าการพัฒนาถูกนำมาจากสเตปป์อื่น? สิ่งที่เหลืออยู่คือการเรียนรู้ด้วยตัวเอง มีคำตอบสำหรับคำถามที่ว่า “ใครจะตำหนิ” แต่สำหรับคำถาม “จะทำอย่างไร” ก็ต้องค้นหาคำตอบ มาดูในหนังสือกัน และฉันอยากจะบอกคุณเกี่ยวกับเรื่องหนึ่งอัลกอริธึม Grok
ในบรรดาผลงานทั้งหมด ฉันเจอหนังสือชื่อ "Grocking Algorithms" คุณสามารถหาข้อมูลเพิ่มเติมได้ที่นี่: “ หนังสือ “Growing Algorithms คู่มือพร้อมภาพประกอบสำหรับโปรแกรมเมอร์และผู้ที่มีความอยากรู้อยากเห็น ” ฉันสังเกตเห็นหนังสือเล่มนี้เมื่อนานมาแล้ว แต่สำหรับโอโซนมีราคา 680 รูเบิล แพงหรือถูก - ทุกคนตัดสินใจด้วยตัวเอง ฉันกำลังซื้อหนังสือเล่มที่สองบน Avito ในราคาเพียงครึ่งเดียวแล้ว ดังนั้นฉันจึงพบมันในเซนต์ปีเตอร์สเบิร์ก ซื้อมัน และไปคร่ำครวญ ซึ่งเป็นสิ่งที่ฉันตัดสินใจแบ่งปันกับคุณ ใช่ ไม่มีโค้ด 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;
}
}
}การเรียกซ้ำ
ต่อไปเราจะบอกว่ามีสิ่งที่เรียกว่าการเรียกซ้ำ ก่อนอื่นมีปัญหากับเกษตรกรที่มีนาขนาด AxB จำเป็นต้องแบ่งฟิลด์นี้ออกเป็น "กำลังสอง" เท่า ๆ กัน และหลังจากนั้นก็กล่าวถึง Euclid Algorithm สิ่งที่ฉันไม่ชอบก็คือพวกเขาไม่ได้พยายามเขียนโค้ดของมัน แต่อัลกอริทึม 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);
}จัดเรียงอย่างรวดเร็ว
การเรียงลำดับอย่างรวดเร็วเป็นอัลกอริทึมที่ค่อนข้างน่าสนใจ หนังสือไม่ได้สนใจเขามากนัก นอกจากนี้ รหัสจะได้รับเฉพาะในกรณีที่เลวร้ายที่สุด เมื่อเลือกองค์ประกอบแรก อย่างไรก็ตาม บางทีสำหรับคนรู้จักครั้งแรกตัวอย่างนี้อาจจดจำได้ง่ายกว่า และเป็นการดีกว่าที่จะเขียน Quicksort ที่ไม่ดีมากกว่าที่จะไม่เขียนเลย นี่คือตัวอย่างจากหนังสือ:
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); } } }นั่นคือถ้าอาร์เรย์ประกอบด้วยองค์ประกอบอย่างน้อยสององค์ประกอบ ก็สามารถเรียงลำดับได้แล้ว ขั้นแรก เราแบ่งอาร์เรย์ทั้งหมดออกเป็นสองส่วน องค์ประกอบที่เล็กกว่าเดือยและองค์ประกอบที่ใหญ่กว่า จากนั้นเราจะดำเนินการที่คล้ายกันสำหรับแต่ละส่วนที่เป็นผล
และสำหรับการทดสอบ:
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 เราจะเห็นว่าอาร์เรย์รายการอาศัยอยู่ภายใน รายการคือเรกคอร์ดที่เป็นการรวมกันของคีย์ – ค่า HashTable มี defaultCapacity - นั่นคือขนาดเริ่มต้น และ loadFactor – ปัจจัยโหลด ค่าเริ่มต้นคือ 0.75 ตัวเลขนี้จะบอกคุณว่าโหลดของอาร์เรย์ (จำนวนองค์ประกอบ/จำนวนทั้งหมด) ใดที่ต้องเพิ่มขนาด ใน Java มันเพิ่มขึ้น 2 เท่า หนังสืออธิบายว่าตารางแฮชเรียกว่าตารางแฮช เนื่องจากขึ้นอยู่กับฟังก์ชันแฮช ซึ่งก็คือเซลล์อาร์เรย์ (ตะกร้า) ซึ่งไฟล์Entry. คุณยังสามารถอ่านเพิ่มเติมได้ที่นี่: โครงสร้างข้อมูลในรูปภาพ HashMapและLinkedHashMap _ คุณยังสามารถอ่านได้ในหนังสือ ตัวอย่างที่นี่: " พื้นฐาน HashTable "
กราฟ, การค้นหาแบบกว้างก่อน (การค้นหาเส้นทางที่สั้นที่สุด)
อาจเป็นหนึ่งในหัวข้อที่น่าสนใจที่สุดคือกราฟ พูดตามตรงแล้วหนังสือเล่มนี้ให้ความสำคัญกับพวกเขาเป็นอย่างมาก บางทีนั่นอาจเป็นเหตุผลว่าทำไมจึงคุ้มค่าที่จะอ่านหนังสือเล่มนี้ แม้ว่าบางทีอาจจะระบุไว้ชัดเจนกว่านี้อีกหน่อย)) แต่เรามีอินเทอร์เน็ตและนอกเหนือจากหนังสือแล้ว คุณสามารถดูเพลย์ลิสต์เกี่ยวกับทฤษฎีนี้สำหรับ "ผู้ที่ได้ยินเกี่ยวกับกราฟเป็นครั้งแรก " ” ในตอนต้นของหนังสือ อัลกอริธึมการค้นหาแบบกว้างต้องมาก่อนbreadth-first-searchหรือที่เรียกว่า BFS ได้ถูกมอบให้ไว้ หนังสือเล่มนี้ประกอบด้วยกราฟต่อไปนี้:
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));ค้นหาเพื่อนบ้านที่ใกล้ที่สุด
หนังสือเล่มนี้ยังพูดถึงอัลกอริธึมเพื่อนบ้านที่ใกล้ที่สุดอย่างชัดเจน:
GO TO FULL VERSION