Tengo un mapa:

Map<String, String> abc = new HashMap<>();

"clave1": "valor1",
"clave2": "valor2"

Y una matriz:

String[] options= {"value1", "value2", "value3"}

Estoy creando esta matriz de la siguiente manera (estoy usando el siguiente método para hacer otra cosa que no es relevante para la pregunta que estoy haciendo aquí):

public String[] getOptions() {
    List<String> optionsList = getOptionsFromAMethod(WebElementA);
    String[] options = new String[optionsList.size()];
    options = optionsList.toArray(options);
    return options;
}

¿Cuál es la mejor manera de verificar si la Cadena [] contiene cada valor del Mapa?

Estoy pensando en hacer esto:

for (Object value : abc.values()) {
    Arrays.asList(options).contains(value);
}
1
user7331530 23 oct. 2017 a las 17:43

3 respuestas

La mejor respuesta

Explicación

Su enfoque actual crea un ArrayList (de java.util.Arrays, para no confundirlo con el ArrayList de java.util) envolviendo la matriz dada.

Luego llama, para cada valor del mapa, al método ArrayList#contains. Sin embargo, este método es muy lento . Recorre la lista completa para buscar algo.

Por lo tanto, su enfoque actual produce O(n^2) que no escala muy bien.


Solución

Podemos hacerlo mejor utilizando una estructura de datos diseñada para una consulta rápida contains, es decir, una HashSet.

Entonces, en lugar de poner todos sus valores en un ArrayList, los pondremos en un HashSet cuyo método contains es rápido :

boolean doesContainAll = true;
HashSet<String> valuesFromArray = new HashSet<>(Arrays.asList(options));
for (String value : abc.values()) {
    if (!valuesFromArray.contains(value)) {
        doesContainAll = false;
        break;
    }
}

// doesContainAll now is correctly set to 'true' or 'false'

El código ahora funciona en O(n), que es mucho mejor y también óptimo en términos de complejidad.

Por supuesto, puede optimizar aún más para acelerar por factores constantes. Por ejemplo, primero puede verificar el tamaño, si options.length es mayor que abc.values().size(), puede regresar directamente con false.


Solución JStream

También puede usar Java 8 y Stream s para simplificar el código anterior, el resultado y también el procedimiento detrás de escena es el mismo:

HashSet<String> valuesFromArray = new HashSet<>(Arrays.asList(options));
boolean doesContainAll = abc.values().stream()
    .allMatch(valuesFromArray::contains);

Insights of ArrayList # contiene

Echemos un vistazo más de cerca a java.util.Arrays.ArrayList. Puede encontrar su código aquí.

Aquí está su código para el método contains:

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

Veamos cómo se implementa indexOf:

public int indexOf(Object o) {
    E[] a = this.a;
    if (o == null) {
        for (int i = 0; i < a.length; i++)
            if (a[i] == null)
                return i;
    } else {
        for (int i = 0; i < a.length; i++)
            if (o.equals(a[i]))
                return i;
    }
    return -1;
}

De hecho, en todos los casos, el método atravesará de izquierda a derecha a través de la matriz fuente para encontrar el objeto. No existe ningún método sofisticado que pueda acceder directamente a la información si si el objeto está contenido o no, se ejecuta en O(n) y no en O(1).


Nota sobre duplicados

Si cualquiera de sus datos puede contener duplicados y planea contarlos individualmente , necesitará un enfoque ligeramente diferente ya que contains no molestará por la cantidad de duplicados

Para esto, puede recopilar su abc.values() primero en un List, por ejemplo. Luego, cada vez que marque un elemento, eliminará el elemento coincidente de List.

Alternativamente, puede configurar un HashMap<String, Integer> que cuenta para cada elemento sus ocurrencias. Luego, cada vez que marque un elemento, disminuya el contador en uno.

3
Zabuzard 23 oct. 2017 a las 17:30

Puede usar https://docs.oracle.com/javase/7/docs/api/java/util/List.html#containsAll(java.util.Collection)

Arrays.asList("value1", "value2", "value3").containsAll(abc.values())
1
awsome 23 oct. 2017 a las 14:48

Yo recomendaría usar una transmisión:

final List<String> optionsList = Arrays.asList(options);
abc.values().stream().allMatch(optionsList::contains);
0
ivospijker 23 oct. 2017 a las 14:55