Algumas empresas entrevistam código de escrita online. É necessário resolver o problema das olimpíadas para obter velocidade. Nessas circunstâncias, não há tempo para ver os detalhes da implementação das estruturas de dados - você precisa realizar a ideia imediatamente. Mas os cursos sobre algoritmos e estruturas de dados fornecem exemplos em pseudo-código ou C ++. Muitas vezes, soluções de referência para problemas são escritas em C ++. Preparando-me para uma entrevista, fiz um berço de bibliotecas - análogos de contêineres da STL, para não perder tempo precioso pesquisando.
Vamos começar com o óbvio.
Matriz contínua dinâmica
std::vector analógico
std::vector .
Oferece suporte ao acesso a um elemento por índice por um tempo constante de vários ciclos do processador. Você pode aumentar ou diminuir a capacidade. Esta é a fatia interna:
vector := []int{}
Convenientemente, conceitos básicos são incorporados à linguagem.
Análogo de
std::stack .
Um conjunto ordenado no qual a adição de novos elementos e a exclusão dos existentes é feita a partir de uma extremidade. O elemento que foi colocado por último (último a entrar, primeiro a sair - LIFO) é removido primeiro da pilha. Esta é novamente uma fatia murada. Os trechos são copiados de um projeto para outro:
A operação de fatia não aloca uma nova memória.
Análogo de
std::queue e
std::deque .
As filas implementam operações de recuperação e adição para iniciar e terminar em tempo constante. O elemento que foi colocado primeiro (primeiro a entrar, primeiro a sair - FIFO) é excluído primeiro da fila. Um canal em buffer é uma fila em um buffer em anel; você pode usá-lo quando o leitor e o gravador são goroutines diferentes. Mas não há implementação de fila separada na biblioteca padrão. A lista
impressionante inclui a biblioteca
https://github.com/gammazero/deque .
import "github.com/gammazero/deque"
Operações em andamento:
func (q *Deque) PushBack(elem interface{}) func (q *Deque) PushFront(elem interface{}) func (q *Deque) PopBack() interface{} func (q *Deque) PopFront() interface{} func (q *Deque) Back() interface{} func (q *Deque) Front() interface{} func (q *Deque) At(i int) interface{}
Lista duplamente vinculada
Análogo ao
std::list .
Consiste em elementos que contêm, além de seus próprios dados, links para o item de lista seguinte e anterior. Está na biblioteca padrão:
import "container/list"
Como esperado, ele suporta operações de inserção (no início, no final, antes e depois do elemento, cujo ponteiro é passado) e exclusão.
func (l *List) PushBack(v interface{}) *Element func (l *List) PushFront(v interface{}) *Element func (l *List) InsertAfter(v interface{}, mark *Element) *Element func (l *List) InsertBefore(v interface{}, mark *Element) *Element func (l *List) Remove(e *Element) interface{}
O Go não fornece sintaxe específica para iteradores. Portanto, o elemento próximo / anterior pode ser obtido de um ponteiro para qualquer nó. Esses métodos não dão errado depois de adicionar / remover um item da lista, sem surpresas.
func (e *Element) Next() *Element func (e *Element) Prev() *Element
Fila prioritária
Analógico
std::priority_queuePermite empilhar itens em qualquer ordem e obter a qualquer momento a maior prioridade do restante. É usado, por exemplo, no algoritmo para a construção de uma árvore de abrangência mínima, quando na próxima etapa o algoritmo seleciona a borda mais curta de todas, iniciando nos vértices já cobertos em uma extremidade.
A biblioteca padrão possui um adaptador que transforma qualquer contêiner classificável (que implementa
sort.Interface ) em uma fila prioritária.
import "container/heap"
Esta é uma
pilha binária clássica. Implementa inserção e exclusão em O (log n).
func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{}
É um dicionário e uma matriz associativa.
Analógico
std::unordered_map .
Permite adicionar um valor-chave, excluir o valor por chave e verificar a presença de um elemento para O (1) em média. Obviamente, o mapa está embutido no idioma:
unorderedMap := make(map[string]int)
O resultado do make (map) é um ponteiro e a maneira como funciona é um pouco diferente dos contêineres padrão:
"Tempo de execução / mapa", diferentemente de std :: unordered_map, cuida do programador - é seguro excluir valores durante a iteração.
Muitos
Analógico
std::unordered_set .
Quase o mesmo que uma tabela de hash, mas sem salvar o valor.
Se precisarmos apenas de uma verificação rápida de entrada, poderemos usar o mapa interno novamente. Só é necessário especificar um valor vazio para indicar que apenas a chave é importante.
var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"]
Mas essa implementação não oferece suporte a operadores complexos. Para mesclar, cruzar, a diferença da caixa, você precisa de bibliotecas de terceiros. Mais usado, a julgar pelo número de estrelas:
https://github.com/deckarep/golang-set import "github.com/deckarep/golang-set"
A parte mais necessária da
API :
Add(i interface{}) bool Remove(i interface{}) Cardinality() int
Definir int
Na parte experimental da biblioteca padrão, há um conjunto otimizado int que salva todos os bits.
import "golang.org/x/tools/container/intsets"
Ele também suporta união, interseção, diferença de conjuntos.
Análogos
std::set e
std::map .
Pode parecer um novato análogos ruins de tabelas de hash:
também suporta adição, remoção e verificação de ocorrências, mas além de O (log n).
Mas as árvores armazenam nós classificados por chave.
Não há árvores na biblioteca padrão, um
repositório contendo AVL, Vermelho-Preto e Árvores B é amplamente utilizado.
import "github.com/emirpasic/gods/trees/avltree"
Métodos de
API mais usados:
func (tree *Tree) Get(key interface{}) (value interface{}, found bool) func (tree *Tree) Put(key interface{}, value interface{}) func (tree *Tree) Remove(key interface{}) func (tree *Tree) Size() int func (tree *Tree) Keys() []interface{} func (tree *Tree) Values() []interface{} func (tree *Tree) Left() *Node func (tree *Tree) Right() *Node
Existem dois métodos de árvore particularmente importantes:
func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool)
retorna o menor item existente maior que a chave.
func (tree *Tree) Floor(key interface{}) (floor *Node, found bool)
retorna o maior elemento existente menos que uma chave.
As tarefas para isso são encontradas com relativa frequência nas entrevistas. Na vida real, é usado em índices de banco de dados:
select x from table where x <= $1 limit 1;
Se houver um índice, ele funcionará para O (log n), para 1 pesquisa pela borda na árvore B.
Mas essa estrutura de dados no stl não é.
Como uma tabela de hash, permite verificar se um elemento pertence a um conjunto. Mas o filtro não armazena chaves ao adicionar e consome uma quantidade constante de memória. É possível receber uma resposta positiva falsa (não há elemento no conjunto, mas a estrutura de dados informa que é), mas não é falso negativo. Ele é usado como um filtro para eliminar rapidamente quase todas as chaves inexistentes, economizando verificações mais caras, por exemplo, lendo em um disco ou fazendo uma solicitação ao banco de dados.
Há uma biblioteca de terceiros:
https://github.com/willf/bloom import "github.com/willf/bloom"
Não é usado com tanta frequência, você pode espiar a
API .
Não existe tal coisa na biblioteca C ++ padrão.
Estrutura probabilística de dados. Com um pequeno erro (± 0,4%), considera o número de elementos únicos sem armazenar as chaves. Ele oferece uma enorme economia de memória. Se a tarefa é calcular rapidamente o número de visitantes ou solicitações - o HyperLogLog é ideal.
A biblioteca mais popular para isso agora.
https://github.com/axiomhq/hyperloglog import "github.com/axiomhq/hyperloglog"
Classificações
Análogos
std::sort e
std::stable_sort .
Do ponto de vista do consumidor, existem apenas 2 tipos fundamentalmente diferentes:
Estável (não altere a ordem dos elementos iguais [[4, 0], [1, 2], [1, 1], [5, 6]] -> [[1, 2], [1, 1], [4 , 0], [5, 6]])
e não estável, não garantindo a consistência dos campos restantes.
Ambos estão na biblioteca padrão:
func Sort(data Interface)
Esta é uma implementação do quicksort Hoar, instável. Porém, para seções de tamanho <12, a classificação de heap é usada como otimização.
func Stable(data Interface)
Por dentro, essa é uma classificação por mesclagem, mas, para eficiência, quando o algoritmo recursivo atinge blocos com menos de 20 elementos, a classificação por inserção é usada.
Estes são os algoritmos clássicos que trabalham para O (n log n).
Se você ler, parabéns. Conhecer APIs específicas ajuda a resolver problemas de teste. (Se você trabalhou com alguma coisa e conhece as melhores alternativas - escreva nos comentários.