Programming

PreviousTuning NextComputer Organization

Last updated 5 years ago

Was this helpful?

Programming

String

String 对象是 Java 语言中最重要的数据类型，往往在内存中占用最大。合理地使用 String，可以提升系统的整体性能。请先了解。

显式使用 StringBuilder

String s1 = "ab" + "cd" + "ef";

// 字节码
// LDC "abcdef"

String s2 = "abc";
for(int i=0; i<1000; i++) {
    s2 = s2 + i;
}

// 反编译
String str = "abc";
for(int i=0; i<1000; i++) {
    str = (new StringBuilder(String.valueOf(str))).append(i).toString();
}

如上面代码，虽然编译器会优化，但是每次循环都创建一个 StringBuilder 对象，会降低性能，所以建议显式使用 StringBuilder 对象。

String.intern()

调用 intern() 方法后，堆内原有的 String 对象就没有引用了，可以被 GC。

String str1= "abc";
String str2= new String("abc");
String str3= str2.intern();
assertSame(str1==str2);
assertSame(str2==str3);
assertSame(str1==str3)

// false false true

要注意过度使用 intern 也会使常量池太大，遍历的时间复杂度增加。所以要根据需求权衡。

String.split

split 使用正则表达式，但正则的性能不稳定，使用不恰当会引起回溯问题，导致 CPU 居高不下。

若 indexOf 方法能够满足需求，尽量使用它。

split 有两种情况不会使用正则：

传入参数长度为 1，且不包含 .$|()[{^?*+\\；
传入参数长度为 2，第一个字符是 \，且第二个字符不是 ASCII 数字或字母。

正则表达式

正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的字符串，很多语言都实现了它。

普通字符：字母[a-zA-Z]、数字[0-9]、下划线[_]、标点等
标准字符：能够与多种普通字符匹配的简单表达式，如 \d（数字）、\w（包括下划线的单词字符）、\s（空白字符）等。
限定字符：用于表示数量，*、+、?、{n} 等。
定位字符：符合某种条件的位置，$、^ 等。

引擎

给定正则表达式后，程序对表达式语法分析，建立语法分析数，再根据这个分析树结合正则表达式引擎生成执行程序（又称状态机、状态自动机），用于匹配字符。

正则表达式引擎有两种：

DFA 自动机：Deterministic Final Automata，确定有限状态自动机，匹配时间复杂度 O(n)
NFA 自动机：Non deterministic Final Automaton，非确定有限状态自动机，匹配时间复杂度 O(ns)，s 为状态数；优点是支持功能更多，如捕获 group、环视、占有有限量词等，所以编程语言里面一般用 NFA 实现。

回溯问题

假设字符串为 ”abbc“，正则表达式为 "ab{1,3}c"，则匹配过程如下图：

NFA 自动机默认情况时贪婪模式，即匹配尽量多的内容，在第 2 步匹配到一个 b 后，会继续尽量匹配到 3 个 b。所以第 4 步，想要匹配第三个 b 时匹配不到，就会发送回溯，已经读取到 c 会被回退，指针重新指向第三个字符 b，然后再匹配 c。

贪婪模式（Greedy）

如果单独使用 +、?、*、{min,max}，则会尽量匹配多的内容。

懒惰模式（Reluctant）

NFA 会尽量匹配少的内容。通过增加 ? 开启。

独占模式（Possessive）

与贪婪模式一致，会尽量匹配多的内容，但是若匹配失败，不会回溯，直接匹配结束。通过增加 + 开启。

案例

public static void main(String[] args) {
    String text = "abbbc";
    String reg1 = "ab{1,3}bbc";
    String reg2 = "ab{1,3}?bbc";
    String reg3 = "ab{1,3}+bbc";
    System.out.println(String.format("文本: \"%s\"", text));
    System.out.println(String.format("贪婪模式: \"%s\"", reg1));
    System.out.println(String.format("懒惰模式: \"%s\"", reg2));
    System.out.println(String.format("独占模式: \"%s\"\n", reg3));
    print(text, reg1, reg2);
    Pattern p = Pattern.compile(reg3);
    Matcher matcher = p.matcher(text);
    System.out.println(String.format("\n独占模式匹配结果：%b", matcher.find()));
}

private static void print(String text, String regex1, String regex2) {
    System.out.println("regex1     regex2   percentage");
    Pattern p1 = Pattern.compile(regex1);
    Pattern p2 = Pattern.compile(regex2);
    for (int i = 0; i < 10; i++) {
        long t1 = cost(text, p1);
        long t2 = cost(text, p2);
        if (i >= 1) {
            System.out.println(String.format("%4d%10d%10.2f", t1, t2, t2 * 1.0 / t1));
        }
    }
}

private static long cost(String text, Pattern p) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        Matcher matcher = p.matcher(text);
        boolean b = matcher.find();
    }
    return System.currentTimeMillis() - start;
}

输出结果：

文本: "abbbc"
贪婪模式: "ab{1,3}bbc"
懒惰模式: "ab{1,3}?bbc"
独占模式: "ab{1,3}+bbc"

regex1     regex2   percentage
 873       561      0.64
 851       587      0.69
 876       624      0.71
 850       619      0.73
 857       615      0.72
 863       623      0.72
 865       624      0.72
 858       608      0.71
 853       611      0.72

独占模式匹配结果：false

优化

少用贪婪模式，多用独占模式

减少分支选择

"(x|y|z)" 会降低性能，可以做如下优化：

常用的放在前面，就可以较快被匹配到。
"(abcs|abef)" 改成 "ab(cd|ef)"。
"(x|y|z)" 可以改成调用三次 String.indexOf() 方法。

减少捕获组

正则表达式中，子表达式匹配的内容保存到以数组编号或显示命名的数组中，方便后面引用，叫做捕获组，一般 () 表示一个捕获组，捕获组可以嵌套。

可以用 (?:exp) 来表示不用捕获组。

减少捕获组可以提高性能。

List

初始化，ArrayList 最好指定容量，避免扩容复制。
新增元素，不考虑扩容时：
- 头部增加： LinkedList 效率较高，因为 ArrayList 需要移动大部分数据。
- 中间增加：差不多，因为 ArrayList 需要移动大约一半数据，LinkedList 找到中间位置需要遍历大约一半的数据。
- 尾部增加：ArrayList 效率较高，因为 LinkedList 的指针变换比较耗时。
删除元素：
- 头部删除：LinkedList 效率较高。
- 中间删除：差不多。
- 尾部删除：ArrayList 效率较高。
遍历元素：
- for(;;) 遍历：ArrayList 效率高，因为 LinkedList 每次都要找到位置。
- 迭代器遍历：差不多。