Algo più veloce per cercare set di caratteri in una stringa data

Question

Questo è un dibattito che stavo avendo con uno dei miei amici: quale sarebbe il modo più veloce di fare un metodo di valenza che controlli se la stringa data ha uno dei non consentiti personaggi

metodo I: semplice

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; 
       } 
      } 
     } 

metodo II: Sfruttando Map O (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; 
     } 

Il metodo che è in realtà N2, ma buono come N quando invalidChars sono meno in numero. Cosa dovrebbe essere preferito quando Caso I: ci sono molti caratteri non validi, Caso II: solo pochi caratteri non validi?

Nota: non sto cercando di eventuali soluzioni Java incorporati, ma, appena l'algoritmo per filtrare alcuni (non tutti) i caratteri non di testo

Answer 1

Se siete interessati solo a convalidare caratteri ASCII, quindi una lunghezza -128 tabella di ricerca booleana potrebbe essere essere più veloce di uno dei metodi sopra.

Answer 2

La creazione di una hashmap e il posizionamento di elementi in essa è relativamente costosa. Tuttavia, come hai detto, la ricerca di elementi in una mappa di hash è O (1).

Quindi abbiamo il riempimento hashmap: O (n log n) con ricerca O (1).

Oppure il modo standard (compilare O (1) ricerca O (n)).

Tuttavia, poiché la ricerca O (n) avviene per tutte le stringhe, il primo metodo in totale è O (numberOfInvalidChars + stringhe * NumberofInValidChars) il secondo è O (numInv log numInv + stringhe). Quale è wayyyy meno costoso quindi quasi sempre più economico.

Answer 3

C'è un metodo semplice che ti dà la complessità temporale O(n log(m)), dove n è la lunghezza dell'input e m è il numero di caratteri non consentiti.

Analizza l'input un carattere alla volta e cerca il carattere corrente nell'array (ordinato) di caratteri non consentiti utilizzando la ricerca binaria.

Answer 4

Se si usa un HashSet, che vi dà O (1) su Add e contiene voi hanno:

• O (n) per l'inserimento di ogni carattere proibito
• O (m) per ogni confronto operazione

Quale porta a O (m + n) dove m è il numero di caratteri vietati en è la lunghezza della stringa. Ma vedo già risposte migliori.

Ma tieni presente che la maggior parte delle cose ha un sovraccarico (come "hash" in HashSet/HashMap). Quindi, anche se la prestazione asintotica potrebbe essere migliore, un'implementazione ingenua potrebbe essere più veloce su piccoli input. Non sto dicendo che dovresti usare qualcosa che ha O (n²) ma potrebbe valere la pena di confrontare una soluzione O (n log n) con una soluzione O (m) per un insieme comune di dati!

Answer 5

Il più veloce! HashMap è di gran lunga la soluzione più veloce, solo teoricamente è O (1).

in Java: java.util.BitSet è stato progettato per le vostre esigenze. In alternativa utilizzare array lunghi []/int [] scartati (a seconda dell'architettura di destinazione 32/64)

Perché HashMap non è buono? Il bagaglio extra derivante dall'accesso e dalla creazione di benne è più alto di quello a destra.