Recherche en Rust : trouver l'indice d'un élément de tableau avec une performance maximale

Introduction : Pourquoi la recherche d'indice en Rust n'est pas simplement "trouver et retourner" ?

Chaque développeur passant à Rust depuis Python ou JavaScript se demande tôt ou tard : "Comment trouver l'indice d'un élément dans un tableau ou un vecteur ici ?" En Python, cela se fait en une ligne list.index(element), en JavaScript — array.indexOf(element). Mais Rust, en véritable perfectionniste, propose non pas une, mais plusieurs méthodes, chacune avec ses nuances de performance et de sécurité.

Voyons comment trouver l'indice d'un élément dans les collections Rust (tableaux, vecteurs et slices) de manière à ce que le code soit non seulement correct, mais aussi rapide. Car en programmation système, chaque nanoseconde compte !

Base : les méthodes principales de recherche d'indice en Rust

Dans la bibliothèque standard de Rust, il y a deux "acteurs" principaux pour la recherche d'indice : position() et rposition(). Ils sont disponibles pour tous les itérateurs, donc aussi pour les tableaux, vecteurs et slices.

Méthode position() : recherche de gauche à droite

position() prend une closure et retourne Option<usize> — l'indice du premier élément satisfaisant la condition, ou None si aucun élément n'est trouvé.

fn main() {\n    let numbers = vec![10, 20, 30, 40, 50];\n    \n    // Recherche de la première occurrence du nombre 30\n    let index = numbers.iter().position(|&x| x == 30);\n    \n    match index {\n        Some(i) => println!("Indice du nombre 30 : {}", i), // Affichage : 2\n        None => println!("Élément non trouvé"),\n    }\n}\n

Notez que nous appelons iter() avant position(). C'est important car position() est une méthode du trait Iterator, et non de la collection elle-même.

Méthode rposition() : recherche de droite à gauche

Si vous avez besoin du dernier indice d'occurrence d'un élément, utilisez rposition(). Il fonctionne de manière similaire, mais parcourt la collection depuis la fin :

fn main() {\n    let data = vec!['a', 'b', 'c', 'b', 'a'];\n    \n    // Trouvons la dernière occurrence de 'b'\n    let last_b = data.iter().rposition(|&c| c == 'b');\n    \n    println!("Dernier 'b' à l'indice : {:?}", last_b); // Some(3)\n}\n

Une limitation importante : rposition() ne fonctionne qu'avec les collections qui supportent le parcours bidirectionnel (trait DoubleEndedIterator). Heureusement, toutes les collections standard de Rust satisfont cette exigence.

Comparaison des performances : position() vs parcours manuel

De nombreux débutants écrivent des boucles manuellement, pensant que c'est plus rapide. Vérifions cette hypothèse en pratique.

Considérons deux approches pour rechercher l'indice d'un élément dans un vecteur d'un million d'entiers :

use std::time::Instant;\n\nfn main() {\n    let large_vec: Vec<i32> = (0..1_000_000).collect();\n    let target = 999_999;\n    \n    // Méthode 1 : position()\n    let start = Instant::now();\n    let pos1 = large_vec.iter().position(|&x| x == target);\n    let duration1 = start.elapsed();\n    println!("position() : {:?}, temps : {:?}", pos1, duration1);\n    \n    // Méthode 2 : boucle manuelle\n    let start = Instant::now();\n    let mut pos2 = None;\n    for (i, &val) in large_vec.iter().enumerate() {\n        if val == target {\n            pos2 = Some(i);\n            break;\n        }\n    }\n    let duration2 = start.elapsed();\n    println!("Boucle manuelle : {:?}, temps : {:?}", pos2, duration2);\n}\n

Les résultats sur les processeurs modernes montrent généralement que position() est aussi rapide que la boucle manuelle, et parfois même plus rapide grâce aux optimisations internes du compilateur Rust (LLVM). Conclusion : utilisez position() — c'est idiomatique, sûr et ne sacrifie pas la vitesse.

Recherche binaire : quand les données sont triées

Si votre collection est triée, vous devez utiliser binary_se