Złożoność czasowa podłoży Javy()

Question

Jaka jest złożoność czasu metody String#substring() w Javie?

Answer 1

Nowa odpowiedź

Jak aktualizacji 6 w Java 7 za życia, zachowanie substring zmieniony, aby utworzyć kopię - więc każdy String odnosi się do char[] która nie wspólny z żadnym innym obiektem, jak o ile wiem. W tym momencie substring() stała się operacją O (n), gdzie n to liczby w podciągach.

Old odpowiedź: pre-Java 7

Undocumented - ale w praktyce O (1), jeśli nie ponoszą śmieci wymagane jest gromadzenie, itp

To po prostu buduje nowy obiekt nawiązujący do String ten sam podstawowy char[], ale z różnymi wartościami przesunięcia i zliczenia. Koszt to czas potrzebny na przeprowadzenie walidacji i skonstruowanie pojedynczego nowego (stosunkowo małego) obiektu. To jest O (1), o ile rozsądnie jest mówić o złożoności operacji, które mogą zmieniać się w czasie w zależności od zbierania śmieci, pamięci podręcznych procesora itp. W szczególności nie zależy bezpośrednio od długości oryginalnego łańcucha lub podłańcucha .

Answer 2

O (1) ponieważ nie jest wykonywane kopiowanie oryginalnego ciągu, po prostu tworzy nowy obiekt opakowania z różnymi informacjami o przesunięciach.

Answer 3

Sędzia dla siebie z podążania, ale wady wydajności Java leżą gdzie indziej, nie tutaj w podciągu łańcucha. Kod:

public static void main(String[] args) throws IOException { 

     String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + 
       "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" + 
       "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx"; 
     int[] indices = new int[32 * 1024]; 
     int[] lengths = new int[indices.length]; 
     Random r = new Random(); 
     final int minLength = 6; 
     for (int i = 0; i < indices.length; ++i) 
     { 
      indices[i] = r.nextInt(longStr.length() - minLength); 
      lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength); 
     } 

     long start = System.nanoTime(); 

     int avoidOptimization = 0; 
     for (int i = 0; i < indices.length; ++i) 
      //avoidOptimization += lengths[i]; //tested - this was cheap 
      avoidOptimization += longStr.substring(indices[i], 
        indices[i] + lengths[i]).length(); 

     long end = System.nanoTime(); 
     System.out.println("substring " + indices.length + " times"); 
     System.out.println("Sum of lengths of splits = " + avoidOptimization); 
     System.out.println("Elapsed " + (end - start)/1.0e6 + " ms"); 
    } 

wyjściowa:

substring 32768 times 
Sum of lengths of splits = 1494414 
Elapsed 2.446679 ms

Jeśli jest O (1), czy też nie, zależy. Jeśli po prostu odwołujesz się do tego samego ciągu znaków w pamięci, to wyobraź sobie, że masz długi łańcuch, robisz podciąg i przestajesz odwoływać się do długiego. Czy nie byłoby miło zwolnić pamięci na długi?

Answer 4

To była O (1) w starszych wersjach Javy - jak stwierdził Jon, po prostu stworzył nowy Ciąg z tym samym podstawowym znakiem [] oraz innym przesunięciem i długością.

to jednak faktycznie zmienił rozpoczął Java 7 aktualizacji 6.

char [] dzielenie został wyeliminowany, a przesunięcie i pola długości zostały usunięte. Funkcja substring() teraz kopiuje wszystkie znaki do nowego ciągu.

Ergo podciąg O (n) w Java 7 aktualizacją 6

Answer 5

Teraz złożoność liniowa. Jest to po naprawieniu problemu z przeciekiem pamięci dla podłańcucha.

Tak więc od wersji 1.7.0_06 Java należy pamiętać, że StringSubstring ma teraz złożoność liniową zamiast stałej.