logo标签列表

Java的substring()方法的时间复杂度是多少？

javasubstringtime-complexity
120
< p > String#substring() 方法在 Java 中的时间复杂度是多少？< /p >
7个回答
176

新答案

从 Java 7 的第 6 次更新开始，substring的行为更改为创建一个副本 - 所以每个String都引用一个char[]，该数组与任何其他对象都不共享，据我所知。因此，从那时起，substring()成为一个O(n)操作，其中n是子字符串中的字符数。

旧答案：Java 7之前

未记录 - 但在实践中如果您假设不需要垃圾回收等，则为O(1)。

它仅构建一个新的String对象，该对象引用相同的底层char[]，但具有不同的偏移量和计数值。因此，成本是执行验证和构造单个新（相对较小）对象所需的时间。就这方面而言，它并不直接取决于原始字符串或子字符串的长度。在讨论可能基于垃圾回收、CPU缓存等时间变化的操作复杂性时，这是O(1)。

16
“undocumented” 加一分，这是 API 的一个不幸弱点。 - Raedwald
11
这并不是软弱。如果记录了行为，但未记录实现细节，则可以在将来更快地进行实现。一般来说，Java通常定义行为并让实现决定最佳方式。换句话说，你不应该在乎，毕竟这是Java；-) - peenut
2
好观点，尽管我几乎不相信他们将能够使这个比O(1)更快。 - abahgat
12
不，这种情况应该有记录。开发者应该知道，以防他计划从一个大字符串中取一个小子串，并期望像在.NET中一样将大字符串进行垃圾回收。 - Qwertie
1
值得注意的是，尽管性能较差，这个改变是为了解决垃圾回收泄漏问题。 - Krease
显示剩余4条评论
41

在早期版本的Java中，它是O(1) - 正如Jon所述，它只是创建一个具有相同底层char[]、不同偏移量和长度的新String。

但是，这个情况实际上从Java 7更新6开始发生了改变。

char[]共享被消除，偏移量和长度字段被删除。substring()现在只是将所有字符复制到一个新的String中。

因此，在Java 7更新6中，substring的时间复杂度为O(n)。

2
+1 这确实是最近Sun Java和OpenJDK版本中的情况。GNU Classpath（和其他一些，我想）仍在使用旧范例。不幸的是，关于这一点似乎存在一些智力惯性。我仍然看到2013年的帖子，推荐基于子字符串使用共享char[]的假设的各种方法... - thkala
14
新版本不再具有O(1)复杂度。想知道是否有其他替代方法能够在O(1)时间内实现子字符串操作？String.substring是一个非常有用的方法。 - Yitong Zhou
13

现在它具有线性复杂度。这是修复了 substring 的内存泄漏问题之后的结果。

因此，从 Java 1.7.0_06 开始，请记住 String.substring 现在具有线性复杂度而不是常数复杂度。

现在（对于长字符串）情况更糟了吗？ - Peter Mortensen
@PeterMortensen 是的。 - Ido Kessler
9

为Jon的回答提供证明。

我有同样的疑问，想检查字符串长度是否会影响子字符串函数。编写了以下代码来确定子字符串实际上取决于哪个参数。

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

证明子字符串函数取决于请求的子字符串长度而不是字符串的长度。
2
我不想成为扫兴的人，但这不是“证明”，而只是一个指示。 - akiva
2

O(1)是因为不需要复制原始字符串，它只是创建一个具有不同偏移信息的新包装对象。

1
请自行判断，但Java的性能缺陷不在于字符串的子串。代码：
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)取决于情况。如果您只是在内存中引用同一字符串，那么想象一下一个非常长的字符串，您制作了子字符串并停止引用长字符串。释放长字符串的内存不是很好吗？

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接