java.lang.OutOfMemoryError:用于查找所有长度为n的字符串的Java堆空间
我想用字母a、b和c生成长度为n的所有可能的字符串。我得到了这个错误java.lang.OutOfMemoryError：Java heap space。我的堆大小是512m。你能给我建议一下替代方案吗？
回答 3
Stack Overflow用户
发布于 2011-12-21 06:09:10
对不含"ABC“子串的字符串进行计数，可以用动态规划的方法解决。
首先，让我们将长度为n的所有字符串的数量命名为S(n)。请注意，S(n)很容易计算。S(n) = pow(size_of_the_alphabet,n)
让我们将包含长度为n的"ABC“的所有字符串的数量命名为A(n)，并将在第k个位置首次出现"ABC”的所有字符串的数量命名为A(n,k)
现在请注意：A(n,k) = (S(k-1) - A(k-1)) * S(n - k - 3) (因为k是"ABC“出现的第一个位置，所以每个字符串都有一个在该位置前面没有"ABC”的子字符串和第一个“ABC”之后的任何子字符串)。
请注意，A(n) = sum A(n,k) for k in [0..n-3]
所以现在我们可以计算A(n)了，从0开始计算A(n)的每个值。
基本情况很简单，如A(n) = 0 for n = 0,1,2
A(3) = (S(0) - A(0))*S(0) = 1 (即"ABC")
等等。
一旦你有了A(n)，你就可以使用公式S(n) - A(n)得到你想要的数字。
伪java伪代码：
public class Counter {
public int count(int aSize, int n) {
long[] a = new long[n+1]; // n + 1 elements since a[i] contains # of strings containing "ABC"
a[0] = 0;
a[1] = 0;
a[2] = 0;
for (int i = 3; i <= n; ++i){
long sum = 0;
for (int k = 0; k <= i-3; ++k) {
sum += (pow(aSize, k) - a[k]) * pow(aSize, i - k - 3);
}
a[i] = sum;
}
return a[n];
}
public static void main(String... args) {
int aSize = 3; //size of the alphabet
int n = 30; // length of the strings
//final result
long result = pow(aSize, n) - count(aSize, n);
}
} 假设幂为O(1)，则运行时间为O(n^2)。如果不是，那么你可以节省一些时间来预计算S(i)。
空间要求为O(n)。
请注意，这将计算长度为== n的所有字符串的数量。如果您希望长度为<= n，那么修改是显而易见的(您只需将a中的所有元素相加)。
Stack Overflow用户
发布于 2011-12-21 02:03:16
您当前正在计算的字符串数为
3^30 = 205 891 132 094 649这是相当多的..。
知道每个字符串包含三个字节：
3^30 * 3 = 617 673 396 283 947加上二维数组的32位或64位指针。
3^30 * (3 + 4) = 1 441 237 924 662 540 // 32-bit Java VM
3^30 * (3 + 8) = 2 264 802 453 041 140 // 64-bit Java VM这就是
2 109 261 GB = 2059 TB // 64-bit JVM我想这就是问题所在。
在您的限制为500MB的情况下，您可以解此方程：
3^x * (3 + 8) = 524 288 000
3^x = 47662545
x = log(47662545) / log(3)
x = 7 / 0.477121254719662
x = 14.67所以，如果我什么都没忘记，你的测试应该可以在n <= 14上工作。当然，在您删除以下代码之前，它不会起作用：
List<String> result = new ArrayList<String>();
for (char[] permutation : table) {
result.add(new String(permutation));
}这段代码复制了所有数据！这意味着您需要两倍的内存量。试着立即打印出来。
Stack Overflow用户
发布于 2011-12-21 03:03:56
我在你的评论中注意到你有一个不同的问题。你想找出所有长度为30，a-z，不包含a-c的字符串。这是所有长度为30的字符串的计数，它们是d-z。计数是(26-3)^30。
System.out.printf("%,d%n", BigInteger.valueOf(26-3).pow(30));打印
71,094,348,791,151,363,024,389,554,286,420,996,798,449您可以将每个可能的字符串编码为数字，而不是记住每个字符串。在您的示例中，您可以使用long。
public static void main(String... args) {
String letters = "abc";
int len = 30;
long combinations = (long) Math.pow(letters.length(), len);
System.out.printf("There are %,d strings%n", combinations);
for (long i = 0; i < 10; i++)
System.out.println(fromLong(i, letters, len));
System.out.println("... some numbers skipped ...");
for (long i = combinations-10; i < combinations; i++)
System.out.println(fromLong(i, letters, len));
}
public static String fromLong(long n, String letters, int len) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(letters.charAt((int) (n % letters.length())));
n /= letters.length();
}
return sb.reverse().toString();
}打印
There are 205,891,132,094,649 strings
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaac
aaaaaaaaaaaaaaaaaaaaaaaaaaaaba
aaaaaaaaaaaaaaaaaaaaaaaaaaaabb
aaaaaaaaaaaaaaaaaaaaaaaaaaaabc
aaaaaaaaaaaaaaaaaaaaaaaaaaaaca
aaaaaaaaaaaaaaaaaaaaaaaaaaaacb
aaaaaaaaaaaaaaaaaaaaaaaaaaaacc
aaaaaaaaaaaaaaaaaaaaaaaaaaabaa
... some numbers skipped ...
cccccccccccccccccccccccccccbcc
ccccccccccccccccccccccccccccaa
ccccccccccccccccccccccccccccab
ccccccccccccccccccccccccccccac
ccccccccccccccccccccccccccccba
ccccccccccccccccccccccccccccbb
ccccccccccccccccccccccccccccbc
ccccccccccccccccccccccccccccca
cccccccccccccccccccccccccccccb
cccccccccccccccccccccccccccccc这可以打印从0到3^30-1的每个可能的字符串。您不需要存储所有编码值，因为您知道所有可能的值都在一个连续的范围内。
https://stackoverflow.com/questions/8579575
复制相似问题
腾讯云开发者
