Algoritmos grocking ou uma introdução indolor aos algoritmos

Resenha do livro "Algoritmos de Grocking". Um pouco de opinião pessoal, alguns exemplos. Espero que esta resenha ajude você a entender se deseja ler este livro ou se ele não ocupará seu lugar na sua estante. AVISO: Muito texto)

“Algoritmos Grocking” ou uma introdução indolor aos algoritmos

Introdução

Quase todas as vagas de nível júnior possuem requisitos como “conhecimento de estruturas de dados e algoritmos”. Para quem tem formação especializada, os algoritmos estão incluídos no curso geral e não devem haver problemas. Mas e se o desenvolvimento vier de outras estepes? Resta apenas aprender por conta própria. Há uma resposta para a pergunta “quem é o culpado”, mas para a pergunta “o que fazer” a resposta deve ser buscada. Vamos procurar nos livros. E eu quero falar sobre um.

Algoritmos Grok

Entre todos os trabalhos, me deparei com um livro como “Grocking Algorithms”. Você pode saber mais aqui: " O livro "Crescendo Algoritmos. Um guia ilustrado para programadores e curiosos ." Notei o livro há muito tempo, mas no ozônio custava 680 rublos. Caro ou barato - cada um decide por si. Já estou comprando o segundo livro no Avito pela metade do preço. Então eu o encontrei em São Petersburgo, comprei e fui grocar. Foi isso que decidi compartilhar com vocês. Sim, não há código Java no livro, mas há... outro código, mas falaremos mais sobre isso mais tarde.

Introdução aos algoritmos (classificação por seleção)

Assim, numa forma fácil de narração, chegamos à primeira ordenação em nossa performance. Esta é a classificação por seleção. A sua essência é percorrer os elementos da esquerda para a direita (do elemento 0 ao último) e procurar o maior entre os restantes elementos. Se o encontrarmos, trocamos o elemento em que estamos agora e o maior elemento. A maneira mais simples de pensar primeiro em um array é: [5, 3, 6, 2, 10]. Pegue um pedaço de papel, uma caneta (a forma mais simples e econômica) e imagine como temos uma borda esquerda, um índice atual (ou borda direita) e um índice do elemento mínimo. E como trabalhamos com isso. Por exemplo: Os algoritmos são frequentemente descritos em pseudocódigo, por exemplo, na Wikipedia. O nosso não é exatamente pseudocódigo, mas falaremos mais sobre isso mais tarde. Por enquanto vamos ver:

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

Agora vamos apresentá-lo na 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 você pode ver, o código é quase o mesmo. O primeiro código é um exemplo do livro. A segunda é minha execução gratuita em código Java.

Recursão

A seguir, somos informados de que existe algo chamado recursão. Em primeiro lugar, existe o problema de um agricultor que possui um campo de tamanho AxB. É necessário dividir este campo em “quadrados” iguais. E depois disso o Algoritmo de Euclides é mencionado. O que não gosto é que eles não tentaram escrever seu código. Mas o algoritmo de Euclides é simples e eficaz: Para ser sincero, perdi alguns detalhes do livro, como neste vídeo: “ Informática. Teoria dos algoritmos. Algoritmo de Euclides ." Por exemplo, se a for menor que b, então durante a primeira execução b e a mudarão de lugar e na segunda vez o maior será dividido pelo menor. Portanto, a ordem dos argumentos não é importante. Como sempre, primeiro podemos “sentir” o algoritmo em um pedaço de papel: Agora vamos dar uma olhada no código:

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

Vamos escrever o mesmo código em Java. Se desejar, podemos usar o compilador online :

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

Factorial também foi mencionado no início do livro. O fatorial de um número n (n!) é o produto dos números de 1 a n. Por que fazer isso? Há uma aplicação prática aqui. Se tivermos n objetos (por exemplo, n cidades), então poderemos fazer n deles! Combinações. Você pode ler mais sobre recursão aqui: “ Recursão. Tarefas de treinamento ”. Comparação de abordagens iterativas e recursivas: “ Recursão ”.

Ordenação rápida

A classificação rápida é um algoritmo bastante interessante. O livro não dá muita atenção a ele. Além disso, o código é fornecido apenas para o pior caso, quando o primeiro elemento é selecionado. No entanto, talvez para um primeiro contato este exemplo seja mais fácil de lembrar. E é melhor escrever um quicksort ruim do que não escrever nenhum. Aqui está um exemplo do livro:

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)

Tudo aqui é super simples. Se tivermos um array de 0 ou 1 elemento, não há necessidade de classificá-lo. Se for maior, pegamos o primeiro elemento do array e o consideramos o “elemento pivô”. Criamos 2 novos arrays - um contém elementos maiores que o pivô e o segundo contém elementos menores. E repetimos recursivamente. Não é a melhor opção, mas, novamente, é melhor lembrada. Vamos implementar esse algoritmo em Java, mas de forma mais correta. O material da revisão “ Ciência da Computação em JavaScript: Quicksort ” nos ajudará nisso . E antes de escrever o código, vamos desenhar novamente para “sentir” o algoritmo: Primeiro, vamos desenhar novamente em um pedaço de papel para entender o algoritmo: Parece-me que um dos momentos mais perigosos é resolver totalmente os problemas. Portanto, realizaremos a implementação em vários pequenos passos:

• Precisamos ser capazes de trocar elementos em um array:

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




• Precisamos de um método que divida o array no intervalo especificado em 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;
  }

  Detalhes no link acima. Resumindo, movemos o cursor esquerdo até que o elemento seja menor que o pivô. Da mesma forma, mova o cursor direito da outra extremidade. E fazemos uma troca se os cursores não corresponderem. Continuamos até que os cursores convirjam. Retornamos um índice que divide o processamento adicional em 2 partes.

• Há uma separação, precisamos da própria classificação:

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

  Ou seja, se o array consistir em pelo menos dois elementos, eles já poderão ser classificados. Primeiro, dividimos todo o array em duas partes, elementos menores que o pivô e elementos maiores. Em seguida, realizamos ações semelhantes para cada uma das partes resultantes.

  E para o teste:

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

O livro afirma que este algoritmo pertence aos chamados algoritmos “Dividir e Conquistar”, quando o conjunto de dados processados ​​​​é dividido ao meio a cada vez. Complexidade do algoritmo: O(nLogn) O que é ruim (ou seja, o que eu não gostei) é que o livro menciona a classificação por mesclagem de passagem, mas não fornece nenhum exemplo ou código. Mais detalhes podem ser encontrados aqui: " Informática. Algoritmos de pesquisa e classificação: Merge sort ". Portanto, por uma questão de consistência, vamos fazer isso nós mesmos. O algoritmo em si, é claro, é inerentemente simples e direto:

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 o meio e dividimos o array ao meio. Para cada metade fazemos o mesmo e assim por diante. Condição de parada ou caso base - devemos ter mais de um elemento, pois não podemos dividir um elemento em dois. Agora precisamos implementar a fusão, ou seja, mesclar:

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

Não há muito o que comentar aqui. Pelos nomes das variáveis println​​tudo fica claro. Bem, para verificar:

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

Tabelas hash

O livro também aborda tabelas hash. Você não precisa implementá-lo sozinho, e a essência das tabelas hash é bastante simples. Afinal, Java também possui uma implementação de tabelas hash, java.util.HashTable. Se olharmos para o dispositivo HashTable, veremos que o array Entry reside dentro dele. Entrada é um registro que é uma combinação de Chave – Valor. HashTable possui inicialCapacity - ou seja, o tamanho inicial. E loadFactor – fator de carga. O padrão é 0,75. Este número informa em qual carga da matriz (número de elementos/número total) o tamanho precisa ser aumentado. Em Java aumenta 2 vezes. O livro explica que as tabelas hash são chamadas de tabelas hash porque, com base na função hash, a célula da matriz (cesta) na qual o arquivo Entry. Você também pode ler mais aqui: Estruturas de dados em imagens. HashMap e LinkedHashMap . Você também pode ler isso em livros. Por exemplo aqui: " Noções básicas de HashTable "

Gráficos, pesquisa em amplitude (pesquisa de caminho mais curto)

Provavelmente um dos tópicos mais interessantes são os gráficos. E aqui, para ser justo, o livro dá muita atenção a eles. Talvez por isso valha a pena ler este livro. Embora, talvez, pudesse ter sido dito um pouco mais claramente)) Mas, temos a Internet e além do livro, você pode conferir esta playlist sobre teoria para “aqueles que estão ouvindo falar de gráficos pela primeira vez . ” Bem, naturalmente, logo no início do livro, breadth-first-searché fornecido o algoritmo de busca em largura, também conhecido como BFS. O livro contém o seguinte gráfico: O livro afirma que uma fila nos ajudará. Além disso, podemos adicionar elementos ao final e processar a fila desde o início. Essas filas são chamadas de filas bidirecionais ou Deque em inglês. O livro sugere o uso de uma estrutura de dados - uma tabela hash. Para correlacionar o nome e os vizinhos. Com vértices numerados, você pode simplesmente usar um array. Esse armazenamento de vértices é chamado de “Lista de vértices adjacentes”, que não é mencionado no livro. Isso é um sinal de menos para eles. Vamos implementar isso em 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;
}

Agora a pesquisa em si, baseada nestes dados:

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 você pode ver, nada complicado. Se você comparar com o código do livro, é quase a mesma coisa.

Gráficos, Algoritmo de Dijkstra

Tendo compreendido mais ou menos o BFS, o autor do livro nos convida a compreender o algoritmo Daysktra e os gráficos ponderados. O seguinte gráfico é proposto para a solução: Primeiro, precisamos entender como representar nossos gráficos. Poderíamos representá-lo como uma matriz. Um artigo sobre Habré nos ajudará aqui: o algoritmo de Dijkstra. Encontrando rotas ótimas em um gráfico . Vamos usar a matriz de adjacência:

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 agora a própria lógica:

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

O livro explica tudo passo a passo. Se você adicionar um artigo sobre Habré na Internet + olhar o código, você poderá se lembrar dele. Achei a análise passo a passo um pouco confusa. Mas para a própria natureza passo a passo é uma vantagem. No geral, ok, embora pudesse ter sido melhor)

Algoritmos gananciosos

A próxima seção é dedicada a “algoritmos gananciosos”. Esta seção é interessante porque usa conjuntos (java.util.Set). Finalmente podemos ver por que isso pode ser necessário. Usamos uma lista de estados como entrada:

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

E também uma lista de estações de rádio que cobrem alguns desses 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")));

O livro continua apontando e explicando o algoritmo em si:

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

Programaçao dinamica

O livro também descreve problemas aos quais é aplicada uma abordagem chamada “programação dinâmica”. A tarefa é dada: Temos um saco de 4kg. Você precisa encontrar os itens mais lucrativos para um determinado peso. Primeiro, vamos fazer uma lista de itens:

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

Agora o algoritmo em si:

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

Há também uma tarefa interessante para encontrar as palavras mais semelhantes. Interessante, não é? Mais detalhes aqui: LongestCommonSubsequence.java

Procure os vizinhos mais próximos

O livro também fala claramente sobre o algoritmo dos k-vizinhos mais próximos: E a fórmula de cálculo é dada:

Resultado final

O livro termina com uma seção interessante “O que vem a seguir?”, que fornece uma rápida visão geral de algoritmos interessantes. Aqui está uma breve descrição do significado das árvores e outros algoritmos. No geral, gostei do livro. Não deve ser levado a sério como algum tipo de informação abrangente. Você terá que pesquisar e entender por si mesmo. Mas como informação introdutória para interessar e dar uma ideia inicial, é muito boa. Sim, o código do livro está escrito em Python. Portanto, todos os exemplos acima são compiláveis. Espero que esta resenha ajude você a ter uma ideia do que o livro contém e se vale a pena comprá-lo.

Adicionalmente

Você também pode verificar os seguintes recursos sobre este tópico:

1. EdX - Introdução à Programação Java: Estruturas de Dados e Algoritmos Fundamentais
2. LinkedIn - Introdução a estruturas de dados e algoritmos em Java (pago)
3. 27 sites com quebra-cabeças para aprimorar suas habilidades de programação
4. Codificação Java Bat
5. Tarefas para programadores, respostas para tarefas de complexidade variada

#Viacheslav