Filtrer les éléments de Set in Java

Question

J'ai une liste d'éléments (i.e Strings) que j'ai besoin de trier/filtrer.

Le résultat final devrait pas contenir aucun doublon (facile), je vais les mettre tous dans l'ensemble. Donc j'ai un ensemble de cordes maintenant.

explication plus ..

Je également un procédé qui permet de calculer x la quantité de différence entre deux cordes (en utilisant la distance de Levenstein).

Question:

Avant d'insérer une nouvelle chaîne string dans mon Set set je veux vérifier Levenstein la distance en utilisant la méthode x entre string et toute autre chaîne dans la set et si x retours >=3 que je devrais ne l'ajoute pas.

Quelle est ma meilleure chance de le faire? Sauf itération du creux set pour chaque string à insérer?

Answer 1

L'itération à travers le Set va être votre meilleur pari, car il n'y a aucune implémentation Set intégrée qui vous aiderait à réduire les possibilités.

Answer 2

Vous pouvez utiliser un comparateur personnalisé lors de la création de l'ensemble. Dans votre comparateur, vous retournez que deux chaînes sont identiques si elles sont identiques (selon les règles de comparaison de chaînes normales) ou si leur distance Levenstein répond à vos critères. Lorsque votre comaprator dit que deux chaînes sont identiques, la nouvelle chaîne n'est pas insérée dans l'ensemble. (Notez que cela signifie que le résultat final de la chaîne pourrait dépendre de l'ordre d'insertion)

Mise à jour: Aborder les commentaires concernant la commande totale:

En utilisant un comparateur comme celui proposé ci-dessus se faire la endresult dépendante selon l'ordre d'insertion (comme indiqué ci-dessus), comme toute autre solution, comme le critère de distance de Levenstein utilisé, ne définit pas l'ordre total. OTOH, une fois qu'une chaîne réussit le test non égal et qu'elle est insérée dans l'ensemble, aucune autre chaîne de l'ensemble ne sera comparable à celle-ci, donc les chaînes de l'ensemble utiliseront leur ordre de chaînes naturel, ce qui définir la commande totale, donc aucune autre incohérence ne survient dans les opérations internes de l'ensemble (par exemple, le tri).

Answer 3

J'ai joué avec mon idée de la façon de le faire. Je ne peux pas penser à un moyen de le faire sans aucune quantité d'itération. Supposons que vous ayez la méthode distance(String,String):int qui renvoie la distance donnée entre deux chaînes.

String x = "Obi-wan"; //this is the item subject to eval addition 
List<String> items = new ArrayList<String>(asList("Luke","Yoda","Anakin")); 
if (items.filter(s -> distance(s, x) >= 3).getFirst() == null) { 
    items.add(x); 
} 

Si vous utilisez JDK8 Preview vous pouvez le faire en peu de temps en utilisant exactement le code ci-dessus. La méthode Iterables.getFirst() n'itère pas la collection entière, mais seulement jusqu'à ce que le premier élément répondant aux critères soit trouvé.

Sinon, vous devrez probablement implémenter une interface de prédicat et une méthode de filtrage. Vous pouvez également arrêter le filtrage une fois que vous avez trouvé le premier élément répondant à vos critères. Vous pouvez également arrêter le filtrage.