Comment vérifier s'il y a des doublons dans une tranche?

Existe-t-il un moyen natif de vérifier si une section a des doublons? Pour l'instant, j'utilise ceci:Comment vérifier s'il y a des doublons dans une tranche?

fn has_dup<T: PartialEq>(slice: &[T]) -> bool { 
    for i in 1..slice.len() { 
     if slice[i..].contains(&slice[i - 1]) { 
      return true; 
     } 
    } 
    false 
} 

fn main() { 
    use std::ops::Not; 

    assert!(has_dup(&[1, 2, 3, 2, 5, 6])); 
    assert!(has_dup(&[1, 2, 3, 4, 5, 6]).not()); 
}

mais pour ce genre d'opérations de base, je n'aime pas utiliser le code à la main.

S'il n'y a pas de fonction disponible pour cela dans la bibliothèque standard, est-ce une manière d'optimiser mon code? Je sais que l'indexation de la tranche n'est pas le moyen le plus optimisé (for i in slice {} vs for i in 0..slice.len() { slice[i] }).

Source

2017-10-16 Boiethios

Il s'agit fondamentalement du [problème de distinction d'élément] (https://en.wikipedia.org/wiki/Element_distinctness_problem). Il y a des façons plus efficaces de le faire que de vérifier chaque élément par rapport au reste de la liste, qui est 'O (n^2)', mais aucun d'entre eux n'est implémenté dans std. Cependant, le compromis est qu'ils pourraient nécessiter plus de mémoire. Voir une approche de [suppression des dupes avec un HashSet] (https://github.com/Hoverbear/rust-rosetta/blob/master/tasks/remove-duplicate-elements/src/main.rs) sur rosetta-code. C'est à enlever vs juste vérifier mais cela devrait vous donner une idée de comment cela peut être fait. –

@PaoloFalabella Il est étrange qu'un tel algorithme de base ne soit pas dans le standard. – Boiethios

@Boiethios pourquoi croyez-vous que c'est un algorithme "de base"? Même si c'est le cas, rappelez-vous que des choses comme * génération de nombres aléatoires *, que beaucoup considèrent comme «basiques», sont fournies par une caisse. – Shepmaster

En termes de complexité algorithmique, il est souvent préférable de garder une trace des valeurs uniques dans un index. Si vous pouvez vérifier l'égalité avec Hash et Eq, vous pouvez essayer cette fonction utilitaire:

fn has_unique_elements<T>(iter: T) -> bool 
where 
    T: IntoIterator, 
    T::Item: Eq + Hash, 
{ 
    let mut uniq = HashSet::new(); 
    iter.into_iter().all(move |x| uniq.insert(x)) 
} 

assert!(!has_unique_elements(vec![10, 20, 30, 10, 50])); 
assert!(has_unique_elements(vec![10, 20, 30, 40, 50])); 
assert!(has_unique_elements(Vec::<u8>::new()));

Playground

De même, si vos éléments ne mettent pas en œuvre Hash mais Ænglisc Ord, vous pouvez utiliser une place BTreeSet (Playground).

Source

2017-10-16 10:05:44

J'aime cette solution, mais il y a plus de contraintes sur le type ('Hash' +' Clone') – Boiethios

Impossible de faire une omelette sans casser des oeufs. : P Une fonction de hachage ou une relation d'ordre total est requise pour des recherches plus rapides. Je ne suis pas sûr si faire des copies des éléments précédemment récupérés peut être évité. –

Est-il possible d'utiliser '.cloned(). All (déplacer | x | uniq.insert (x))' ?. La contrainte 'ExactSizeIterator' ne devrait pas être nécessaire. – Boiethios

L'indexation n'est pas moins optimisée, ce n'est juste pas idiomatique en présence d'une solution d'itérateur. Il n'y a pas de solution d'itérateur, donc votre code est déjà la solution optimale.

Si vous voulez aller sur une route plus fonctionnelle, vous pouvez écrire

(1..slice.len()).any(|i| slice[i..].contains(&slice[i - 1]))

Source

2017-10-16 09:15:54

L'indexation vérifie si l'index est dans les limites. Il y a donc une (petite) surcharge. Mais cette petite surcharge peut faire une plus grande différence dans une boucle. – Boiethios

LLVM prendra soin de ces boucles simples. Vous avez raison dans le cas général. –

Comment vérifier s'il y a des doublons dans une tranche?

Répondre

Questions connexes