Come trovare i duplicati all'interno di una stringa?

Question

Voglio scoprire se una stringa che viene separato da virgole contiene solo gli stessi valori:

test,asd,123,test 
test,test,test 

Qui la seconda stringa contiene solo la parola "test". Mi piacerebbe identificare queste stringhe.

Come voglio ripetere oltre 100 GB, le prestazioni sono importanti.

Quale potrebbe essere il modo più veloce per determinare un risultato boolean se la stringa contiene un solo valore ripetutamente?

public static boolean stringHasOneValue(String string) { 
    String value = null; 
    for (split : string.split(",")) { 
     if (value == null) { 
     value = split; 
     } else { 
     if (!value.equals(split)) return false; 
     } 
    } 
    return true; 
} 

Answer 1

Non è necessario dividere la stringa, in realtà non è necessario alcun tipo di manipolazione delle stringhe.

• Trova la prima parola (indexOf virgola).
• Verificare che la lunghezza della stringa rimanente sia un multiplo esatto di quella parola + la virgola di separazione. (ad esempio length-1 % (foundLength+1)==0)
• Passare attraverso il resto della stringa controllando la parola trovata contro ogni parte della stringa. Basta tenere due indici nella stessa stringa e spostarli entrambi attraverso di essa. Assicurati di controllare anche le virgole (ad esempio bob,bob,bob corrisponde a bob,bobabob).
• Come assylias rilevare v'è alcuna necessità di reimpostare i puntatori, basta lasciarli correre attraverso la stringa e confrontare il 1 ° con 2 °, 2 ° con 3 °, ecc

ciclo esempio, sarà necessario modificare la posizione esatta di startPos per puntare al primo carattere dopo la prima virgola:

for (int i=startPos;i<str.length();i++) { 
    if (str.charAt(i) != str.charAt(i-startPos)) { 
     return false; 
    } 
} 
return true; 

non sarà in grado di farlo molto più veloce di questo dato il formato dei dati è in arrivo in, ma si può fare con una singola scansione lineare. Il controllo della lunghezza eliminerà immediatamente molti casi non corrispondenti, quindi è una semplice ottimizzazione.

Answer 2

Chiamare split potrebbe essere costoso, soprattutto se si tratta di dati di 200 GB.

considerare qualcosa come qui di seguito (non testato e potrebbe richiedere un po 'di tweaking i valori di indice, ma penso che si ottiene l'idea) -

public static boolean stringHasOneValue(String string) { 

     String seperator = ","; 
     int firstSeparator = string.indexOf(seperator); //index of the first separator i.e. the comma 
     String firstValue = string.substring(0, firstSeparator); // first value of the comma separated string 
     int lengthOfIncrement = firstValue.length() + 1; // the string plus one to accommodate for the comma 

     for (int i = 0 ; i < string.length(); i += lengthOfIncrement) { 
      String currentValue = string.substring(i, firstValue.length()); 
      if (!firstValue.equals(currentValue)) { 
       return false; 
      } 
     } 

     return true; 
    } 

complessità O (n) - ipotizzando implementazioni Java di substring è efficiente In caso contrario, è possibile scrivere il proprio metodo substring che accetta il numero richiesto di caratteri dalla stringa.

Answer 3

per una crepa solo un codice di linea:

(risposta @ Tim è più efficiente)

System.out.println((new HashSet<String>(Arrays.asList("test,test,test".split(","))).size()==1));