Algoritmos grocking o una introducción indolora a los algoritmos

Reseña del libro "Algoritmos de Grocking". Una pequeña opinión personal, algunos ejemplos. Espero que esta reseña le ayude a comprender si desea leer este libro o si no ocupará su lugar en su estantería. ADVERTENCIA: Mucho texto)

“Algoritmos en crecimiento” o una introducción sencilla a los algoritmos

Introducción

Casi cualquier vacante de nivel Junior tiene requisitos como "conocimiento de estructuras de datos y algoritmos". Para quienes tienen una formación especializada, los algoritmos están incluidos en el curso general y no debería haber problemas. ¿Pero qué pasaría si el desarrollo procediera de otras estepas? Todo lo que queda es aprender por tu cuenta. Hay una respuesta a la pregunta "quién tiene la culpa", pero a la pregunta "qué hacer" hay que buscarla. Miremos en los libros. Y quiero hablarles de uno.

Algoritmos de Grok

Entre todos los trabajos, encontré un libro llamado "Algoritmos de Grocking". Puede encontrar más información aquí: " El libro "Algoritmos de crecimiento. Una guía ilustrada para programadores y curiosos ". Me di cuenta del libro hace mucho tiempo, pero con ozono cuesta 680 rublos. Caro o barato: cada uno decide por sí mismo. Ya estoy comprando el segundo libro sobre Avito por la mitad de precio. Así que lo encontré en San Petersburgo, lo compré y me puse a asimilarlo. Que es lo que decidí compartir contigo. Sí, no hay código Java en el libro, pero hay... otro código, pero hablaremos de eso más adelante.

Introducción a los algoritmos (ordenación por selección)

Así, en una forma fácil de narración, llegamos al primer orden de nuestra actuación. Esta es la clasificación por selección. Su esencia es que recorremos los elementos de izquierda a derecha (desde el elemento 0 hasta el último), y buscamos el más grande entre los elementos restantes. Si lo encontramos, intercambiamos el elemento en el que nos encontramos ahora y el elemento más grande. La forma más sencilla de pensar primero en una matriz es: [5, 3, 6, 2, 10]. Tome una hoja de papel, un bolígrafo (la forma más sencilla y rentable) e imagine cómo tenemos un borde izquierdo, un índice actual (o borde derecho) y un índice del elemento mínimo. Y cómo trabajamos con ello. Por ejemplo: Los algoritmos a menudo se describen en pseudocódigo, por ejemplo, en Wikipedia. El nuestro no es exactamente un pseudocódigo, pero hablaremos de eso más adelante. Por ahora veamos:

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

Ahora presentémoslo en forma de código 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;
            }
        }
}

Como puede ver, el código es casi el mismo. El primer código es un ejemplo del libro. El segundo es mi ejecución gratuita en código Java.

recursividad

A continuación se nos dice que existe la recursividad. En primer lugar, existe el problema de un agricultor que tiene un campo de tamaño AxB. Es necesario dividir este campo en “cuadrados” iguales. Y luego de esto se menciona el algoritmo de Euclides. Lo que no me gusta es que no intentaron escribir su código. Pero el algoritmo de Euclides es simple y eficaz: Para ser honesto, me perdí algunos detalles del libro, como en este video: “ Informática. Teoría de los algoritmos. El algoritmo de Euclides ." Por ejemplo, si a es menor que b, entonces durante la primera ejecución b y a cambiarán de lugar y la segunda vez el más grande se dividirá entre el más pequeño. Por tanto, el orden de los argumentos no es importante. Como es habitual, primero podemos “sentir” el algoritmo en una hoja de papel: Ahora veamos el código:

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

Escribamos el mismo código en Java. Si lo deseamos, podemos utilizar el compilador en línea :

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

Factorial también fue mencionado al principio del libro. El factorial de un número n (n!) es el producto de los números del 1 al n. ¿Por qué hacer esto? Aquí hay una aplicación práctica. Si tenemos n objetos (por ejemplo, n ciudades), ¡podemos hacer n con ellos! Combinaciones. Puede leer más sobre la recursividad aquí: " Recursividad. Tareas de entrenamiento ". Comparación de enfoques iterativos y recursivos: " Recursión ".

Ordenación rápida

La clasificación rápida es un algoritmo bastante interesante. El libro no le presta mucha atención. Además, el código se proporciona sólo para el peor de los casos, cuando se selecciona el primer elemento. Sin embargo, quizás para un primer contacto este ejemplo sea más fácil de recordar. Y es mejor escribir una mala clasificación rápida que no escribir ninguna. Aquí hay un ejemplo del 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)

Todo aquí es súper simple. Si tenemos una matriz de 0 o 1 elemento, no es necesario ordenarla. Si es mayor, tomamos el primer elemento de la matriz y lo consideramos el "elemento pivote". Creamos 2 matrices nuevas: una contiene elementos más grandes que el pivote y la segunda contiene elementos más pequeños. Y repetimos recursivamente. No es la mejor opción, pero nuevamente, es mejor recordarla. Implementemos este algoritmo en Java, pero de forma más correcta. El material de la revisión " Informática en JavaScript: Quicksort " nos ayudará con esto . Y antes de escribir el código, volvamos a dibujar para “sentir” el algoritmo: Primero, volvamos a dibujar en una hoja de papel para entender el algoritmo: Me parece que uno de los momentos más peligrosos es resolver los problemas por completo. Por tanto, realizaremos la implementación en varios pequeños pasos:

• Necesitamos poder intercambiar elementos en una matriz:

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




• Necesitamos un método que divida la matriz en el intervalo especificado en 3 partes

  
  

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

  Detalles en el enlace de arriba. En resumen, movemos el cursor izquierdo hasta que el elemento sea menor que el pivote. De manera similar, mueva el cursor derecho desde el otro extremo. Y hacemos un intercambio si los cursores no coinciden. Seguimos hasta que los cursores converjan. Devolvemos un índice que divide el procesamiento posterior en 2 partes.

• Hay una separación, necesitamos la clasificación en sí:

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

  Es decir, si la matriz consta de al menos dos elementos, entonces ya se pueden ordenar. Primero, dividimos toda la matriz en dos partes, elementos más pequeños que el pivote y elementos más grandes. Luego realizamos acciones similares para cada una de las partes resultantes.

  Y para la prueba:

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

El libro afirma que este algoritmo pertenece a los llamados algoritmos "divide y vencerás", cuando el conjunto de datos procesados ​​se divide por la mitad cada vez. Complejidad del algoritmo: O (nLogn) Lo malo (es decir, lo que no me gustó) es que el libro menciona la ordenación por fusión de pasada, pero no proporciona ningún ejemplo ni código. Se pueden encontrar más detalles aquí: " Informática. Algoritmos de búsqueda y clasificación: clasificación por combinación ". Por lo tanto, en aras de la coherencia, hagámoslo nosotros mismos. El algoritmo en sí, por supuesto, es inherentemente simple y directo:

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

Determinamos el medio y dividimos la matriz por la mitad. Para cada mitad hacemos lo mismo y así sucesivamente. Condición de parada o caso base: debemos tener más de un elemento, ya que no podemos dividir un elemento en dos. Ahora necesitamos implementar la fusión, es decir, fusionar:

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

No hay mucho que comentar aquí. Por los nombres de las variables printlntodo queda claro. Bueno, para comprobar:

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

tablas hash

El libro también aborda las tablas hash. No es necesario que las implemente usted mismo y la esencia de las tablas hash es bastante simple. Después de todo, Java también tiene una implementación de tablas hash, java.util.HashTable. Si miramos el dispositivo HashTable, veremos que la matriz Entry se encuentra en su interior. La entrada es un registro que es una combinación de Clave – Valor. HashTable tiene capacidad inicial, es decir, el tamaño inicial. Y loadFactor – factor de carga. El valor predeterminado es 0,75. Este número le indica a qué carga de la matriz (número de elementos/número total) se debe aumentar el tamaño. En Java aumenta 2 veces. El libro explica que las tablas Hash se llaman tablas hash porque, según la función hash, la celda de la matriz (cesta) en la que se encuentra el archivo Entry. También puedes leer más aquí: Estructuras de datos en imágenes. HashMap y LinkedHashMap . También puedes leerlo en libros. Por ejemplo aquí: " Conceptos básicos de HashTable "

Gráficos, búsqueda en amplitud (búsqueda de ruta más corta)

Probablemente uno de los temas más interesantes sean los gráficos. Y aquí, para ser justos, el libro les presta mucha atención. Quizás por eso vale la pena leer este libro. Aunque, tal vez, podría haberse dicho un poco más claramente)) Pero tenemos Internet y, además del libro, puedes consultar esta lista de reproducción sobre teoría para "aquellos que escuchan sobre gráficos por primera vez ". " Bueno, naturalmente, al principio del libro, breadth-first-searchse proporciona el algoritmo de búsqueda en amplitud, también conocido como BFS. El libro contiene el siguiente gráfico: El libro afirma que una cola nos ayudará. Además, de modo que podamos agregar elementos al final y procesar la cola desde el principio. Estas colas se denominan colas de dos vías o Deque en inglés. El libro sugiere utilizar una estructura de datos: una tabla hash. Correlacionar el nombre y los vecinos. Con vértices numerados, simplemente puedes usar una matriz. Este almacenamiento de vértices se denomina "Lista de vértices adyacentes", que no se menciona en el libro. Esto es un inconveniente para ellos. Implementemos esto en 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;
}

Ahora la búsqueda en sí, basada en estos datos:

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

Como puedes ver, nada complicado. Si lo comparas con el código del libro, es casi lo mismo.

Gráficos, algoritmo de Dijkstra.

Habiendo entendido más o menos BFS, el autor del libro nos invita a comprender el algoritmo Daysktra y los gráficos ponderados. Para la solución se propone el siguiente gráfico: Primero, necesitamos entender cómo representar nuestras gráficas. Podríamos representarlo como una matriz. Un artículo sobre Habré nos ayudará aquí: el algoritmo de Dijkstra. Encontrar rutas óptimas en un gráfico . Usemos la matriz de adyacencia:

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

Y ahora la lógica misma:

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

El libro lo desglosa paso a paso. Si agrega un artículo sobre Habré en Internet + mira el código, podrá recordarlo. El análisis paso a paso me pareció un poco desordenado. Pero por la propia naturaleza paso a paso es una ventaja. En general bien, aunque podría haber sido mejor)

Algoritmos codiciosos

La siguiente sección está dedicada a los "algoritmos codiciosos". Esta sección es interesante porque utiliza conjuntos (java.util.Set). Finalmente podemos ver por qué podría ser necesario. Usamos una lista de estados como entrada:

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

Y también una lista de estaciones de radio que cubren algunos de estos estados:

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

El libro continúa señalando y explicando el algoritmo en sí:

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

Programación dinámica

El libro también describe problemas a los que se aplica un enfoque llamado "programación dinámica". Se da la tarea: Disponemos de una bolsa de 4 libras. Necesita encontrar los artículos más rentables para un peso determinado. Primero, hagamos una lista de elementos:

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

Ahora el algoritmo en sí:

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

También existe una tarea interesante para encontrar las palabras más similares. Interesante, ¿no? Más detalles aquí: LongestCommonSubsequence.java

Buscar vecinos más cercanos

El libro también habla muy claramente sobre el algoritmo de k vecinos más cercanos: Y se da la fórmula para el cálculo:

Línea de fondo

El libro termina con una interesante sección "¿Qué sigue?", que proporciona una descripción general rápida de algoritmos interesantes. A continuación se ofrece una breve descripción de cuál es el significado de los árboles y otros algoritmos. En general, me gustó el libro. No debe tomarse en serio como una especie de información completa. Tendrás que buscar y comprender por ti mismo. Pero como dato introductorio para interesar y dar una idea inicial, está bastante bien. Sí, el código del libro está escrito en Python. Por lo tanto, todos los ejemplos anteriores son compilables). Espero que esta reseña le ayude a tener una idea de lo que contiene el libro y si vale la pena comprarlo.

Además

También puede consultar los siguientes recursos sobre este tema:

1. EdX - Introducción a la programación Java: estructuras de datos y algoritmos fundamentales
2. LinkedIn - Introducción a estructuras de datos y algoritmos en Java (pago)
3. 27 sitios con acertijos para perfeccionar tus habilidades de programación
4. Codificación JavaBat
5. Tareas para programadores, respuestas a tareas de diversa complejidad.

#viacheslav