Rust va bene per algoritmi e strutture dati?
Per usarli, benissimo: le collezioni standard sono veloci e ben documentate, sort è stabile, e il Rust sicuro esclude puntatori pendenti e data race già in compilazione, senza garbage collector. Per scrivere strutture basate su puntatori, è più difficile che in C o Java, perché l'ownership esclude collegamenti condivisi e mutabili a meno che tu non scelga Rc e RefCell, e una lista doppiamente concatenata o un albero con puntatori al genitore sono fatti proprio di questi. Quella difficoltà è anche la lezione: una volta che sai scriverli in Rust, sai esattamente chi possiede cosa.
Quali collezioni di Rust corrispondono a quali strutture dati?
Vec<T> è un array dinamico e la tua pila, VecDeque<T> è un buffer circolare e la tua coda, HashMap e HashSet sono tabelle hash (SipHash per impostazione predefinita, che resiste alle collisioni intenzionali a scapito di un po' di velocità), BTreeMap e BTreeSet sono B-tree ordinati, BinaryHeap<T> è un max-heap, e LinkedList<T> è una lista doppiamente concatenata che raramente preferirai a un Vec o a un VecDeque. Non esiste un tipo trie o grafo; quelli li costruisci tu.
Perché è così difficile scrivere una lista concatenata in Rust?
Perché ogni valore ha esattamente un proprietario. Una lista semplicemente concatenata rispetta la regola: ogni nodo possiede il successivo tramite Option<Box<Node>>. Una lista doppiamente concatenata o un albero con collegamenti al genitore no, perché a ogni nodo portano due puntatori, quindi ricorri a Rc<RefCell<Node>> con Weak per i collegamenti all'indietro, oppure tieni i nodi in un Vec e li colleghi tramite indice. Learning Rust With Entirely Too Many Linked Lists esiste perché tantissime persone si bloccano proprio qui.
Come ottengo un min-heap in Rust?
BinaryHeap<T> è un max-heap, quindi avvolgi ogni elemento in std::cmp::Reverse: inserisci Reverse(x) e il più piccolo x esce per primo. Per Dijkstra, inserisci Reverse((distance, node)), e la tupla confronta prima la distanza. Una volta che hai scritto un heap da te nel secondo passaggio, invertirne l'ordine è ovvio.
Quali corsi di questo percorso non sono insegnati in Rust?
Tre: la programmazione dinamica e la serie di colloqui in Python, insegnate in Python, e la manipolazione dei bit, insegnata in C++. Sono elencati dopo i passaggi, ognuno con un link che lo apre nel suo linguaggio. Una tabella di memoizzazione in Rust è un Vec o una HashMap, e l'overflow degli interi va in panic in una build di debug, quindi un trucco sui bit che si basa sull'overflow circolare lo esplicita con wrapping_add o wrapping_mul.
Devo conoscere Rust prima di iniziare questo percorso?
Almeno ownership, borrowing, struct, enum e Option; Box e i trait aiutano. Se sono argomenti nuovi, il corso di Rust di Coddy ti porta prima a quel punto, gratis, e questo percorso riprende da dove finisce.
