Thuật toán Grocking hoặc phần giới thiệu dễ dàng về thuật toán

Review cuốn sách "Thuật toán Grocking". Một chút ý kiến ​​cá nhân, một vài ví dụ. Tôi hy vọng bài đánh giá này sẽ giúp bạn hiểu liệu bạn muốn đọc cuốn sách này hay liệu nó sẽ không xuất hiện trên kệ của bạn. CẢNH BÁO: Rất nhiều văn bản)

“Thuật toán đang phát triển” hoặc Giới thiệu dễ dàng về thuật toán

Giới thiệu

Hầu như bất kỳ vị trí tuyển dụng nào ở cấp độ Junior đều có các yêu cầu như “kiến thức về cấu trúc dữ liệu và thuật toán”. Đối với những người có trình độ học vấn chuyên biệt, các thuật toán được đưa vào khóa học tổng quát và sẽ không có vấn đề gì. Nhưng điều gì sẽ xảy ra nếu sự phát triển được mang đến từ các thảo nguyên khác? Tất cả những gì còn lại là tự học. Có câu trả lời cho câu hỏi “ai là người có lỗi”, nhưng câu hỏi “phải làm gì” thì phải tìm câu trả lời. Chúng ta hãy nhìn vào sách. Và tôi muốn kể cho bạn nghe về một điều.

Thuật toán Grok

Trong số tất cả các tác phẩm, tôi tình cờ thấy một cuốn sách như “Thuật toán Grocking”. Bạn có thể tìm hiểu thêm tại đây: " Cuốn sách "Thuật toán phát triển. Hướng dẫn minh họa dành cho lập trình viên và những người tò mò ." Tôi đã để ý đến cuốn sách này từ lâu, nhưng trên ozone, nó có giá 680 rúp. Đắt hay rẻ - mỗi người tự quyết định. Tôi đã mua cuốn sách thứ hai trên Avito với giá chỉ bằng một nửa. Vì vậy, tôi đã tìm thấy nó ở St. Petersburg, mua nó và mò mẫm. Đó là những gì tôi quyết định chia sẻ với bạn. Đúng, không có mã Java trong sách, nhưng có... mã khác, nhưng sẽ nói thêm về điều đó sau.

Giới thiệu về thuật toán (Sắp xếp lựa chọn)

Vì vậy, bằng một hình thức tường thuật dễ dàng, chúng ta đạt đến điểm xuất sắc đầu tiên trong màn trình diễn của mình. Đây là Sắp xếp lựa chọn. Bản chất của nó là chúng ta duyệt qua các phần tử từ trái sang phải (từ phần tử 0 đến phần tử cuối cùng) và tìm phần tử lớn nhất trong số các phần tử còn lại. Nếu chúng ta tìm thấy nó, thì chúng ta hoán đổi phần tử mà chúng ta đang ở trên đó và phần tử lớn nhất. Cách đơn giản nhất để nghĩ về mảng đầu tiên là: [5, 3, 6, 2, 10]. Lấy một tờ giấy, một cây bút (cách đơn giản và rẻ tiền nhất) và tưởng tượng chúng ta có viền trái (trái), chỉ mục hiện tại (hoặc viền phải), có chỉ mục của phần tử tối thiểu. Và cách chúng tôi làm việc với nó. Ví dụ: Các thuật toán thường được mô tả bằng mã giả, chẳng hạn như trên Wikipedia. Mã của chúng tôi không hẳn là mã giả, nhưng sẽ nói thêm về điều đó sau. Bây giờ chúng ta hãy xem:

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]))

Bây giờ hãy trình bày nó dưới dạng mã 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;
            }
        }
}

Như bạn có thể thấy, mã gần như giống nhau. Mã đầu tiên là một ví dụ từ cuốn sách. Thứ hai là khả năng thực thi miễn phí của tôi bằng mã Java.

đệ quy

Tiếp theo chúng ta được biết rằng có một thứ gọi là đệ quy. Trước hết có vấn đề về một người nông dân có cánh đồng có kích thước AxB. Cần phải chia trường này thành các “hình vuông” bằng nhau. Và sau đó Thuật toán Euclid được đề cập. Điều tôi không thích là họ không cố gắng viết mã cho nó. Nhưng thuật toán Euclid rất đơn giản và hiệu quả: Thành thật mà nói, tôi đã bỏ lỡ một số chi tiết trong cuốn sách, như trong video này: “ Tin học. Lý thuyết về thuật toán. Thuật toán Euclid .” Ví dụ: nếu a nhỏ hơn b thì trong lần chạy đầu tiên b và a sẽ đổi chỗ và ở lần thứ hai cái lớn hơn sẽ bị chia cho cái nhỏ hơn. Vì vậy, thứ tự của các đối số không quan trọng. Như thường lệ, đầu tiên chúng ta có thể “cảm nhận” thuật toán trên một tờ giấy: Bây giờ hãy xem mã:

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

Hãy viết cùng một mã trong Java. Nếu muốn, chúng ta có thể sử dụng trình biên dịch trực tuyến :

public static int euclid(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        return euclid(b, a%b);
}

Yếu tố cũng đã được đề cập ở phần đầu của cuốn sách. Giai thừa của một số n (n!) là tích của các số từ 1 đến n. Tại sao làm điều này? Có một ứng dụng thực tế ở đây. Nếu chúng ta có n đối tượng (ví dụ: n thành phố), thì chúng ta có thể tạo ra n đối tượng! Sự kết hợp. Bạn có thể đọc thêm về đệ quy tại đây: " Đệ quy. Nhiệm vụ đào tạo ." So sánh các phương pháp lặp và đệ quy: " Đệ quy ".

Sắp xếp nhanh chóng

Sắp xếp nhanh là một thuật toán khá thú vị. Cuốn sách không chú ý nhiều đến anh ta. Hơn nữa, mã chỉ được đưa ra cho trường hợp xấu nhất khi phần tử đầu tiên được chọn. Tuy nhiên, có lẽ đối với những người mới làm quen lần đầu, ví dụ này sẽ dễ nhớ hơn. Và thà viết một bản sắp xếp nhanh tồi còn hơn là không viết một bản nào cả. Đây là một ví dụ từ cuốn sách:

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)

Mọi thứ ở đây đều siêu đơn giản. Nếu chúng ta có một mảng gồm 0 hoặc 1 phần tử thì không cần sắp xếp nó. Nếu nó lớn hơn, chúng ta lấy phần tử đầu tiên của mảng và coi nó là “phần tử xoay”. Chúng tôi tạo 2 mảng mới - một mảng chứa các phần tử lớn hơn trục và mảng thứ hai chứa các phần tử nhỏ hơn. Và chúng tôi lặp lại đệ quy. Không phải là lựa chọn tốt nhất, nhưng một lần nữa, được ghi nhớ tốt hơn. Hãy triển khai thuật toán này trong Java nhưng chính xác hơn. Tài liệu từ bài đánh giá “ Khoa học máy tính trong JavaScript: Quicksort ” sẽ giúp chúng ta điều này . Và trước khi viết code, chúng ta hãy vẽ lại để “cảm nhận” thuật toán: Đầu tiên chúng ta hãy vẽ lại trên một tờ giấy để hiểu thuật toán: Đối với tôi, có vẻ như một trong những thời điểm nguy hiểm nhất là giải quyết toàn bộ vấn đề. Vì vậy, chúng ta sẽ tiến hành thực hiện theo một số bước nhỏ:

• Chúng ta cần có khả năng hoán đổi các phần tử trong một mảng:

  private static void swap(int[] array, int firstIndex, int secondIndex) {
          int temp = array[firstIndex];
          array[firstIndex] = array[secondIndex];
          array[secondIndex] = temp;
  }




• Chúng ta cần một phương thức chia mảng trong khoảng đã chỉ định thành 3 phần

  
  

  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;
  }

  Chi tiết tại link trên. Nói tóm lại, chúng ta di chuyển con trỏ trái cho đến khi phần tử nhỏ hơn trục xoay. Tương tự, di chuyển con trỏ phải từ đầu bên kia. Và chúng tôi thực hiện hoán đổi nếu con trỏ không khớp. Chúng tôi tiếp tục cho đến khi các con trỏ hội tụ. Chúng tôi trả về một chỉ mục chia quá trình xử lý tiếp theo thành 2 phần.

• Có sự tách biệt, chúng ta cần tự sắp xếp:

  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);
              }
          }
  }

  Nghĩa là, nếu mảng bao gồm ít nhất hai phần tử thì chúng có thể được sắp xếp. Đầu tiên, chúng ta chia toàn bộ mảng thành hai phần, các phần tử nhỏ hơn trục và các phần tử lớn hơn. Sau đó, chúng tôi thực hiện các hành động tương tự cho từng phần kết quả.

  Và cho bài kiểm tra:

  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));
  }

Cuốn sách nói rằng thuật toán này thuộc về cái gọi là thuật toán “Chia để trị”, khi tập dữ liệu đã xử lý được chia làm đôi mỗi lần. Độ phức tạp của thuật toán: O(nLogn) Điều tệ (tức là điều tôi không thích) là cuốn sách đề cập đến việc sắp xếp hợp nhất khi chuyển qua, nhưng không cung cấp bất kỳ ví dụ hoặc mã nào. Thông tin chi tiết có thể tìm thấy tại đây: " Tin học. Thuật toán tìm kiếm và sắp xếp: Sắp xếp hợp nhất ". Vì vậy, để thống nhất, chúng ta hãy tự mình thực hiện. Tất nhiên, bản thân thuật toán vốn đã đơn giản và dễ hiểu:

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);
}

Chúng tôi xác định phần giữa và chia mảng làm đôi. Đối với mỗi nửa, chúng tôi làm tương tự, v.v. Điều kiện dừng hoặc trường hợp cơ sở - chúng ta phải có nhiều hơn một phần tử, vì chúng ta không thể chia một phần tử thành hai phần tử. Bây giờ chúng ta cần thực hiện việc sáp nhập, nghĩa là hợp nhất:

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);
}

Không có nhiều điều để bình luận ở đây. Từ tên của các biến, printlnmọi thứ đều rõ ràng. Vâng, để kiểm tra:

int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));

Bảng băm

Cuốn sách cũng chạm vào bảng băm. Bạn không cần phải tự thực hiện và bản chất của bảng băm khá đơn giản. Suy cho cùng, Java cũng có triển khai các bảng băm, java.util.HashTable. Nếu nhìn vào thiết bị HashTable, chúng ta sẽ thấy mảng Entry nằm bên trong. Mục nhập là một bản ghi là sự kết hợp của Khóa – Giá trị. HashTable có initCapacity - nghĩa là kích thước ban đầu. Và LoadFactor – hệ số tải. Mặc định là 0,75. Con số này cho bạn biết mức tải của mảng (số phần tử/tổng ​​số) thì kích thước cần tăng lên. Trong Java nó tăng gấp 2 lần. Sách giải thích rằng bảng Hash được gọi là bảng băm vì dựa trên hàm băm, ô mảng (rổ) trong đó Entry. Bạn cũng có thể đọc thêm tại đây: Cấu trúc dữ liệu trong ảnh. HashMap và LinkedHashMap . Bạn cũng có thể đọc nó trong sách. Ví dụ ở đây: " Khái niệm cơ bản về HashTable "

Đồ thị, Tìm kiếm theo chiều rộng (tìm kiếm đường dẫn ngắn nhất)

Có lẽ một trong những chủ đề thú vị nhất là đồ thị. Và ở đây, công bằng mà nói, cuốn sách dành rất nhiều sự quan tâm cho họ. Có lẽ đó là lý do tại sao nó đáng đọc cuốn sách này. Mặc dù, có lẽ, nó có thể được trình bày rõ ràng hơn một chút)) Nhưng, chúng tôi có Internet và ngoài cuốn sách, bạn có thể xem danh sách phát này về lý thuyết dành cho “những người lần đầu tiên nghe về đồ thị . ” Vâng, một cách tự nhiên, ở phần đầu của cuốn sách, thuật toán tìm kiếm theo chiều rộng, breadth-first-searchcòn được gọi là BFS, đã được đưa ra. Cuốn sách chứa biểu đồ sau: Cuốn sách nói rằng việc xếp hàng sẽ giúp ích cho chúng ta. Hơn nữa, như vậy chúng ta có thể thêm các phần tử vào cuối và xử lý hàng đợi ngay từ đầu. Những hàng đợi như vậy được gọi là hàng đợi hai chiều hay Deque trong tiếng Anh. Cuốn sách gợi ý sử dụng cấu trúc dữ liệu - bảng băm. Để tương quan tên và hàng xóm. Với các đỉnh được đánh số, bạn chỉ cần sử dụng một mảng. Việc lưu trữ các đỉnh này được gọi là “Danh sách các đỉnh liền kề”, không được đề cập trong cuốn sách. Đây là một điểm trừ đối với họ. Hãy thực hiện điều này trong 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;
}

Bây giờ, việc tìm kiếm được xây dựng dựa trên dữ liệu này:

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;
}

Như bạn có thể thấy, không có gì phức tạp. Nếu bạn so sánh nó với mã trong sách thì nó gần giống nhau.

Đồ thị, thuật toán Dijkstra

Đã hiểu ít nhiều về BFS, tác giả cuốn sách mời chúng ta tìm hiểu về thuật toán Daysktra và đồ thị có trọng số. Biểu đồ sau đây được đề xuất cho giải pháp: Đầu tiên, chúng ta cần hiểu cách biểu diễn đồ thị của mình. Chúng ta có thể biểu diễn nó dưới dạng ma trận. Một bài viết về Habré sẽ giúp chúng ta ở đây: Thuật toán Dijkstra. Tìm đường đi tối ưu trên đồ thị Hãy sử dụng ma trận kề:

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;
}

Và bây giờ chính logic:

@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);
}

Cuốn sách chia nhỏ nó ra từng bước một. Nếu bạn thêm một bài viết về Habré trên Internet + nhìn vào mã, bạn có thể nhớ nó. Tôi thấy việc phân tích từng bước hơi lộn xộn. Nhưng đối với bản chất từng bước thì đó là một điểm cộng. Nói chung là ổn, mặc dù nó có thể tốt hơn)

Thuật toán tham lam

Phần tiếp theo được dành cho “các thuật toán tham lam”. Phần này thú vị vì nó sử dụng các bộ (java.util.Set). Cuối cùng chúng ta có thể thấy tại sao nó có thể cần thiết. Chúng tôi sử dụng danh sách các trạng thái làm đầu vào:

Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));

Và cũng là danh sách các đài phát thanh phủ sóng một số tiểu bang sau:

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")));

Cuốn sách tiếp tục chỉ ra và giải thích thuật toán:

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);

Lập trình năng động

Cuốn sách cũng mô tả các vấn đề mà phương pháp tiếp cận được gọi là “lập trình động” được áp dụng. Nhiệm vụ được đưa ra: Chúng tôi có một túi 4 lb. Bạn cần tìm những mặt hàng có lợi nhất cho một trọng lượng nhất định. Đầu tiên chúng ta hãy lập danh sách các mục:

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));

Bây giờ chính thuật toán:

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));

Ngoài ra còn có một nhiệm vụ thú vị là tìm những từ giống nhau nhất. Thật thú vị phải không? Thêm chi tiết tại đây: LongestCommonSubsequence.java

Tìm kiếm hàng xóm gần nhất

Cuốn sách cũng nói rất rõ ràng về thuật toán k-hàng xóm gần nhất: Và công thức tính toán được đưa ra:

Điểm mấu chốt

Cuốn sách kết thúc bằng phần "Tiếp theo là gì?" thú vị, cung cấp tổng quan nhanh về các thuật toán thú vị. Dưới đây là mô tả ngắn gọn về ý nghĩa của cây và các thuật toán khác. Nhìn chung, tôi thích cuốn sách. Nó không nên được coi trọng như một loại thông tin toàn diện. Bạn sẽ phải tự mình tìm kiếm và hiểu rõ. Nhưng làm thông tin mang tính chất giới thiệu để gây hứng thú và đưa ra ý tưởng ban đầu thì khá hay. Có, mã trong sách được viết bằng Python. Vì vậy, tất cả các ví dụ trên đều có thể biên dịch được) Tôi hy vọng bài đánh giá này sẽ giúp bạn biết nội dung cuốn sách và liệu nó có đáng mua hay không.

Ngoài ra

Bạn cũng có thể xem các tài nguyên sau về chủ đề này:

1. EdX - Giới thiệu về lập trình Java: Thuật toán và cấu trúc dữ liệu cơ bản
2. LinkedIn - Giới thiệu về Cấu trúc dữ liệu & Thuật toán trong Java (trả phí)
3. 27 trang web có câu đố giúp rèn luyện kỹ năng lập trình của bạn
4. Mã hóa JavaBat
5. Nhiệm vụ dành cho lập trình viên, câu trả lời cho các nhiệm vụ có độ phức tạp khác nhau

#Viacheslav