Jaki jest najłatwiejszy / najlepszy / najbardziej poprawny sposób na iterację znaków ciągu znaków w Javie?

341

StringTokenizer? Konwertuj na Stringa char[]i powtórzyć? Coś innego?

Paul Wicks
źródło
3
Zobacz także stackoverflow.com/questions/1527856/…
rogerdpack
1
Zobacz także stackoverflow.com/questions/8894258/... Testy porównawcze pokazują, że String.charAt () jest najszybszy dla małych łańcuchów, a użycie odbicia do bezpośredniego odczytu tablicy znaków jest najszybszy dla dużych łańcuchów.
Jonathan
Zobacz także Jak zamienić ciąg w strumień w Javie?
Dangermouse,

Odpowiedzi:

363

Używam pętli for do iteracji łańcucha i używam charAt()do tego, aby każdy znak go zbadał. Ponieważ String jest implementowany za pomocą tablicy, charAt()metoda jest operacją o stałym czasie.

String s = "...stuff...";

for (int i = 0; i < s.length(); i++){
    char c = s.charAt(i);        
    //Process char
}

Tak bym zrobił. Wydaje mi się to najłatwiejsze.

Jeśli chodzi o poprawność, nie wierzę, że tu istnieje. Wszystko opiera się na twoim osobistym stylu.

jjnguy
źródło
3
Czy kompilator wstawia metodę length ()?
Uri
7
może wstawić length (), czyli podnieść metodę stojącą za tym wywołaniem kilku ramek, ale bardziej wydajne jest to zrobić dla (int i = 0, n = s.length (); i <n; i ++) {char c = s.charAt (i); }
Dave Cheney
32
Zaśmiecanie kodu dla niewielkiego wzrostu wydajności. Unikaj tego, dopóki nie zdecydujesz, że ten obszar kodu ma krytyczne znaczenie dla szybkości.
szczupły
31
Zauważ, że ta technika daje ci znaki , a nie punkty kodowe , co oznacza, że ​​możesz otrzymać surogaty.
Gabe
2
@ikh charAt is not O (1) : Jak to jest? Kod dla String.charAt(int)po prostu działa value[index]. Myślę, że mylisz się chatAt()z czymś innym, co daje ci punkty kodowe.
antak
209

Dwie opcje

for(int i = 0, n = s.length() ; i < n ; i++) { 
    char c = s.charAt(i); 
}

lub

for(char c : s.toCharArray()) {
    // process c
}

Pierwszy jest prawdopodobnie szybszy, a następnie drugi jest prawdopodobnie bardziej czytelny.

Dave Cheney
źródło
26
plus jeden za umieszczenie s.length () w wyrażeniu inicjalizacji. Jeśli ktoś nie wie, dlaczego, to dlatego, że jest to oceniane tylko raz, gdy zostanie umieszczone w instrukcji zakończenia jako i <s.length (), to s.length () będzie wywoływana za każdym razem, gdy zostanie zapętlona.
Dennis
57
Myślałem, że optymalizacja kompilatora zajęła się tym za Ciebie.
Rhyous,
4
@Matthias Za pomocą dezasemblera klasy Javap można się przekonać, że rzeczywiście uniknięto powtarzania wywołań funkcji s.length () w celu wyrażenia zakończenia pętli. Zauważ, że w opublikowanym kodzie OP wywołanie s.length () znajduje się w wyrażeniu inicjalizacji, więc semantyka języka już gwarantuje, że zostanie wywołana tylko raz.
prasopes
3
@prasopes Zauważ jednak, że większość optymalizacji java odbywa się w czasie wykonywania, NIE w plikach klas. Nawet jeśli widziałeś powtarzające się wywołania funkcji length (), które niekoniecznie oznaczają karę czasu wykonywania.
Izaak,
2
@Lasse, przypuszczalnym powodem jest wydajność - twoja wersja wywołuje metodę length () przy każdej iteracji, podczas gdy Dave wywołuje ją raz w inicjalizatorze. To powiedziawszy, jest bardzo prawdopodobne, że optymalizator JIT („just in time”) zoptymalizuje dodatkowe wywołanie, więc prawdopodobnie jest to tylko różnica w czytelności bez rzeczywistego zysku.
Steve,
90

Zauważ, że większość innych opisanych tutaj technik psuje się, jeśli masz do czynienia ze znakami spoza BMP (Unicode Basic Multilingual Plane ), tj. Punktami kodowymi które znajdują się poza zakresem u0000-uFFFF. Zdarza się to rzadko, ponieważ punkty kodu poza tym są w większości przypisane do martwych języków. Ale poza tym jest kilka użytecznych znaków, na przykład niektóre punkty kodowe używane do notacji matematycznej, a niektóre do kodowania prawidłowych nazw w języku chińskim.

W takim przypadku Twój kod będzie:

String str = "....";
int offset = 0, strLen = str.length();
while (offset < strLen) {
  int curChar = str.codePointAt(offset);
  offset += Character.charCount(curChar);
  // do something with curChar
}

Character.charCount(int)Metoda wymaga Java 5+.

Źródło: http://mindprod.com/jgloss/codepoint.html

sk.
źródło
1
Nie rozumiem, jak używasz niczego poza Podstawowym wielojęzycznym samolotem tutaj. curChar ma nadal 16 bitów righ?
Umowa prof. Falkena została naruszona
2
Albo używasz int, aby zapisać cały punkt kodowy, albo każdy znak zapisze tylko jedną z dwóch par zastępczych, które definiują punkt kodowy.
sk.
1
Myślę, że muszę przeczytać o kodach i parach zastępczych. Dzięki!
Umowa prof. Falkena została złamana
6
+1, ponieważ wydaje się, że jest to jedyna odpowiedź, która jest poprawna dla znaków Unicode poza BMP
Jason S
Napisałem kod, aby zilustrować koncepcję iteracji w punktach kodowych
Emmanuel Oga
26

Zgadzam się, że StringTokenizer ma tutaj nadmiar. Właściwie wypróbowałem powyższe sugestie i poświęciłem trochę czasu.

Mój test był dość prosty: utwórz StringBuilder z około milionem znaków, przekonwertuj go na String i przejrzyj każdy z nich za pomocą charAt () / po konwersji na tablicę char / z CharacterIteratorem tysiąc razy (oczywiście upewniając się, że zrób coś z łańcucha, aby kompilator nie mógł zoptymalizować całej pętli :-)).

Wynik na moim Powerbooku 2,6 GHz (to Mac :-)) i JDK 1.5:

  • Test 1: charAt + String -> 3138msec
  • Test 2: Ciąg przekonwertowany na tablicę -> 9568 ms
  • Test 3: StringBuilder charAt -> 3536msec
  • Test 4: CharacterIterator i łańcuch -> 12151 ms

Ponieważ wyniki różnią się znacznie, najszybszy wydaje się również najprostszy sposób. Co ciekawe, charAt () StringBuilder wydaje się być nieco wolniejszy niż String.

BTW Sugeruję, aby nie używać CharacterIteratora, ponieważ uważam, że nadużywanie znaku „\ uFFFF” jako „koniec iteracji” jest naprawdę okropnym włamaniem. W dużych projektach zawsze jest dwóch facetów, którzy używają tego samego rodzaju hacka do dwóch różnych celów, a kod ulega awarii w bardzo tajemniczy sposób.

Oto jeden z testów:

    int count = 1000;
    ...

    System.out.println("Test 1: charAt + String");
    long t = System.currentTimeMillis();
    int sum=0;
    for (int i=0; i<count; i++) {
        int len = str.length();
        for (int j=0; j<len; j++) {
            if (str.charAt(j) == 'b')
                sum = sum + 1;
        }
    }
    t = System.currentTimeMillis()-t;
    System.out.println("result: "+ sum + " after " + t + "msec");

źródło
1
Ma to ten sam problem opisany tutaj: stackoverflow.com/questions/196830/...
Emmanuel Oga
22

W Javie 8 możemy to rozwiązać jako:

String str = "xyz";
str.chars().forEachOrdered(i -> System.out.print((char)i));
str.codePoints().forEachOrdered(i -> System.out.print((char)i));

Metoda chars () zwraca IntStreamjak wspomniano w doc :

Zwraca strumień int rozszerzający zero wartości char z tej sekwencji. Każdy znak odwzorowany na zastępczy punkt kodowy jest przekazywany przez niezinterpretowany. Jeśli sekwencja zostanie zmutowana podczas odczytywania strumienia, wynik jest niezdefiniowany.

Metoda codePoints()zwraca również IntStreamjak na dokument:

Zwraca strumień wartości punktów kodowych z tej sekwencji. Wszelkie pary zastępcze napotkane w sekwencji są łączone tak, jak przez Character.toCodePoint, a wynik jest przekazywany do strumienia. Wszelkie inne jednostki kodu, w tym zwykłe znaki BMP, niesparowane parametry zastępcze i niezdefiniowane jednostki kodu, są rozszerzane od zera do wartości int, które są następnie przekazywane do strumienia.

Czym różni się znak i kod? Jak wspomniano w tym artykule:

Unicode 3.1 dodał dodatkowe znaki, zwiększając całkowitą liczbę znaków do ponad 216 znaków, które można rozróżnić za pomocą pojedynczego 16-bitowego char. Dlatego charwartość nie ma już odwzorowania jeden na jeden do podstawowej jednostki semantycznej w Unicode. JDK 5 został zaktualizowany, aby obsługiwał większy zestaw wartości znaków. Zamiast zmiany definicji chartypu, niektóre nowe znaki dodatkowe są reprezentowane przez zastępczą parę dwóch charwartości. Aby zmniejszyć zamieszanie związane z nazywaniem, punkt kodowy będzie używany w odniesieniu do liczby reprezentującej określony znak Unicode, w tym znaki uzupełniające.

Wreszcie dlaczego, forEachOrdereda nie forEach?

Zachowanie forEachjest wyraźnie niedeterministyczne, gdy jako forEachOrderedwykonuje akcję dla każdego elementu tego strumienia, w kolejności spotkań strumienia, jeśli strumień ma zdefiniowaną kolejność spotkań. Tak forEachnie gwarantuje, że zamówienie zostanie utrzymane. Sprawdź również to pytanie, aby uzyskać więcej.

W przypadku różnicy między znakiem, punktem kodowym, glifem i grafemem sprawdź to pytanie .

akhil_mittal
źródło
21

Istnieje kilka dedykowanych klas do tego:

import java.text.*;

final CharacterIterator it = new StringCharacterIterator(s);
for(char c = it.first(); c != CharacterIterator.DONE; c = it.next()) {
   // process c
   ...
}
Bruno De Fraine
źródło
7
Wygląda jak przesada dla czegoś tak prostego jak iteracja nad niezmienną tablicą znaków.
ddimitrov
1
Nie rozumiem, dlaczego to przesada. Iteratory to najbardziej zaawansowany java sposób na zrobienie czegokolwiek ... iteracyjnego. StringCharacterIterator musi w pełni wykorzystać niezmienność.
szczupły
2
Zgadzam się z @ddimitrov - to przesada. Jedynym powodem użycia iteratora byłoby skorzystanie z foreach, które jest nieco łatwiejsze do „zobaczenia” niż pętla for. Jeśli mimo wszystko zamierzasz napisać konwencjonalną pętlę for, równie dobrze możesz użyć charAt ()
Rob Gilliam
3
Korzystanie z iteratora znaków jest prawdopodobnie jedynym poprawnym sposobem na iterację znaków, ponieważ Unicode wymaga więcej miejsca niż Java char. Java charzawiera 16 bitów i może przechowywać znaki Unicode do U + FFFF, ale Unicode określa znaki do U + 10FFFF. Użycie 16 bitów do kodowania Unicode powoduje kodowanie znaków o zmiennej długości. Większość odpowiedzi na tej stronie zakłada, że ​​kodowanie Java jest kodowaniem o stałej długości, co jest nieprawidłowe.
ceving
3
@ceving Wydaje się, że iterator znaków nie pomoże ci ze znakami spoza BMP: oracle.com/us/technologies/java/supplementary-142654.html
Bruno De Fraine
18

Jeśli masz Guava na swojej ścieżce klas, poniższe informacje są dość czytelną alternatywą. Guava ma nawet dość rozsądną implementację Listy niestandardowej w tym przypadku, więc nie powinno to być nieefektywne.

for(char c : Lists.charactersOf(yourString)) {
    // Do whatever you want     
}

AKTUALIZACJA: Jak zauważył @Alex, w Javie 8 jest także CharSequence#charsdo użycia. Nawet typ to IntStream, więc można go odwzorować na znaki takie jak:

yourString.chars()
        .mapToObj(c -> Character.valueOf((char) c))
        .forEach(c -> System.out.println(c)); // Or whatever you want
Touko
źródło
Jeśli potrzebujesz zrobić coś skomplikowanego, skorzystaj z pętli for + guava, ponieważ nie możesz mutować zmiennych (np. Liczb całkowitych i ciągów) zdefiniowanych poza zakresem forEach wewnątrz forEach. Wszystko, co znajduje się w forEach, również nie może rzucać sprawdzonych wyjątków, więc czasami jest to również denerwujące.
sabujp
13

Jeśli potrzebujesz iterować przez punkty kodu String(zobacz tę odpowiedź ), krótszym / bardziej czytelnym sposobem jest użycie CharSequence#codePointsmetody dodanej w Javie 8:

for(int c : string.codePoints().toArray()){
    ...
}

lub używając strumienia bezpośrednio zamiast pętli for:

string.codePoints().forEach(c -> ...);

Jest również, CharSequence#charsjeśli chcesz strumień znaków (choć jest to IntStream, ponieważ nie ma CharStream).

Alex
źródło
3

Nie użyłbym tego, StringTokenizerponieważ jest to jedna z klas w JDK, która jest dziedzictwem.

Jawadok mówi:

StringTokenizerjest klasą starszą, która jest zachowywana ze względu na kompatybilność, chociaż jej użycie jest odradzane w nowym kodzie. Zaleca się, aby każdy, kto szuka tej funkcji, używał metody podziału Stringlub java.util.regexpakietu.

Alan
źródło
Tokenizer ciągów jest w pełni poprawnym (i bardziej wydajnym) sposobem na iterację po tokenach (tj. Słowach w zdaniu.) Jest to zdecydowanie przesada w iteracji po znakach. Głosuję twój komentarz za mylący.
ddimitrov
3
ddimitrov: Nie podążam za wskazaniem, że StringTokenizer nie jest zalecany, W TYM cytat z JavaDoc ( java.sun.com/javase/6/docs/api/java/util/StringTokenizer.html ), ponieważ oświadczenie to jest takie zwodniczy. Przesunięty na offset.
Władca
1
Dzięki, panie Bemrose ... Rozumiem, że cytowany cytat blokowy powinien być krystalicznie czysty, przy czym prawdopodobnie należy wywnioskować, że aktywne poprawki błędów nie zostaną zatwierdzone przez StringTokenizer.
Alan
2

Jeśli potrzebujesz wydajności, musisz przetestować środowisko. Żaden inny sposób.

Oto przykładowy kod:

int tmp = 0;
String s = new String(new byte[64*1024]);
{
    long st = System.nanoTime();
    for(int i = 0, n = s.length(); i < n; i++) {
        tmp += s.charAt(i);
    }
    st = System.nanoTime() - st;
    System.out.println("1 " + st);
}

{
    long st = System.nanoTime();
    char[] ch = s.toCharArray();
    for(int i = 0, n = ch.length; i < n; i++) {
        tmp += ch[i];
    }
    st = System.nanoTime() - st;
    System.out.println("2 " + st);
}
{
    long st = System.nanoTime();
    for(char c : s.toCharArray()) {
        tmp += c;
    }
    st = System.nanoTime() - st;
    System.out.println("3 " + st);
}
System.out.println("" + tmp);

W Javie online otrzymuję:

1 10349420
2 526130
3 484200
0

Na Androida x86 API 17 otrzymuję:

1 9122107
2 13486911
3 12700778
0
Enyby
źródło
0

Zobacz samouczki Java: ciągi .

public class StringDemo {
    public static void main(String[] args) {
        String palindrome = "Dot saw I was Tod";
        int len = palindrome.length();
        char[] tempCharArray = new char[len];
        char[] charArray = new char[len];

        // put original string in an array of chars
        for (int i = 0; i < len; i++) {
            tempCharArray[i] = palindrome.charAt(i);
        } 

        // reverse array of chars
        for (int j = 0; j < len; j++) {
            charArray[j] = tempCharArray[len - 1 - j];
        }

        String reversePalindrome =  new String(charArray);
        System.out.println(reversePalindrome);
    }
}

Włóż długość int leni użyj forpętli.

Eugene Yokota
źródło
1
Zaczynam czuć się trochę spamer ... jeśli jest takie słowo :). Ale w tym rozwiązaniu pojawia się problem opisany tutaj: Ten sam problem opisany tutaj: stackoverflow.com/questions/196830/...
Emmanuel Oga
0

StringTokenizer jest całkowicie nieodpowiedni do zadania dzielenia łańcucha na poszczególne znaki. Dzięki temu String#split()możesz to zrobić łatwo, używając wyrażenia regularnego, które nie pasuje do niczego, np .:

String[] theChars = str.split("|");

Jednak StringTokenizer nie używa wyrażeń regularnych i nie można określić łańcucha ogranicznika, który pasowałby do niczego między znakami. Jest to jeden śliczny włamać można użyć, aby osiągnąć to samo: użyj sam ciąg jako ciąg ogranicznika (zrobienie każdy znak w nim separatorem) i dokonania ich zwrotu ograniczników:

StringTokenizer st = new StringTokenizer(str, str, true);

Jednak wymieniam te opcje tylko w celu ich odrzucenia. Obie techniki dzielą oryginalny ciąg na ciągi jednoznakowe zamiast prymitywów znaków i oba wymagają dużego nakładu pracy w postaci tworzenia obiektów i manipulacji ciągami. Porównaj to z wywołaniem charAt () w pętli for, która praktycznie nie wiąże się z narzutem.

Alan Moore
źródło
0

Opracowywanie tej odpowiedzi i tej odpowiedzi .

Powyższe odpowiedzi wskazują na problem wielu rozwiązań, które nie powtarzają się według wartości punktowej kodu - miałyby problem z dowolnymi znakami zastępczymi . Dokumenty Java również opisują ten problem tutaj (patrz „Reprezentacje znaków Unicode”). Tak czy inaczej, oto kod, który używa niektórych rzeczywistych znaków zastępczych z dodatkowego zestawu Unicode i konwertuje je z powrotem na ciąg. Zauważ, że .toChars () zwraca tablicę znaków: jeśli masz do czynienia z surogatami, koniecznie będziesz mieć dwa znaki. Ten kod powinien działać dla każdego znaku Unicode.

    String supplementary = "Some Supplementary: 𠜎𠜱𠝹𠱓";
    supplementary.codePoints().forEach(cp -> 
            System.out.print(new String(Character.toChars(cp))));
Hawkeye Parker
źródło
0

Ten przykładowy kod pomoże ci!

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class Solution {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        map.put("a", 10);
        map.put("b", 30);
        map.put("c", 50);
        map.put("d", 40);
        map.put("e", 20);
        System.out.println(map);

        Map sortedMap = sortByValue(map);
        System.out.println(sortedMap);
    }

    public static Map sortByValue(Map unsortedMap) {
        Map sortedMap = new TreeMap(new ValueComparator(unsortedMap));
        sortedMap.putAll(unsortedMap);
        return sortedMap;
    }

}

class ValueComparator implements Comparator {
    Map map;

    public ValueComparator(Map map) {
        this.map = map;
    }

    public int compare(Object keyA, Object keyB) {
        Comparable valueA = (Comparable) map.get(keyA);
        Comparable valueB = (Comparable) map.get(keyB);
        return valueB.compareTo(valueA);
    }
}
devDeejay
źródło
0

Tak więc zazwyczaj są dwa sposoby na iterację poprzez ciąg w java, na który już odpowiedział wiele osób tutaj w tym wątku, wystarczy dodać moją wersję. Najpierw używa

String s = sc.next() // assuming scanner class is defined above
for(int i=0; i<s.length; i++){
     s.charAt(i)   // This being the first way and is a constant time operation will hardly add any overhead
  }

char[] str = new char[10];
str = s.toCharArray() // this is another way of doing so and it takes O(n) amount of time for copying contents from your string class to character array

Jeśli w grę wchodzi wydajność, zalecam używanie pierwszej w stałym czasie, jeśli nie jest, wówczas korzystanie z drugiej ułatwia pracę, biorąc pod uwagę niezmienność klas łańcuchów w Javie.

Sumit Kapoor
źródło