Jak znaleźć duplikaty w ciągu znaków?

Question

Chcę dowiedzieć się, czy ciąg znaków, który jest oddzielone przecinkami zawiera tylko te same wartości:

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

Tutaj 2nd ciąg zawiera tylko słowo „test”. Chciałbym zidentyfikować te ciągi.

Ponieważ chcę iterować ponad 100 GB, wydajność ma duże znaczenie.

Jaki może być najszybszy sposób określenia wyniku boolean, jeśli ciąg zawiera tylko jedną wartość wielokrotnie?

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

Nie trzeba w ogóle rozdzielać struny, w rzeczywistości nie trzeba manipulować ciągami.

• Znajdź pierwsze słowo (indexOf przecinek).
• Sprawdź, czy pozostała długość ciągu jest dokładną wielokrotnością tego słowa + przecinkiem separującym. (tj. length-1 % (foundLength+1)==0)
• Przeprowadź pętlę przez pozostałą część łańcucha, sprawdzając znalezione słowo przed każdą częścią łańcucha. Po prostu utrzymuj dwa indeksy w tym samym ciągu i przenieś je przez oba. Sprawdź też przecinki (np. bob,bob,bob pasujące do bob,bobabob).
• Jak assylias wskazał, nie ma potrzeby, aby zresetować wskaźniki, tylko niech prowadzony przez String i porównać z 1st 2nd 3rd, 2nd z itp

przykładzie pętli, trzeba będzie dostosować dokładne położenie startPos pkt do pierwszego znaku po pierwszym przecinku:

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

nie będzie w stanie zrobić to znacznie szybciej niż ten podany format danych przychodzących przybywa, ale można to zrobić z pojedynczym skanem liniowym. Kontrola długości wyeliminuje wiele niedopasowanych przypadków natychmiast, więc jest to prosta optymalizacja.

Answer 2

Dzwonienie pod numer split może być kosztowne - szczególnie jeśli jest to 200 GB danych.

Rozważmy coś jak poniżej (nie testowane i może wymagać trochę szczypanie wartości indeksu, ale myślę, że masz pomysł) -

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

złożoność O (n) - zakładając implementacje Java substring jest wydajny. Jeśli nie - możesz napisać własną metodę substring, która pobiera wymaganą liczbę znaków z ciągu.

Answer 3

przez szparę tylko linia kodu:

(odpowiedź @Tim jest bardziej wydajny)

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