Algunas compañías entrevistan el código de escritura en línea. Es necesario resolver el problema de la olimpiada para la velocidad. En tales circunstancias, no hay tiempo para ver los detalles de la implementación de estructuras de datos; debe darse cuenta de inmediato de la idea. Pero los cursos sobre algoritmos y estructuras de datos proporcionan ejemplos en pseudocódigo o C ++. A menudo se escriben más soluciones de referencia a los problemas en C ++. Preparándome para una entrevista, hice una cuna de bibliotecas, análogos de contenedores STL, para no perder un tiempo precioso buscando.
Comencemos con lo obvio.
Matriz continua dinámica
Analog
std::vector .
Admite el acceso a un elemento por índice durante un tiempo constante de varios ciclos de procesador. Puede aumentar o disminuir la capacidad. Este es el segmento incorporado:
vector := []int{}
Convenientemente, los conceptos básicos están integrados en el lenguaje.
Análogo de
std::stack .
Un conjunto ordenado en el que agregar elementos nuevos y eliminar los existentes se realiza desde un extremo. El elemento que se colocó en último lugar (último en entrar, primero en salir - LIFO) se elimina primero de la pila. Esta es nuevamente una rebanada amurallada. Los fragmentos se copian de proyecto a proyecto:
La operación de división no asigna una nueva memoria.
Análogo de
std::queue y
std::deque .
Las colas implementan operaciones de recuperación y adición para iniciar y finalizar en tiempo constante. El elemento que se colocó primero (primero en entrar, primero en salir - FIFO) se elimina primero de la cola. Un canal almacenado en una memoria intermedia es una cola en un búfer en anillo, puede usarlo cuando el lector y el escritor son diferentes rutinas. Pero no hay una implementación de cola separada en la biblioteca estándar. La lista
awesome-go aconseja a la biblioteca
https://github.com/gammazero/deque .
import "github.com/gammazero/deque"
Operaciones en curso:
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 doblemente vinculada
Análogo a
std::list .
Se compone de elementos que contienen, además de sus propios datos, enlaces al elemento de la lista siguiente y anterior. Está en la biblioteca estándar:
import "container/list"
Como se esperaba, admite operaciones de inserción (al principio, al final, antes y después del elemento, el puntero al que se pasa) y eliminación.
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{}
Go no proporciona una sintaxis específica para los iteradores. Por lo tanto, el elemento siguiente / anterior se puede obtener de un puntero a cualquier nodo. Estos métodos no salen mal después de agregar / eliminar un elemento de la lista, sin sorpresas.
func (e *Element) Next() *Element func (e *Element) Prev() *Element
Cola de prioridad
Analog
std::priority_queueLe permite apilar elementos en cualquier orden y obtener en cualquier momento la máxima prioridad del resto. Se utiliza, por ejemplo, en el algoritmo para construir un árbol de expansión mínimo, cuando, en el siguiente paso, el algoritmo selecciona el borde más corto de todos comenzando en los vértices ya cubiertos en un extremo.
La biblioteca estándar tiene un adaptador que convierte cualquier contenedor ordenable (que implementa
sort.Interface ) en una cola prioritaria.
import "container/heap"
Este es un
montón binario clásico. Implementa inserción y eliminación en O (log n).
func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{}
Es un diccionario y una matriz asociativa.
Analog
std::unordered_map .
Le permite agregar un valor clave, eliminar el valor por clave y verificar la presencia de un elemento para O (1) en promedio. Obviamente, el mapa está integrado en el lenguaje:
unorderedMap := make(map[string]int)
El resultado de make (map) es un puntero, y la forma en que funciona es ligeramente diferente de los contenedores estándar:
"Runtime / map", a diferencia de std :: unordered_map, se encarga del programador; es seguro eliminar valores durante la iteración.
Muchos
Analog
std::unordered_set .
Casi lo mismo que una tabla hash, pero sin guardar el valor.
Si solo necesitamos una verificación de entrada rápida, entonces podemos usar el mapa incorporado nuevamente. Solo es necesario especificar un valor vacío para indicar que solo la clave es importante.
var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"]
Pero esta implementación no admite operadores complejos. Para fusionar, intersecar, la diferencia con el cuadro, necesita bibliotecas de terceros. Más utilizado, a juzgar por el número de estrellas:
https://github.com/deckarep/golang-set import "github.com/deckarep/golang-set"
La parte más necesaria de la
API :
Add(i interface{}) bool Remove(i interface{}) Cardinality() int
Establecer int
En la parte experimental de la biblioteca estándar hay un conjunto optimizado int que guarda cada bit.
import "golang.org/x/tools/container/intsets"
También admite unión, intersección, diferencia de conjuntos.
Análogos
std::set y
std::map .
Puede parecer un novato análogos malos de tablas hash:
también admite agregar, eliminar y verificar ocurrencias, pero más allá de O (log n).
Pero los árboles almacenan nodos ordenados por clave.
No hay árboles en la biblioteca go estándar, se utiliza ampliamente un
repositorio que contiene AVL, Rojo-Negro y B-trees.
import "github.com/emirpasic/gods/trees/avltree"
Métodos
API más utilizados:
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
Hay dos métodos de árbol particularmente importantes:
func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool)
devuelve el elemento existente más pequeño más grande que la clave.
func (tree *Tree) Floor(key interface{}) (floor *Node, found bool)
devuelve el elemento existente más grande menos que una clave.
Las tareas para esto se encuentran relativamente a menudo en las entrevistas. En la vida real se usa en índices de bases de datos:
select x from table where x <= $1 limit 1;
Si hay un índice, funcionará para O (log n), para 1 búsqueda del borde en el árbol B.
Pero esta estructura de datos en stl no lo es.
Al igual que una tabla hash, le permite verificar si un elemento pertenece a un conjunto. Pero el filtro no almacena claves al agregar, y toma una cantidad constante de memoria. Es posible recibir una respuesta falsa positiva (no hay ningún elemento en el conjunto, pero la estructura de datos informa que sí), pero no falso negativo. Se utiliza como filtro para cortar rápidamente casi todas las claves no existentes, lo que ahorra una verificación más costosa, por ejemplo, leer desde un disco o realizar una solicitud a la base de datos.
Hay una biblioteca de terceros:
https://github.com/willf/bloom import "github.com/willf/bloom"
No se usa con tanta frecuencia, puede echar un vistazo a la
API .
No existe tal cosa en la biblioteca estándar de C ++.
Estructura de datos probabilística. Con un pequeño error (≈ 0.4%), considera el número de elementos únicos sin almacenar las claves. Proporciona grandes ahorros de memoria. Si la tarea es calcular rápidamente la cantidad de visitantes o solicitudes, HyperLogLog es ideal.
La biblioteca más popular para esto ahora.
https://github.com/axiomhq/hyperloglog import "github.com/axiomhq/hyperloglog"
Clasificaciones
Análogos
std::sort y
std::stable_sort .
Desde el punto de vista del consumidor, solo hay 2 tipos fundamentalmente diferentes:
Estable (no cambie el orden de los elementos iguales [[4, 0], [1, 2], [1, 1], [5, 6]] -> [[1, 2], [1, 1], [4 , 0], [5, 6]])
y no es estable, no garantiza la consistencia de los campos restantes.
Ambos están en la biblioteca estándar:
func Sort(data Interface)
Esta es una implementación rápida de Hoar, inestable. Pero para las secciones de longitud <12, la ordenación del montón se utiliza como optimización.
func Stable(data Interface)
En el interior, este es un tipo de fusión, pero para mayor eficiencia, cuando el algoritmo recursivo alcanza bloques de menos de 20 elementos, se utiliza el orden de inserción.
Estos son los algoritmos clásicos que funcionan para O (n log n).
Si lo lees, felicidades. Conocer API específicas ayuda a resolver problemas de prueba. (Si trabajó con algo y conoce las mejores alternativas, escriba en los comentarios.