2012-05-23 30 views
5

Tengo una lista de elementos (es decir, cadenas) que debo ordenar/filtrar.Eliminar elementos del conjunto en Java

El resultado final debe no contiene cualquier duplicado (fácil), los incluiré en el conjunto. Así que tengo un conjunto de cuerdas ahora.

más explicación ..

también tengo un método x que calcula la cantidad de diferencia entre dos cuerdas (utilizando distancia Levenstein).

Pregunta:

Antes de introducir nueva cadena string en mi Conjunto set Quiero comprobar si hay distancia Levenstein utilizando el método x entre string y cualquier otra cadena en el set y si x vuelve >=3 de lo que debería no agregarlo

¿Cuál es mi mejor oportunidad de hacer esto? Excepto iterar a través del set por cada string que se va a insertar?

+1

Haga su propio método de agregar local que verifique eso y luego lo agregue al conjunto si pasó la prueba. – jn1kk

+0

Es poco probable que haya una solución que lo haga sin potencialmente iterar a través de todo el conjunto, ya que esencialmente desea encontrar la cadena más alejada de la que está insertando y probar esa distancia. Lo más reconfortante es que puedes cortocircuitar la iteración una vez que encuentras una gran distancia. Una última cosa para señalar es que el resultado depende del orden de inserción: '345 34567 12345' rechazará' 12345', pero '345 12345 34567' rechazará' 34567' (Es extraño que quieras eso). – trutheality

Respuesta

2

Iterar a través del Set va a ser su mejor apuesta, ya que no hay ninguna implementación incorporada de Set que le ayude a reducir las posibilidades.

1

Puede usar un comparador personalizado al crear el conjunto. En su comparador, usted devuelve que dos cadenas son iguales si son iguales (según las reglas de comparación de cadenas regulares) o si su distancia Levenstein cumple con sus criterios.

Cuando su comaprator dice que dos cuerdas son iguales, la nueva cuerda no se inserta en el conjunto. (Tenga en cuenta que esto significa que el resultado final de la cadena podría depender de la orden de inserción)

actualización: Direccionamiento de los comentarios sobre ordenación total:

El uso de un comparador como el que se sugirió anteriormente haría que el endresult dependientes en el orden de inserción (como se indicó anteriormente), como cualquier otra solución, ya que los criterios de distancia de Levenstein utilizados no definen el orden total.

OTOH, una vez que una cuerda pasa la prueba no igual y se inserta en el conjunto, ninguna otra cuerda en el conjunto se comparará igual a esta, por lo que las cuerdas en el conjunto usarán su orden natural de cuerdas, que lo hace define el orden total, por lo que no surgen incoherencias adicionales dentro de las operaciones internas del conjunto (p. ej. clasificación).

+1

¿Cómo harías esto en un pedido total? No lo estoy viendo –

+0

El uso de los criterios de distancia de Levenstein no le dará un total de pedidos (por ejemplo, set000> get000 == tit011 == set000) – Attila

+0

Um ... usar una distancia para un comparador le daría un orden incoherente. De ahí la confusión sobre por qué está sugiriendo que se use un comparador. – trutheality

2

He jugado con mi idea de cómo hacerlo. No puedo pensar en una manera de hacer esto sin ninguna cantidad de iteración.

Supongamos que tiene el método denominado distance(String,String):int que devuelve la distancia dada entre dos cadenas.

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 utiliza JDK8 Preview Esto se puede hacer en poco tiempo usando exactamente el código de seguridad. El método Iterables.getFirst() no iterará toda la colección, sino solo hasta que se encuentre el primer elemento que satisfaga los criterios.

De lo contrario, probablemente tendrá que implementar una interfaz Predicate y un método de filtrado.

interface Predicate<T> { 
    public boolean eval(T o); 
} 

public static void main(String[] args) { 
    final String x = "Obi-wan"; //this is the item subject to eval addition 
    List<String> items = new ArrayList<String>(asList("Luke","Yoda","Anakin")); 
    Predicate<String> p = new Predicate<String>() { 
     public boolean eval(String s){ 
      return distance(s, x) >= 3; 
     } 
    }; 
    if(filter(items, p).isEmpty()){ 
     items.add(x); 
    } 
} 

public static <T> List<T> filter(List<? extends T> items, Predicate<? super T> predicate){ 
    List<T> destiny = new ArrayList<T>(); 
    for(T item : items){ 
     if(predicate.eval(item){ 
      destiny.add(item); 
     } 
    } 
    return destiny; 
} 

Como alternativa, puede dejar de filtrar una vez que encuentre el primer elemento que cumpla con sus criterios.

Cuestiones relacionadas