生成排列的更快方法

Question

我正在编写一个程序，该程序计算两个字符串（a和B）之间的命中率。为了获得准确的百分比，我将N-Grams与字符串a的排列列表进行匹配。

这是我的代码

public String[] generatePermutations( String name ){
    String[] perms = new String[ calcN(name.length()) ];
    int nameLen = name.length(),
                cnt = 0;

    for(int i = 0; i < name.length(); i++ ){
        nameLen = name.length()-i;
        for( int ii = 0; ii <= i; ii++){
            perms[cnt++] = name.substring( ii, ii + nameLen );
        }
    }
    return perms;
}

供参考calcN（）低于

public int calcN( int n ){
    return ( n * (n+1 )) / 2;
}

给定字符串"ABC"，此方法将生成

{"A"、"B"、"C"、"AB"、"BC"、"ABC"}

既然我已经做了数千次（也许数十万次）这个操作，有什么办法可以从我的CPU中挤出一些额外的周期吗？（除了切换到C++或C之外）。一如既往，提前感谢您的建议！

Answer 1

该方法的性能优化在一定程度上取决于所使用的JVM。例如，在OpenJDK中，子字符串实现为：

public String substring(int beginIndex, int endIndex) {
    if (beginIndex < 0) {
        throw new StringIndexOutOfBoundsException(beginIndex);
    }
    if (endIndex > count) {
        throw new StringIndexOutOfBoundsException(endIndex);
    }
    if (beginIndex > endIndex) {
        throw new StringIndexOutOfBoundsException(endIndex - beginIndex);
    }
    return ((beginIndex == 0) && (endIndex == count)) ? this :
        new String(offset + beginIndex, endIndex - beginIndex, value);
}

该字符串构造函数是一个受保护的表单，实现为：

 // Package private constructor which shares value array for speed.
String(int offset, int count, char value[]) {
     this.value = value;
     this.offset = offset;
     this.count = count;
 }

请注意，这不需要创建新的值（支持String的char[]）。

另一方面，正如《Java 7性能调整指南》中所述，由于内存泄漏，它被删除了（1000个字符长的字符串中的单字符子字符串被垃圾收集后仍保留支持它的1000个字符字符串）。

因此，选择使用哪种jvm可能会对从子字符串创建字符串产生重大影响。

根据您的应用程序以及性能的关键程度，您可能会考虑实现自己的String有限版本，该版本可以重新实现子字符串的偏移量和长度实现。

Answer 2

我知道，我可能不会帮忙，但我无法抗拒。

Scala一行：

(1 to 3).flatMap("ABC".combinations(_))

返回

Vector(A, B, C, AB, AC, BC, ABC)

和

"ABC".permutations.toList

返回

List(ABC, ACB, BAC, BCA, CAB, CBA)

在JVM之上使用Scala非常容易。

Answer 3

这不会有多大帮助，但我看不到使用cnt，它只是使用ii