Pergi struktur data lembar contekan

Beberapa perusahaan mewawancarai kode penulisan online. Ini diperlukan untuk memecahkan masalah Olimpiade untuk kecepatan. Dalam keadaan seperti itu, tidak ada waktu untuk melihat detail penerapan struktur data - Anda harus segera mewujudkan gagasan itu. Tetapi kursus tentang algoritma dan struktur data memberikan contoh dalam pseudo-code atau C ++. Lebih banyak solusi referensi untuk masalah sering ditulis dalam C ++. Bersiap untuk wawancara, saya membuat boks perpustakaan - analog wadah STL, agar tidak membuang waktu mencari yang berharga.

Mari kita mulai dengan yang jelas.

Array kontinu dinamis

Analog std::vector .
Mendukung mengakses elemen dengan indeks untuk waktu yang konstan dari beberapa siklus prosesor. Anda dapat menambah atau mengurangi kapasitas. Ini adalah potongan bawaan:

 vector := []int{} 

Mudah, konsep dasar dibangun ke dalam bahasa.

Tumpukan

Analog std::stack .

Set yang diperintahkan untuk menambahkan elemen baru dan menghapus yang sudah ada dilakukan dari satu ujung. Elemen yang ditempatkan terakhir (last-in, first-out - LIFO) dihapus terlebih dahulu dari tumpukan. Lagi-lagi ini adalah potongan berdinding. Cuplikan disalin dari proyek ke proyek:

 // Push stack = append(stack, value) 

 // Pop // ,  len(stack) > 0 stack, value = a[:len(stack)-1], a[len(stack)-1] 

Operasi irisan tidak mengalokasikan memori baru.

Antrian

Analogi std::queue dan std::deque .

Antrian menerapkan operasi pengambilan dan penambahan untuk memulai dan mengakhiri dalam waktu yang konstan. Elemen yang pertama kali ditempatkan (masuk pertama, keluar pertama - FIFO) dihapus pertama dari antrian. Saluran buffered adalah antrian pada buffer cincin, Anda dapat menggunakannya ketika pembaca dan penulis adalah goroutine yang berbeda. Tetapi tidak ada implementasi antrian terpisah di perpustakaan standar. Daftar yang luar biasa menyarankan perpustakaan https://github.com/gammazero/deque .

 import "github.com/gammazero/deque" 

Operasi yang sedang berlangsung:

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

Daftar tertaut ganda

Analog dengan std::list .
Ini terdiri dari elemen yang mengandung, di samping data mereka sendiri, tautan ke item daftar berikutnya dan sebelumnya. Itu ada di perpustakaan standar:

 import "container/list" 

Seperti yang diharapkan, ini mendukung operasi penyisipan (di awal, di akhir, sebelum dan setelah elemen, pointer yang dilewati) dan penghapusan.

 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 tidak menyediakan sintaksis spesifik untuk iterator. Oleh karena itu, elemen berikutnya / sebelumnya dapat diperoleh dari pointer ke sembarang simpul. Metode ini tidak memburuk setelah menambahkan / menghapus item ke daftar, tanpa kejutan.

 func (e *Element) Next() *Element func (e *Element) Prev() *Element 

Antrian prioritas

Analog std::priority_queue
Memungkinkan Anda untuk menumpuk item dalam urutan apa pun, dan dapatkan kapan saja prioritas tertinggi dari sisanya. Ini digunakan, misalnya, dalam algoritma untuk membangun pohon spanning minimal, ketika pada langkah berikutnya algoritma memilih tepi terpendek dari semua mulai dari simpul yang sudah dibahas pada satu ujung.

Pustaka standar memiliki adaptor yang mengubah setiap wadah yang dapat diurutkan (yang mengimplementasikan sort.Interface ) menjadi antrian prioritas.

 import "container/heap" 

Ini adalah tumpukan biner klasik. Menerapkan penyisipan dan penghapusan di O (log n).

 func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{} 

Meja hash

Ini adalah kamus dan array asosiatif.

Analog std::unordered_map .

Memungkinkan Anda menambahkan nilai kunci, menghapus nilai menurut kunci dan memeriksa keberadaan elemen untuk O (1) secara rata-rata. Jelas peta dibangun ke dalam bahasa:

 unorderedMap := make(map[string]int) 

Hasil make (peta) adalah sebuah pointer, dan cara kerjanya sedikit berbeda dari kontainer standar:

 //  : _, ok := unorderedMap["route"] //  : delete(unorderedMap, "route") //  : n := len(unorderedMap) 

"Runtime / map", tidak seperti std :: unordered_map, merawat programmer - aman untuk menghapus nilai selama iterasi.

Banyak

Analog std::unordered_set .
Hampir sama dengan tabel hash, tetapi tanpa menyimpan nilai.
Jika kita hanya perlu cek entri cepat, maka kita bisa menggunakan peta bawaan lagi. Hanya perlu menentukan nilai kosong untuk menunjukkan bahwa hanya kunci yang penting.

 var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"] // true 

Tetapi implementasi ini tidak mendukung operator yang kompleks. Untuk menggabungkan, memotong, perbedaan dari kotak, Anda memerlukan pustaka pihak ketiga. Paling banyak digunakan, dilihat dari jumlah bintang: https://github.com/deckarep/golang-set

 import "github.com/deckarep/golang-set" 

Bagian API yang paling dibutuhkan:

 Add(i interface{}) bool Remove(i interface{}) Cardinality() int // len() Contains(i ...interface{}) bool IsSubset(other Set) bool Intersect(other Set) Set Union(other Set) Set Difference(other Set) Set SymmetricDifference(other Set) Set 

Setel int

Di bagian eksperimental perpustakaan standar ada set int yang dioptimalkan yang menyimpan setiap bit.

 import "golang.org/x/tools/container/intsets" 

Ini juga mendukung penyatuan, persimpangan, perbedaan set.

Pohon pencarian biner

Analog std::set dan std::map .
Ini mungkin tampak seperti analog buruk buruk dari tabel hash:
juga mendukung penambahan, penghapusan dan pemeriksaan kejadian, tetapi di luar O (log n).
Tetapi pohon menyimpan simpul yang diurutkan berdasarkan kunci.

Tidak ada pohon di perpustakaan go standar, repositori yang berisi AVL, Merah-Hitam dan B-pohon banyak digunakan.

 import "github.com/emirpasic/gods/trees/avltree" 

Metode API yang paling umum digunakan:

 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 

Ada dua metode pohon yang sangat penting:

 func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool) 

mengembalikan item terkecil yang ada lebih besar dari kunci.

 func (tree *Tree) Floor(key interface{}) (floor *Node, found bool) 

mengembalikan elemen terbesar yang ada kurang dari kunci.

Tugas untuk ini relatif sering ditemukan dalam wawancara. Dalam kehidupan nyata digunakan dalam indeks basis data:

 select x from table where x <= $1 limit 1; 

Jika ada indeks, itu akan berfungsi untuk O (log n), untuk 1 pencarian perbatasan di B-tree.

Filter mekar

Tetapi struktur data ini di stl tidak.
Seperti tabel hash, ini memungkinkan Anda untuk memeriksa apakah elemen milik set. Tetapi filter tidak menyimpan kunci saat menambahkan, dan mengambil jumlah memori yang konstan. Dimungkinkan untuk menerima tanggapan positif palsu (tidak ada elemen di set, tetapi struktur data melaporkan bahwa itu adalah), tetapi tidak negatif palsu. Ini digunakan sebagai filter untuk dengan cepat memotong hampir semua kunci yang tidak ada, menyimpan verifikasi yang lebih mahal, misalnya, membaca dari disk atau membuat permintaan ke database.
Ada perpustakaan pihak ketiga: https://github.com/willf/bloom

 import "github.com/willf/bloom" 

Tidak begitu sering digunakan, Anda bisa mengintip API .

HyperLogLog

Tidak ada hal seperti itu di pustaka C ++ standar.

Struktur data probabilistik. Dengan kesalahan kecil (≈ 0,4%), itu mempertimbangkan jumlah elemen unik tanpa menyimpan kunci itu sendiri. Ini memberikan penghematan memori yang sangat besar. Jika tugasnya adalah dengan cepat menghitung jumlah pengunjung atau permintaan - HyperLogLog ideal.

Perpustakaan paling populer untuk ini sekarang.

https://github.com/axiomhq/hyperloglog

 import "github.com/axiomhq/hyperloglog" 

Sortasi

Analog std::sort dan std::stable_sort .
Dari sudut pandang konsumen, hanya ada 2 jenis yang berbeda secara mendasar:
Stabil (jangan mengubah urutan elemen yang sama [[4, 0], [1, 2], [1, 1], [5, 6]] -> [[1, 2], [1, 1], [4 , 0], [5, 6]])
dan tidak stabil, tidak menjamin konsistensi bidang yang tersisa.
Keduanya ada di perpustakaan standar:

 func Sort(data Interface) 

Ini adalah implementasi quicksort Hoar, tidak stabil. Tetapi untuk bagian dengan panjang <12 heap sorting digunakan sebagai optimasi.

 func Stable(data Interface) 

Di dalam, ini adalah semacam penggabungan, tetapi untuk efisiensi, ketika algoritma rekursif mencapai blok kurang dari 20 elemen, penyisipan digunakan.

Ini adalah algoritma klasik yang berfungsi untuk O (n log n).

Jika Anda membacanya, selamat. Mengetahui API tertentu membantu dalam memecahkan masalah pengujian. (Jika Anda bekerja dengan sesuatu dan mengetahui alternatif terbaik - tulis di komentar.