metodo più efficace per trovare il personaggio più comune in una stringa

Question

ho creato un metodo per trovare il personaggio più comune in una stringa:

public static char getMax(String s) { 

char maxappearchar = ' '; 
int counter = 0; 
int[] charcnt = new int[Character.MAX_VALUE + 1]; 


for (int i = 0 ; i < s.length() ; i++) 
{ 
    char ch = s.charAt(i); 
    // increment this character's cnt and compare it to our max. 
    charcnt[ch]++ ; 
    if (charcnt[ch] >= counter) 
    { 
     counter = charcnt[ch]; 
     maxappearchar = ch; 
    } 
} 
System.out.println("the max char is " +maxappearchar + " and displayed " +counter+ " times"); 
return maxappearchar; 
} 

sto chiedendo informazioni sulle soluzioni differenti per esso:

• soluzione 1 - codice più veloce (è che il mio codice allegato?)
• soluzione 2 - più efficace in termini di memoria, ha ridotto l'uso di array e variabili

Ho creato il mio metodo usando HashMap - è più adatto alla soluzione 2? Se è così, perché? E quali sono i pro/contro?

Il codice allegato è adatto per o Tecnica (o ^, o logn ...)? Se è così, perché?

Answer 1

Il modo più veloce per fare ciò è contare le occorrenze di ogni carattere, quindi prendere il valore massimo nell'array dei conteggi. Se la tua stringa è lunga, otterrai un discreto aumento di velocità dal mancato rilevamento del massimo corrente mentre esegui il looping sui caratteri nella stringa.

Vedere How to count frequency of characters in a string? per molte altre idee su come contare le frequenze.

Se le stringhe sono per lo più ASCII, un ramo nel ciclo di conteggio per scegliere tra una matrice per i valori di 128 caratteri bassi o una HashMap per il resto, dovrebbe valerne la pena. Il ramo predice bene se le tue stringhe non hanno caratteri non ASCII. Se c'è molto alternanza tra ascii e non-ascii, il ramo potrebbe fare male un po ', rispetto all'utilizzo di HashMap per tutto.

public static char getMax(String s) { 

    char maxappearchar = ' '; 
    int counter = 0; 
    int[] ascii_count = new int[128]; // fast path for ASCII 
    HashMap<Character,Integer> nonascii_count = new HashMap<Character,Integer>(); 

    for (int i = 0 ; i < s.length() ; i++) 
    { 
     char ch = s.charAt(i); // This does appear to be the recommended way to iterate over a String 
     // alternatively, iterate over 32bit Unicode codepoints, not UTF-16 chars, if that matters. 
     if (ch < 128) { 
      ascii_count[ch]++; 
     } else { 
      // some code to set or increment the nonascii_count[ch]; 
     } 
    } 

    // loop over ascii_count and find the highest element 
    // loop over the keys in nonascii_count, and see if any of them are even higher. 
    return maxappearchar; 
} 

non ho rimpolpare il codice, dal momento che non faccio un sacco di Java, quindi IDK se c'è un contenitore che può fare l'operazione Inserisci- 1 -o-incremento più efficiente di una HashMap get e put coppia. https://stackoverflow.com/a/6712620/224132 suggerisce Guava MultiSet<Character>, che sembra buono.

---

Questo può fare meglio di vostra scelta di 2^16 int s. Tuttavia, se si toccano solo i 128 elementi bassi di questo array, la maggior parte della memoria non può mai essere toccata. La memoria allocata ma non toccata non fa davvero male, o consuma RAM/swap.

Tuttavia, il loop su tutte le 65536 voci alla fine significa almeno leggerlo, quindi il sistema operativo dovrebbe inserire la pagina e inserirla. E inquinerà le cache. Quindi, in realtà, aggiornare il massimo su ogni personaggio potrebbe essere una scelta migliore. Microbenchmarks potrebbe mostrare che l'iterazione su String, quindi il looping su charcnt[Character.MAX_VALUE] vince, ma che non avrebbe tenuto conto dell'inquinamento di cache/TLB di toccare quella memoria non tanto necessaria.

Answer 2

È un algoritmo veloce che utilizza molto spazio.

Non copre Unicode completo, ci sono punti di codice (caratteri Unicode, interi) che richiedono due caratteri.

piccole ottimizzazioni ancora possibile:

• Fare versioni in più con byte[] e short[], a seconda s.length().

• Mantenere la length() in una variabile

  for (int i = 0, n = s.length(); i < n; i++) 
  

E sì un HashMap probabilmente è la soluzione più "sensibili".

Ora con java 8, è possibile passare al parallelismo: utilizzando più core. Non ne vale la pena.

int mostFrequentCodePoint = s.codePoints() 
    ... 

Per l'analisi della frequenza in linguaggio naturale, può essere sufficiente limitare la lunghezza della stringa a circa 1000.

Answer 3

Utilizzando la soluzione di cui sopra restituisce un SimpleEntry<Character,Integer> (piena attuazione) per ASCII:

public static Map.Entry getMostCommonChar(String phrase) { 
    if (phrase == null || phrase.isEmpty()) { 
     throw new IllegalArgumentException("input phrase must have non-empty value."); 
    } 

    char maxchar = ' '; 
    int counter = 0; 
    int[] ascii_count = new int[Character.MAX_VALUE]; // fast path for ASCII 

    for (int i = 0; i < phrase.length(); i++) { 
     char ch = phrase.charAt(i); // This does appear to be the recommended way to iterate over a String 
     if (ascii_count[ch]++ >= counter) { 
      counter = ascii_count[ch]; 
      maxchar = ch; 
     } 
    } 

    Map.Entry<Character,Integer> e = new AbstractMap.SimpleEntry<>(maxchar,counter); 

    System.out.println(e.getKey()); 
    System.out.println(e.getValue()); 

    return e; 
}