Wie finde ich Duplikate in einer Zeichenfolge?

Question

Ich möchte herausfinden, ob eine Zeichenfolge, die getrennt Komma enthält nur die gleichen Werte:

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

Hier ist die zweite Zeichenfolge enthält nur das Wort „Test“. Ich möchte diese Zeichenfolgen identifizieren.

Da ich über 100 GB iterieren möchte, spielt die Leistung eine große Rolle.

Welches ist der schnellste Weg, um ein boolean Ergebnis zu bestimmen, wenn die Zeichenfolge wiederholt nur einen Wert enthält?

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

Keine Notwendigkeit, die Zeichenfolge überhaupt zu teilen, in der Tat keine Notwendigkeit für eine String-Manipulation.

• Finden Sie das erste Wort (indexOf Komma).
• Überprüfen Sie die verbleibende Zeichenfolge Länge ist ein genaues Vielfaches dieses Wortes + das trennende Komma. (d. h. length-1 % (foundLength+1)==0)
• Schleife durch den Rest der Zeichenfolge, die das gefundene Wort für jeden Teil der Zeichenfolge überprüft. Behalte einfach zwei Indizes in der gleichen Zeichenfolge und verschiebe sie beide durch. Stellen Sie sicher, dass Sie auch die Kommas überprüfen (d. H. bob,bob,bob entspricht nicht bob,bobabob).
• Wie assylias dort darauf hingewiesen, besteht keine Notwendigkeit, die Zeiger zurückgesetzt, so dass sie durch den String nur laufen lassen und die 1. mit 2., 2. mit 3. vergleichen usw.

Beispiel Schleifen, müssen Sie zwicken die genaue Position von startPos auf das erste Zeichen nach dem ersten Komma Punkt:

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

Sie werden es nicht in der Lage sein, schneller zu tun viel, als dies das Format der eingehenden Daten gegeben in ankommen, aber Sie können es tun mit einem einzigen linearen Scan. Die Längenprüfung wird sofort viele nicht übereinstimmende Fälle eliminieren, was eine einfache Optimierung darstellt.

Answer 2

Der Aufruf split ist möglicherweise teuer - vor allem, wenn es sich um Daten von 200 GB handelt.

Betrachten wir so etwas wie unten (nicht getestet und möglicherweise ein wenig zwicken die Indexwerte erfordern, aber ich denke, Sie bekommen die Idee wird) -

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

Komplexität O (n) - vorausgesetzt, Java-Implementierungen von substring ist effizient. Wenn nicht, können Sie Ihre eigene substring Methode schreiben, die die erforderliche Anzahl von Zeichen aus dem String übernimmt.

Answer 3

für einen Riss nur eine Zeile Code:

(@ Tim Antwort ist effizienter)

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