Złożoność czasowa podciągu Java ()

Odpowiedzi:

137

Nowa odpowiedź

Począwszy od aktualizacji 6 w okresie życia Java 7, zachowanie substringzmieniło się, aby utworzyć kopię - więc każdy Stringodnosi się do obiektu, char[]który nie jest współdzielony z żadnym innym obiektem, o ile wiem. Więc w tym momencie substring()stało się operacją O (n), gdzie n jest liczbami w podłańcuchu.

Stara odpowiedź: wersja przed Java 7

Nieudokumentowane - ale w praktyce O (1), jeśli zakładasz, że nie jest wymagane zbieranie śmieci itp.

Po prostu buduje nowy Stringobiekt odnoszący się do tego samego obiektu bazowego, char[]ale z różnymi wartościami przesunięcia i licznika. Zatem koszt to czas potrzebny na przeprowadzenie walidacji i skonstruowanie pojedynczego nowego (dość małego) obiektu. To jest O (1), o ile rozsądnie jest mówić o złożoności operacji, które mogą się zmieniać w czasie w zależności od czyszczenia pamięci, pamięci podręcznej procesora itp. W szczególności nie zależy to bezpośrednio od długości oryginalnego ciągu lub podłańcucha .

Jon Skeet
źródło
14
+1 za „nieudokumentowane”, co jest niefortunną słabością interfejsu API.
Raedwald,
10
To nie jest słabość. Jeśli zachowanie jest udokumentowane, a szczegóły implementacji nie, pozwala to na szybsze wdrożenia w przyszłości. Ogólnie rzecz biorąc, Java często definiuje zachowanie i pozwala implementacjom decydować, co jest najlepsze. Innymi słowy - nie powinno cię to obchodzić, przecież to Java ;-)
peenut 13.01.11
2
Dobra uwaga, nawet jeśli nie wierzę, że kiedykolwiek uda im się zrobić ten szybszy niż O (1).
abahgat
9
Nie, coś takiego powinno zostać udokumentowane. Deweloper powinien być świadomy, na wypadek gdyby planował wziąć mały podciąg z dużego ciągu, oczekując, że większy ciąg zostanie zebrany jako śmieci, tak jak w .NET.
Qwertie
1
@IvayloToskov: liczba skopiowanych znaków.
Jon Skeet
33

Było to O (1) w starszych wersjach Javy - jak stwierdził Jon, po prostu utworzył nowy ciąg z tym samym podstawowym char [] i innym przesunięciem i długością.

Jednak faktycznie zmieniło się to, począwszy od aktualizacji 6 Java 7.

Współdzielenie znaków [] zostało wyeliminowane, a pola przesunięcia i długości zostały usunięte. substring () teraz po prostu kopiuje wszystkie znaki do nowego ciągu.

Ergo, podciąg jest O (n) w Java 7 Update 6

Chi
źródło
2
+1 Tak jest rzeczywiście w ostatnich wersjach Sun Java i OpenJDK. GNU Classpath (i inne, jak przypuszczam) nadal używają starego paradygmatu. Niestety, wydaje się, że jest w tym trochę intelektualnej inercji. Nadal widzę posty z 2013 roku rekomendujące różne podejścia oparte na założeniu, że podciągi używają udostępnionego char[]...
thkala
10
Tak więc nowa wersja nie ma już złożoności O (1). Ciekawe, czy istnieje alternatywny sposób implementacji podciągów w O (1)? String.substring to niezwykle przydatna metoda.
Yitong Zhou
8

Teraz jest to złożoność liniowa. Dzieje się tak po naprawieniu problemu z wyciekiem pamięci dla podciągu.

Więc z Java 1.7.0_06 pamiętaj, że String.substring ma teraz liniową złożoność zamiast stałej.

friends.pallav
źródło
Czyli teraz jest gorzej (dla długich strun)?
Peter Mortensen,
@PeterMortensen yes.
Ido Kessler
3

Dodawanie dowodu do odpowiedzi Jona. Miałem takie same wątpliwości i chciałem sprawdzić, czy długość łańcucha ma wpływ na funkcję podciągu. Napisano następujący kod, aby sprawdzić, od którego podciągu parametrów faktycznie zależy.

import org.apache.commons.lang.RandomStringUtils;

public class Dummy {

    private static final String pool[] = new String[3];
    private static int substringLength;

    public static void main(String args[]) {
        pool[0] = RandomStringUtils.random(2000);
        pool[1] = RandomStringUtils.random(10000);
        pool[2] = RandomStringUtils.random(100000);
        test(10);
        test(100);
        test(1000);
    }

    public static void test(int val) {
        substringLength = val;
        StatsCopy statsCopy[] = new StatsCopy[3];
        for (int j = 0; j < 3; j++) {
            statsCopy[j] = new StatsCopy();
        }
        long latency[] = new long[3];
        for (int i = 0; i < 10000; i++) {
            for (int j = 0; j < 3; j++) {
                latency[j] = latency(pool[j]);
                statsCopy[j].send(latency[j]);
            }
        }
        for (int i = 0; i < 3; i++) {
            System.out.println(
                    " Avg: "
                            + (int) statsCopy[i].getAvg()
                            + "\t String length: "
                            + pool[i].length()
                            + "\tSubstring Length: "
                            + substringLength);
        }
        System.out.println();
    }

    private static long latency(String a) {
        long startTime = System.nanoTime();
        a.substring(0, substringLength);
        long endtime = System.nanoTime();
        return endtime - startTime;
    }

    private static class StatsCopy {
        private  long count = 0;
        private  long min = Integer.MAX_VALUE;
        private  long max = 0;
        private  double avg = 0;

        public  void send(long latency) {
            computeStats(latency);
            count++;
        }

        private  void computeStats(long latency) {
            if (min > latency) min = latency;
            if (max < latency) max = latency;
            avg = ((float) count / (count + 1)) * avg + (float) latency / (count + 1);
        }

        public  double getAvg() {
            return avg;
        }

        public  long getMin() {
            return min;
        }

        public  long getMax() {
            return max;
        }

        public  long getCount() {
            return count;
        }
    }

}

Wynik wykonania w Javie 8 to:

 Avg: 128    String length: 2000    Substring Length: 10
 Avg: 127    String length: 10000   Substring Length: 10
 Avg: 124    String length: 100000  Substring Length: 10

 Avg: 172    String length: 2000    Substring Length: 100
 Avg: 175    String length: 10000   Substring Length: 100
 Avg: 177    String length: 100000  Substring Length: 100

 Avg: 1199   String length: 2000    Substring Length: 1000
 Avg: 1186   String length: 10000   Substring Length: 1000
 Avg: 1339   String length: 100000  Substring Length: 1000

Funkcja sprawdzająca podciąg zależy od długości żądanego podciągu, a nie od długości ciągu.

Pavan Konduri
źródło
1

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

rodion
źródło
1

Oceń sam na podstawie podążania za nimi, ale wady wydajności Javy leżą gdzie indziej, a nie w podłańcuchu ł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");
    }

Wynik:

podciąg 32768 razy
Suma długości pęknięć = 1494414
Odpowiedź 2.446679 ms

To zależy, czy jest to O (1), czy nie. Jeśli po prostu odwołujesz się do tego samego ciągu w pamięci, wyobraź sobie bardzo długi ciąg, tworzysz podłańcuch i przestajesz odwoływać się do długiego. Czy nie byłoby miło uwolnić pamięć na długi czas?

peenut
źródło