Kompleksitas waktu substring Java ()

Berapa kompleksitas waktu String#substring()metode di Java?

Jawaban baru

Pada pembaruan 6 dalam masa Java 7, perilaku substringdiubah untuk membuat salinan - jadi setiap Stringmengacu pada char[]yang tidak dibagikan dengan objek lain, sejauh yang saya ketahui. Jadi pada titik itu, substring()menjadi operasi O (n) di mana n adalah angka di substring.

Jawaban lama: pra-Java 7

Tidak berdokumen - tetapi dalam praktiknya O (1) jika Anda menganggap pengumpulan sampah tidak diperlukan, dll.

Ini hanya membangun Stringobjek baru yang mengacu pada dasar yang sama char[]tetapi dengan nilai offset dan hitungan yang berbeda. Jadi biaya adalah waktu yang dibutuhkan untuk melakukan validasi dan membangun satu objek baru (cukup kecil). Itu O (1) sejauh masuk akal untuk membicarakan kompleksitas operasi yang dapat bervariasi dalam waktu berdasarkan pengumpulan sampah, cache CPU, dll. Secara khusus, ini tidak secara langsung bergantung pada panjang string asli atau substring .

Itu adalah O (1) di versi Java yang lebih lama - seperti yang dikatakan Jon, itu hanya membuat String baru dengan karakter dasar yang sama [], dan offset dan panjang yang berbeda.

Namun, ini sebenarnya telah berubah dimulai dengan Java 7 update 6.

Pembagian karakter [] dihilangkan, dan bidang offset dan panjang telah dihapus. substring () sekarang hanya menyalin semua karakter ke dalam String baru.

Ergo, substring adalah O (n) di Java 7 update 6

Sekarang kompleksitas linier. Ini terjadi setelah memperbaiki masalah kebocoran memori untuk substring.

Jadi dari Java 1.7.0_06 ingat bahwa String.substring sekarang memiliki kompleksitas linier, bukan yang konstan.

Menambahkan bukti pada jawaban Jon. Saya memiliki keraguan yang sama dan ingin memeriksa apakah panjang string memiliki efek pada fungsi substring. Kode berikut ditulis untuk memeriksa substring parameter mana yang sebenarnya bergantung.

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

}

Output dari eksekusi di Java 8 adalah:

 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

Membuktikan fungsi substring bergantung pada panjang substring yang diminta, bukan pada panjang string.

O (1) karena tidak ada penyalinan string asli yang dilakukan, itu hanya membuat objek pembungkus baru dengan informasi offset berbeda.

Nilailah diri Anda sendiri dari mengikuti, tetapi kelemahan performa Java terletak di tempat lain, bukan di substring string. Kode:

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

Keluaran:

substring 32768 kali
Jumlah panjang split = 1494414
Berlalu 2,446679 ms

Apakah O (1) atau tidak, tergantung. Jika Anda hanya mereferensikan String yang sama di memori, lalu bayangkan String yang sangat panjang, Anda membuat substring dan berhenti mereferensikan yang panjang. Bukankah menyenangkan untuk melepaskan memori untuk waktu yang lama?

Sebelum Java 1.7.0_06: O (1).

Setelah Java 1.7.0_06: O (n). Ini diubah, karena kebocoran memori. Setelah bidang offsetdan countdihapus dari String, implementasi substring menjadi O (n).

Untuk detail lebih lanjut, silakan merujuk ke: http://java-performance.info/changes-to-string-java-1-7-0_06/