Certaines entreprises interrogent l'écriture de code en ligne. Il est nécessaire pour résoudre le problème de l'olympiade pour la vitesse. Dans de telles circonstances, il n'y a pas de temps pour voir les détails de la mise en œuvre des structures de données - vous devez réaliser immédiatement l'idée. Mais les cours sur les algorithmes et les structures de données fournissent des exemples en pseudo-code ou en C ++. D'autres solutions de référence aux problèmes sont souvent écrites en C ++. En me préparant pour une interview, j'ai fait un berceau de bibliothèques - analogues de conteneurs STL, afin de ne pas perdre un temps précieux à chercher.
Commençons par l'évidence.
Réseau continu dynamique
std::vector analogique
std::vector .
Prend en charge l'accès à un élément par index pendant un temps constant de plusieurs cycles de processeur. Vous pouvez augmenter ou diminuer la capacité. Voici la tranche intégrée:
vector := []int{}
Idéalement, les concepts de base sont intégrés dans le langage.
Analogue de
std::stack .
Un ensemble ordonné dans lequel l'ajout de nouveaux éléments et la suppression de ceux existants se fait d'un bout à l'autre. L'élément qui a été placé en dernier (dernier entré, premier sorti - LIFO) est supprimé en premier de la pile. C'est encore une tranche fortifiée. Les extraits sont copiés d'un projet à l'autre:
L'opération de tranche n'alloue pas de nouvelle mémoire.
Analogue de
std::queue et
std::deque .
Les files d'attente implémentent des opérations de récupération et d'ajout pour le début et la fin en temps constant. L'élément qui a été placé en premier (premier entré, premier sorti - FIFO) est supprimé en premier de la file d'attente. Un canal tamponné est une file d'attente sur un tampon en anneau, vous pouvez l'utiliser lorsque le lecteur et l'écrivain sont des goroutines différents. Mais il n'y a pas d'implémentation de file d'attente séparée dans la bibliothèque standard. La liste
awesome-go conseille la bibliothèque
https://github.com/gammazero/deque .
import "github.com/gammazero/deque"
Opérations en cours:
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{}
Liste doublement liée
Analogue à
std::list .
Il se compose d'éléments contenant, en plus de leurs propres données, des liens vers l'élément de liste suivant et précédent. C'est dans la bibliothèque standard:
import "container/list"
Comme prévu, il prend en charge les opérations d'insertion (au début, à la fin, avant et après l'élément dont le pointeur est passé) et la suppression.
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 ne fournit pas de syntaxe spécifique pour les itérateurs. Par conséquent, l'élément suivant / précédent peut être obtenu à partir d'un pointeur vers n'importe quel nœud. Ces méthodes ne vont pas mal après l'ajout / la suppression d'un élément à la liste, sans surprise.
func (e *Element) Next() *Element func (e *Element) Prev() *Element
File d'attente prioritaire
Analog
std::priority_queueVous permet d'empiler des éléments dans n'importe quel ordre et d'obtenir à tout moment la priorité la plus élevée des autres. Il est utilisé, par exemple, dans l'algorithme de construction d'un arbre couvrant minimal, lorsque, à l'étape suivante, l'algorithme sélectionne le bord le plus court de tous en commençant par les sommets déjà couverts à une extrémité.
La bibliothèque standard possède un adaptateur qui transforme n'importe quel conteneur triable (qui implémente
sort.Interface ) en file d'attente prioritaire.
import "container/heap"
Il s'agit d'un
tas binaire classique. Implémente l'insertion et la suppression dans O (log n).
func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{}
Il s'agit d'un dictionnaire et d'un tableau associatif.
Analog
std::unordered_map .
Vous permet d'ajouter une valeur-clé, de supprimer la valeur par clé et de vérifier la présence d'un élément pour O (1) en moyenne. De toute évidence, la carte est intégrée dans le langage:
unorderedMap := make(map[string]int)
Le résultat de make (map) est un pointeur, et son fonctionnement est légèrement différent des conteneurs standard:
"Runtime / map", contrairement à std :: unordered_map, prend soin du programmeur - il est sûr de supprimer des valeurs pendant l'itération.
Beaucoup
Analog
std::unordered_set .
Presque la même chose qu'une table de hachage, mais sans enregistrer la valeur.
Si nous n'avons besoin que d'une vérification d'entrée rapide, nous pouvons à nouveau utiliser la carte intégrée. Il suffit de spécifier une valeur vide pour indiquer que seule la clé est importante.
var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"]
Mais cette implémentation ne prend pas en charge les opérateurs complexes. Pour fusionner, recouper, la différence de la boîte, vous avez besoin de bibliothèques tierces. Le plus utilisé, à en juger par le nombre d'étoiles:
https://github.com/deckarep/golang-set import "github.com/deckarep/golang-set"
La partie la plus nécessaire de l'
API :
Add(i interface{}) bool Remove(i interface{}) Cardinality() int
Définir int
Dans la partie expérimentale de la bibliothèque standard, il y a un ensemble optimisé int qui enregistre chaque bit.
import "golang.org/x/tools/container/intsets"
Il prend également en charge l'union, l'intersection, la différence d'ensembles.
Analogues
std::set et
std::map .
Cela peut sembler un novice de mauvais analogues des tables de hachage:
prend également en charge l'ajout, la suppression et la vérification des occurrences, mais au-delà de O (log n).
Mais les arbres stockent des nœuds triés par clé.
Il n'y a pas d'arbres dans la bibliothèque go standard, un
référentiel contenant les arbres AVL, rouge-noir et B est largement utilisé.
import "github.com/emirpasic/gods/trees/avltree"
Méthodes
API les plus couramment utilisées:
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
Il existe deux méthodes d'arborescence particulièrement importantes:
func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool)
renvoie le plus petit élément existant plus grand que la clé.
func (tree *Tree) Floor(key interface{}) (floor *Node, found bool)
renvoie le plus grand élément existant inférieur à une clé.
Les tâches pour cela se trouvent relativement souvent dans les entretiens. Dans la vraie vie, il est utilisé dans les index de base de données:
select x from table where x <= $1 limit 1;
S'il y a un index, il fonctionnera pour O (log n), pour 1 recherche de la bordure dans l'arborescence B.
Mais cette structure de données dans stl ne l'est pas.
Comme une table de hachage, elle vous permet de vérifier si un élément appartient à un ensemble. Mais le filtre ne stocke pas de clés lors de l'ajout et prend une quantité constante de mémoire. Il est possible de recevoir une fausse réponse positive (il n'y a pas d'élément dans l'ensemble, mais la structure de données signale que c'est le cas), mais pas de faux négatif. Il est utilisé comme filtre pour couper rapidement presque toutes les clés non existantes, ce qui permet d'économiser une vérification plus coûteuse, par exemple, la lecture d'un disque ou l'envoi d'une demande à la base de données.
Il existe une bibliothèque tierce:
https://github.com/willf/bloom import "github.com/willf/bloom"
Peu utilisé, vous pouvez jeter un œil à l'
API .
Il n'y a rien de tel dans la bibliothèque C ++ standard.
Structure de données probabiliste. Avec une petite erreur (≈ 0,4%), il considère le nombre d'éléments uniques sans stocker les clés elles-mêmes. Il offre d'énormes économies de mémoire. Si la tâche consiste à calculer rapidement le nombre de visiteurs ou de demandes - HyperLogLog est idéal.
La bibliothèque la plus populaire pour cela maintenant.
https://github.com/axiomhq/hyperloglog import "github.com/axiomhq/hyperloglog"
Tri
Analogues
std::sort et
std::stable_sort .
Du point de vue du consommateur, il n'y a que 2 types fondamentalement différents:
Stable (ne changez pas l'ordre des éléments égaux [[4, 0], [1, 2], [1, 1], [5, 6]] -> [[1, 2], [1, 1], [4 , 0], [5, 6]])
et non stable, ne garantissant pas la cohérence des champs restants.
Les deux sont dans la bibliothèque standard:
func Sort(data Interface)
Il s'agit d'une implémentation de tri rapide Hoar, instable. Mais pour les sections de longueur <12, le tri par tas est utilisé comme optimisation.
func Stable(data Interface)
À l'intérieur, il s'agit d'un tri par fusion, mais pour plus d'efficacité, lorsque l'algorithme récursif atteint des blocs de moins de 20 éléments, le tri par insertion est utilisé.
Ce sont les algorithmes classiques fonctionnant pour O (n log n).
Si vous le lisez, félicitations. La connaissance d'API spécifiques aide à résoudre les problèmes de test. (Si vous avez travaillé avec quelque chose et connaissez les meilleures alternatives - écrivez dans les commentaires.