Algo más rápido para buscar un conjunto de caracteres en una cadena dada

Question

Este es un debate que estaba teniendo con uno de mis amigos: ¿Cuál sería la forma más rápida de hacer un método de validación que verifique si la cadena dada tiene uno de los no permitidos caracteres

método I: sencilla

char [] invalidChars = "!@#$%^...".toCharArray(); 
     for (int i = 0; i < myString.length(); i++) { 
      char ch = myString.charAt(i); 
      for (int j = 0; j < invalidChars.length; j++) { 
       if (invalidChars[j] == ch) { 
        return false; 
       } 
      } 
     } 

método II: Explotación de O de Mapa (1)

Map <String,String> map = new HashMap<String, String>(); 
     map.put("!", null); 
     map.put("@", null); 
     map.put("#", null); 
     map.put("$", null); 
     map.put("^", null); 
     ... 
     for (int i = 0; i < labels.length(); i++) { 
      char ch = labels.charAt(i); 
      if (map.containsKey(ch)) { 
       return false; 
      } 
      return true; 
     } 

El método I es en realidad N2 pero tan bueno como N cuando invalidChars son menos en número. ¿Qué se debe preferir cuando Caso I: hay muchos caracteres no válidos, Caso II: solo unos pocos caracteres no válidos?

Nota: No estoy en busca de alguna solución de Java incorporado, pero, al igual que el algoritmo para filtrar algunos (no todos) los personajes no son de texto

Answer 1

Si sólo está interesado en la validación de caracteres ASCII, a continuación, una longitud -128 boolean lookup-table puede ser más rápido que cualquiera de los métodos anteriores.

Answer 2

Construir un hashmap y poner elementos allí es relativamente caro. Sin embargo, como ha dicho, buscar elementos en un hashmap es O (1).

Así que tenemos hashmap fill: O (n log n) con la búsqueda O (1).

O la forma estándar (complete O (1) búsqueda O (n)).

Sin embargo, dado que la búsqueda O (n) ocurre para cada cadena, el primer método en total es O (numberOfInvalidChars + cadenas * NumberofInValidChars) el segundo es O (numInv log numInv + cadenas). Whichs es mucho menos costoso, casi siempre más barato.

Answer 3

Hay un método simple que le da O(n log(m)) complejidad de tiempo, donde n es la longitud de la entrada y m es el número de caracteres no permitidos.

Escanee la entrada un carácter a la vez, y busque el carácter actual en la matriz (ordenada) de caracteres no permitidos mediante la búsqueda binaria.

Answer 4

Si utiliza un HashSet, que le da O (1) el complemento y contiene tiene:

• O (n) para la inserción de cada carácter prohibido
• O (m) para cada comparar operación

que conduce a O (m + n) donde m es el número de caracteres prohibidos yn es la longitud de la cadena. Pero ya veo respuestas que funcionan mejor.

Pero tenga en cuenta que la mayoría de las cosas vienen con una sobrecarga (como el "hash" en HashSet/HashMap). Entonces, incluso si el rendimiento asintótico puede ser mejor, una implementación ingenua puede ser más rápida en entradas pequeñas. No digo que deba usar algo que tenga O (n²) pero puede valer la pena comparar una solución O (n log n) con una solución O (m) para un conjunto común de datos.

Answer 5

¡Más rápido! HashMap está lejos de ser la solución más rápida, solo teóricamente es O (1).

En java: java.util.BitSet está diseñado para sus necesidades. Como alternativa, utilice arrays largos sin envolver []/int [] (según la arquitectura de destino 32/64)

¿Por qué HashMap no es bueno? El equipaje extra que proviene de acceder y crear cubos es más alto que el de la derecha.