Ruby est-il adapté aux structures de données et aux algorithmes ?
Oui, pour apprendre comme pour les entretiens dans les entreprises qui utilisent Rails : le code est aussi court qu'en Python, et avec les blocs, les traversées se lisent comme l'algorithme. Deux lacunes sont à connaître. La bibliothèque standard n'a ni tas, ni file de priorité, ni liste chaînée, ni arbre, donc tu les écris ; et Array#sort ne promet pas la stabilité, donc quand des éléments égaux doivent garder leur ordre, trie par paire : sort_by.with_index { |x, i| [x, i] }.
Quelles classes Ruby correspondent à quelles structures de données ?
Array est un tableau dynamique qui sert de pile (push, pop) et de file (push, shift) ; Hash est une table de hachage qui se souvient de l'ordre d'insertion ; et Set, dans la bibliothèque standard, est un ensemble basé sur le hachage. La liste s'arrête là. Il n'y a ni tas, ni file de priorité, ni liste chaînée, ni arbre, ni trie, ni graphe : ceux-là, tu les construis toi-même, aux étapes un et deux.
Comment écrire une file de priorité en Ruby ?
Ruby n'en a jamais fourni, donc il y a trois réponses honnêtes : trier le tableau après chaque insertion, en O(n log n) par ajout ; le garder trié avec bsearch_index et insert, en O(n) par ajout ; ou écrire un tas binaire sur un Array, en O(log n) pour l'ajout comme pour le retrait. La troisième est celle qu'attend un recruteur, et l'étape deux te la fait construire.
Pourquoi l'ordre d'insertion d'un Hash Ruby compte-t-il pour les algorithmes ?
Parce qu'il réduit certaines conceptions classiques à quelques lignes. Un cache LRU, un grand classique des entretiens, est un Hash dans lequel une lecture supprime puis réinsère la clé pour la déplacer à la fin, et l'éviction se fait avec shift, qui retire l'entrée la plus ancienne. Dans la plupart des langages, il faut pour cela une table de hachage et une liste doublement chaînée, les structures que tu construis aux étapes un et deux : tu peux donc expliquer ce que Ruby fait pour toi.
Quels cours de ce parcours ne sont pas enseignés en Ruby ?
Trois : la programmation dynamique et la série d'entretiens en Python, enseignées en Python, et la manipulation de bits, enseignée en C++. Ces trois cours figurent après les étapes, chacun avec un lien qui l'ouvre dans son propre langage. En Ruby, une table de mémoïsation peut être un Hash avec un bloc par défaut, comme Hash.new { |h, n| h[n] = n < 2 ? n : h[n - 1] + h[n - 2] }, et n[i] lit directement le bit i d'un entier, là où C++ écrit (n >> i) & 1.
Faut-il connaître Ruby avant de commencer ce parcours ?
Au minimum les méthodes, les blocs, les tableaux, les hashes et les classes. Si c'est nouveau pour toi, le cours Ruby de Coddy t'y amène d'abord, gratuitement, et ce parcours prend le relais là où il s'arrête.
