Un moyen rapide de trouver des valeurs uniques dans la liste

Donné une liste de KeyValuePairs, où chaque paire possède un getValue() méthode, ce serait le moyen le plus rapide pour obtenir un List (ou Set) de Valeurs uniques?

Tous les dessous de produire de résultat acceptable. u1 semble être la plus rapide au cours d'une taille de la liste (environ 1000-2000 KVP)

Pouvons-nous faire mieux (plus rapide)?

private static Set<String> u1(List<_KVPair> pairs) {
    Set<String> undefined = new HashSet<String>();

    for (_KVPair pair : pairs) {
        undefined.add(pair.getValue());
    }

    if (undefined.size() == 1) {
        return new HashSet<String>();
    }
    return undefined;
}

private static List<String> u2(List<_KVPair> pairs) {

    List<String> undefined = new ArrayList<String>();
    for (_KVPair pair : pairs) {
        if (!undefined.contains(pair.getValue())) {
            undefined.add(pair.getValue());
        }
    }

    return undefined;
}

private static List<String> u3(List<_KVPair> pairs) {

    List<String> undefined = new LinkedList<String>();

    Iterator<_KVPair> it = pairs.iterator();
    while (it.hasNext()) {
        String value = it.next().getValue();
        if (!undefined.contains(value)) {
            undefined.add(value);
        }
    }
    return undefined;
}

À environ 3600 paires, 'u3' gagne. À environ 1500 paires, 'u1' gagne

Ce qui se passe quand vous l'essayer? Qui a le temps le plus bas de la complexité?
Il semble que la première est la plus rapide.
.. et il a le temps le plus bas de la complexité, O(N) vs O(N^2)
Je voudrais assurez-vous que vous exécutez les tests pour au moins 2 à 5 secondes, sinon vous obtiendrez des résultats qui ne sont pas reproduire-mesure.
Un ensemble est une collection qui ne contient que des valeurs uniques. Généralement, le moyen le plus rapide pour trouver les valeurs uniques d'une grande collection de valeurs est d'ajouter toutes les valeurs d'un ensemble, à l'origine de tous les doublons à disparaître depuis la méthode add pour le définir simplement les ignorer l'entrée si celle-ci existe déjà dans le jeu.

OriginalL'auteur JAM | 2012-09-25