Najszybszy sposób na podzielenie rozdzielanego łańcucha w Javie

10

Buduję komparator, który umożliwia sortowanie wielu kolumn na ograniczonym łańcuchu. Obecnie używam metody split z klasy String jako preferowanego sposobu dzielenia surowego ciągu na tokeny.

Czy to jest najlepszy sposób na konwersję surowego ciągu znaków na tablicę ciągu znaków? Będę sortować miliony wierszy, więc myślę, że podejście ma znaczenie.

Wydaje się, że działa dobrze i jest bardzo łatwy, ale nie ma pewności, czy w Javie jest szybszy sposób.

Oto jak działa sortowanie w moim Komparatorze:

public int compare(String a, String b) {

    String[] aValues = a.split(_delimiter, _columnComparators.length);
    String[] bValues = b.split(_delimiter, _columnComparators.length);
    int result = 0;

    for( int index : _sortColumnIndices ) {
        result = _columnComparators[index].compare(aValues[index], bValues[index]);
        if(result != 0){
            break;
        }
    }
    return result;
}

Po analizie porównawczej różnych podejść, wierzcie lub nie, metoda podziału była najszybsza przy użyciu najnowszej wersji Java. Mój ukończony komparator możesz pobrać tutaj: https://sourceforge.net/projects/multicolumnrowcomparator/

Constantin
źródło
5
Wskażę, że charakter odpowiedzi na to pytanie zależy od implementacji Jvm. Zachowanie ciągów (współużytkujących wspólną tablicę podkładową w OpenJDK, ale nie w OracleJDK) jest różne. Ta różnica może mieć znaczący wpływ na dzielenie ciągów i tworzenie podciągów, a także zbieranie pamięci i wycieki pamięci. Jak duże są te tablice? Jak się teraz masz? Czy zastanowiłbyś się nad odpowiedzią, która stwarza nowy typ łańcucha, a nie rzeczywiste ciągi Java?
1
W szczególności spójrz na StringTokenizer nextToken, który ostatecznie wywołuje pakiet prywatny konstruktor String . Porównaj to ze zmianami udokumentowanymi w Wewnętrznych zmianach w łańcuchu zmian wprowadzonych w Javie 1.7.0_06
Rozmiar tablicy zależy od liczby kolumn, więc jest zmienny. Ten wielokolumnowy komparator jest przekazywany jako parametr taki jak: ExternalSort.mergeSortedFiles (fileList, nowy plik („BigFile.csv”), _comparator, Charset.defaultCharset (), false); Zewnętrzna procedura sortowania posortuje cały ciąg wierszy, w rzeczywistości to komparator dokonuje podziału i sortowania na podstawie kolumn sortowania
Constantin,
Zastanowiłbym się, czy nie spojrzeć na tokenizery Lucene. Lucene może być używana jako potężna biblioteka do analizy tekstu, która sprawdza się zarówno w przypadku prostych, jak i złożonych zadań
Doug T.
Zastanów się nad Apache Commons Lang's StringUtils.split[PreserveAllTokens](text, delimiter).
Przywróć Monikę

Odpowiedzi:

19

Napisałem dla tego szybki i brudny test porównawczy. Porównuje 7 różnych metod, z których niektóre wymagają szczególnej wiedzy na temat dzielonych danych.

Dla podstawowego podziału ogólnego, Guava Splitter jest 3,5 razy szybszy niż String # split () i polecam go użyć. Stringtokenizer jest nieco szybszy, a dzielenie się za pomocą indexOf jest dwa razy szybsze niż ponownie.

Kod i więcej informacji można znaleźć na stronie http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance/

Tomek
źródło
Jestem tylko ciekawy, jakiego JDK używałeś ... a jeśli byłby to 1.6, byłbym najbardziej zainteresowany podsumowaniem twoich wyników w 1.7.
1
chyba 1,6. Kod jest dostępny jako test JUnit, jeśli chcesz go uruchomić w wersji 1.7. Uwaga String.split wykonuje dopasowanie wyrażenia regularnego, które zawsze będzie wolniejsze niż dzielenie na jeden zdefiniowany znak.
tom
1
Tak, ale dla 1.6, StringTokenizer (i podobne) wywołuje String.substring (), który wykonuje O (1) tworzenie nowego ciągu przy użyciu tej samej tablicy wspierającej. Zostało to zmienione w wersji 1.7, aby utworzyć kopię niezbędnej części tablicy podkładu zamiast dla O (n). Może to mieć wyjątkowy wpływ na wyniki, zmniejszając różnicę między splitem a StringTokenizer (spowalniając wszystko, co wcześniej używało podciągów).
1
Z pewnością prawda. Chodzi o to, w jaki sposób StringTokenizer przeszedł od „aby utworzyć nowy ciąg, przypisz 3 liczby całkowite” do „, aby utworzyć nowy ciąg, wykonaj kopię tablicy danych”, co zmieni szybkość tego elementu. Różnica między różnymi podejściami może być teraz mniejsza i byłoby interesujące (gdyby nie z innych powodów niż interesujące) wykonanie kontynuacji z Javą 1.7.
1
Dzięki za ten artykuł! Bardzo przydatne i posłuży do porównania różnych podejść.
Constantin,
5

Jak pisze @Tom, podejście typu indexOf jest szybsze niż String.split(), ponieważ to ostatnie zajmuje się wyrażeniami regularnymi i ma dla nich wiele dodatkowych kosztów.

Jednak jedna zmiana algorytmu, która może dać super przyspieszenie. Zakładając, że ten komparator będzie używany do sortowania ~ 100 000 ciągów, nie pisz Comparator<String>. Ponieważ w trakcie sortowania ten sam Ciąg prawdopodobnie będzie porównywany wiele razy, więc podzielisz go wiele razy itp.

Podziel wszystkie ciągi raz na String [] i Comparator<String[]>posortuj String []. Następnie możesz połączyć je wszystkie razem.

Możesz też użyć mapy do buforowania ciągu -> Ciąg [] lub odwrotnie. np. (szkicowy) Pamiętaj też, że wymieniasz pamięć na szybkość, mam nadzieję, że masz dużo pamięci RAM

HashMap<String, String[]> cache = new HashMap();

int compare(String s1, String s2) {
   String[] cached1 = cache.get(s1);
   if (cached1  == null) {
      cached1 = mySuperSplitter(s1):
      cache.put(s1, cached1);
   }
   String[] cached2 = cache.get(s2);
   if (cached2  == null) {
      cached2 = mySuperSplitter(s2):
      cache.put(s2, cached2);
   }

   return compareAsArrays(cached1, cached2);  // real comparison done here
}
użytkownik949300
źródło
to dobra uwaga.
tom
Wymagałoby to modyfikacji zewnętrznego kodu sortowania, który można znaleźć tutaj: code.google.com/p/externalsortinginjava
Constantin
1
Prawdopodobnie najłatwiej wtedy użyć mapy. Zobacz edycję.
user949300,
Biorąc pod uwagę, że jest to część zewnętrznego mechanizmu sortowania (aby poradzić sobie z znacznie większą ilością danych, niż może zmieścić się w dostępnej pamięci), naprawdę szukałem wydajnego „rozdzielacza” (tak, niepotrzebne jest wielokrotne dzielenie tego samego ciągu, stąd moje pierwotnie trzeba to zrobić tak szybko, jak to możliwe)
Constantin
Krótko przeglądając kod ExternalSort, wygląda na to, że jeśli wyczyścisz pamięć podręczną na końcu (lub na początku) każdego sortAndSave()połączenia, nie powinieneś zabraknąć pamięci z powodu ogromnej pamięci podręcznej. IMO, kod powinien zawierać kilka dodatkowych haczyków, takich jak uruchamianie zdarzeń lub wywoływanie metod chronionych przed działaniem „nic nie rób”, które użytkownicy tacy jak ty mogą zastąpić. (Ponadto nie powinny to być wszystkie metody statyczne, aby mogły to zrobić ) Możesz skontaktować się z autorami i złożyć wniosek.
user949300,
2

Według tych testów , StringTokenizer jest szybszy do dzielenia ciągów, ale nie zwraca tablicy, co czyni go mniej wygodnym.

Jeśli chcesz posortować miliony wierszy, polecam użycie RDBMS.

Tulains Córdova
źródło
3
Tak było w JDK 1.6 - rzeczy w łańcuchach są zasadniczo różne w 1.7 - patrz java-performance.info/changes-to-string-java-1-7-0_06 (w szczególności tworzenie podciągów nie jest już O (1), ale raczej O (n)). Link zauważa, że ​​w 1.6 Pattern.split używał innego String do tworzenia niż String.substring ()) - patrz kod połączony w komentarzu powyżej, aby śledzić StringTokenizer.nextToken () i prywatny konstruktor pakietu, do którego miał dostęp.
1

Jest to metoda, której używam do analizowania dużych (1 GB +) plików rozdzielanych tabulatorami. Ma znacznie mniejszy narzut niż String.split(), ale jest ograniczony do charogranicznika. Jeśli ktoś ma szybszą metodę, chciałbym ją zobaczyć. Można to również zrobić na CharSequencea CharSequence.subSequence, ale to wymaga wykonania CharSequence.indexOf(char)(patrz metody pakietu String.indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex)jeśli zainteresowany).

public static String[] split(final String line, final char delimiter)
{
    CharSequence[] temp = new CharSequence[(line.length() / 2) + 1];
    int wordCount = 0;
    int i = 0;
    int j = line.indexOf(delimiter, 0); // first substring

    while (j >= 0)
    {
        temp[wordCount++] = line.substring(i, j);
        i = j + 1;
        j = line.indexOf(delimiter, i); // rest of substrings
    }

    temp[wordCount++] = line.substring(i); // last substring

    String[] result = new String[wordCount];
    System.arraycopy(temp, 0, result, 0, wordCount);

    return result;
}
vallismortis
źródło
Czy porównałeś to z String.split ()? Jeśli tak, to jak to porównać?
Jay Elston,
@JayElston W przypadku pliku 900 MB skrócił czas podziału z 7,7 sekundy do 6,2 sekundy, czyli o około 20% szybciej. Jest to wciąż najwolniejsza część mojej analizy zmiennoprzecinkowej. Zgaduję, że większość pozostałego czasu to alokacja tablicy. Może być możliwe odcięcie przydziału macierzy przy użyciu podejścia opartego na tokenizerze z przesunięciem w metodzie - to zacznie wyglądać bardziej jak metoda cytowana powyżej kodu.
vallismortis