Java 서브스트링()의 시간 복잡도

Java 서브스트링()의 시간 복잡도

의 시간 복잡도는 어느 정도입니까?String#substring()메서드(Java)를 선택합니다.

새로운 답변

Java 7의 라이프 타임 내 업데이트 6을 기준으로substring복사본을 생성하도록 변경됨 - 그래서String를 참조합니다.char[]다른 물건과는 공유되지 않는 걸로 알고 있습니다그래서 그 시점에서substring()는 O(n)연산이 되었습니다.여기서 n은 서브스트링 내의 숫자입니다.

오래된 답변: Java 7 이전

문서화되어 있지 않음 - 그러나 실제로는 가비지 컬렉션이 필요하지 않다고 가정할 경우 O(1).

그것은 단지 새로운 것을 만들어 낼 뿐이다.String같은 밑바탕에 있는 것을 가리키는 것char[]오프셋 및 카운트 값이 다릅니다.따라서 비용은 검증을 수행하고 단일 새로운(합리적으로 작은) 개체를 구축하는 데 걸리는 시간입니다.가비지 컬렉션, CPU 캐시 등에 따라 시간이 달라질 수 있는 운영의 복잡성에 대해 설명하는 것이 합리적이라면 O(1)입니다.특히 원본 문자열의 길이나 하위 문자열에 직접 의존하지 않습니다.

이전 버전의 Java에서는 O(1)였습니다.Jon이 말했듯이 동일한 기본 문자[]와 다른 오프셋과 길이를 가진 새로운 String을 만들었습니다.

그러나 Java 7 업데이트 6부터 실제로 변경되었습니다.

char[] 공유가 삭제되고 오프셋 및 길이 필드가 제거되었습니다.substring()은 모든 문자를 새 문자열로 복사합니다.

Java 7 업데이트 6에서 하위 문자열은 O(n)입니다.

이제 선형 복잡도입니다.서브스트링 메모리 누전 문제를 수정한 후입니다.

따라서 Java 1.7.0_06부터는 String.substring의 복잡성이 일정하지 않고 선형으로 되어 있음을 기억하십시오.

존의 대답에 증거를 추가한다.저도 같은 의심이 들어 끈의 길이가 서브스트링 기능에 영향을 미치는지 확인하고 싶었습니다.실제로 어떤 파라미터 서브스트링이 의존하는지 확인하기 위해 다음 코드를 작성했습니다.

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

}

Java 8 실행 시 출력은 다음과 같습니다.

 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

부분 문자열 함수의 증명은 문자열 길이가 아니라 요청된 부분 문자열의 길이에 따라 달라집니다.

O(1) 원래 문자열은 복사되지 않기 때문에 오프셋 정보가 다른 새 래퍼 개체를 만들 뿐입니다.

자바의 성능상의 단점은 문자열의 하위 문자열이 아닌 다른 곳에 있습니다.코드:

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

출력:

서브스트링 32768회분할 길이의 합계 = 1494414경과시간 2.446679 밀리초

O(1)인지 아닌지는 에 따라 다릅니다.메모리 내에서 동일한 String만 참조할 경우 매우 긴 String을 상상해 서브스트링을 만들고 긴 String을 참조하지 않습니다.기억을 길게 풀면 좋지 않을까요?

Java 1.7.0_06 이전 버전: O(1)

Java 1.7.0_06 이후: O(n).메모리 누수가 원인이 되어, 이 변경은 변경되었습니다.필드 후offset ★★★★★★★★★★★★★★★★★」count【String】(스트링)의 O(n)의 O(n)의 O(n)의 O(n)의 O(String).

상세한 것에 대하여는, http://java-performance.info/changes-to-string-java-1-7-0_06/ 를 참조해 주세요.

언급URL : https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring