java 堆栈溢出错误递归

Question

我正在制作一种方法，它使用一个参数告诉移动多少次来左右移动数组中的字符。它必须在 20 毫秒内完成，所以我尝试了递归。

//数组中切换位置的方法

public static void bytt(char[] c, int i, int j){
    char temp = c[i];
    c[i] = c[j];
    c[j] = temp;
}

//这个方法左移

public static char rotasjon1(char[] a, int i){
    if(i > 0){
        bytt(a,i,i-1);
        return rotasjon1(a,i-1);
    }
    else
        return ' ';
}

//此方法右移

public static char reverseRotasjon(char[] a, int i){
    if(i < a.length-1){
        bytt(a,i,i+1);
        return reverseRotasjon(a,i+1);
    }
    else
        return ' ';
}

//该方法根据参数决定使用右移还是左移

public static void rotasjon(final char[] a, int k){
    if(a.length == 1 || a.length == 0){
        return;
    }
    if(k >= 0){
        for(int i = 0; i< k; i++){
            char temp = a[a.length-1];
            rotasjon1(a,a.length-1);
            a[0] = temp;
        }
    }

    if(k < 0){
        for(int i = k; i< 0; i++) {
            char temp = a[0];
            reverseRotasjon(a, 0);
            a[a.length - 1] = temp;
        }
    }
}

//所有这些都适用于这个数组

char[] d = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
    char[] d0 = {'G', 'H', 'I', 'J', 'A', 'B', 'C', 'D', 'E', 'F'};

    Oblig1.rotasjon(d, 4);

d = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
    Oblig1.rotasjon(d, -6);

//但是我用这个数组得到了java.lang.WhosebugError

char[] x = new char[100_000];
    Oblig1.rotasjon(x, 99_999);

我知道数组很大，但是否可以解决这个问题，还是我必须回到传统的 for 循环？它必须在 20 毫秒内执行

Answer 1

Java 不支持尾调用优化，因此您需要不同的算法或 for 循环。

Answer 2

您想要做的是使用大小为 100 000 到 1 的输入数组调用该函数 100 000 次。您尝试放入内存的最大大小为 (100 000 + 1) * (100 000 / 2) * 8（所有字符的大小）+ 100 000 * 8（数组引用的大小）+ 100 000 * 24（保持数组结构所需的内存）位。这是 5 000 450 000 字节或 ~5GB，因此是 WhosebugError。您仍然可以通过调整 JVM 来实现它运行，但通常对大型数据结构使用深度递归是一个非常糟糕的主意。

Answer 3

I know the array is big an stuff, but is it possible to fix this or do i have to go back to traditional for loops ?

出现异常是因为递归太深；即它需要太多的嵌套调用。

现在在许多语言中这都无关紧要。例如，使用典型的函数式语言，您可以根据需要深入递归。但有效的原因是函数式语言（和许多其他语言）实现了一种称为尾调用优化的东西，其中方法调用末尾的递归调用被（由编译器）优化为跳转到方法调用的开头方法。

参考：What Is Tail Call Optimization?

但是Java不支持尾调用优化。（这有合理但复杂的原因。）相反，每次调用都会在当前线程的堆栈上获得一个堆栈帧；即 N 深度递归需要 N 个堆栈帧。问题是 Java 线程具有固定数量的堆栈 space。（默认值通常为 1M 字节或更少。）一旦创建，线程的堆栈就无法扩展。如果算法递归太深，线程将用完堆栈 space，并且 JVM 会引发异常……如您所见。

那么答案是什么？

一般来说，避免在 Java 中实现可能深度递归的算法：
- 如果算法是递归的，尝试将其转换为等价的迭代；例如手动进行尾调用优化。
- 如果算法是迭代的，就这样吧！
如果确实需要深度递归，可以将线程的最大堆栈大小指定为构造函数参数。（我不确定是否有架构限制，但你肯定会受到可用内存量的限制......）

if so, mabye you have some advice ? Remember it have to execute within 20 milliseconds.

如果您的主要目标是有效地实现它，请不要使用递归而不是迭代。在 Java - 它不会更快，并且始终存在堆栈溢出的潜在风险。
在这种情况下，请查看使用临时数组和System.arraycopy。（如果按 1 旋转，则不需要临时数组。您可以每次按 1 的步长旋转 N，但效率很低。）
在这种情况下，看看如何实现它，就像您手动重新排列扑克牌一样……只用两只手（临时变量）。这在不使用 O(N) 额外存储的情况下解决了 "rotate by N" 问题。

Answer 4

按照 Paul Boddington 的建议，使用 System.arraycopy 进行超快速旋转：

private static void rotate(char[] array, int distance) {
    if (array == null || array.length == 0)
        return; // nothing to rotate
    final int len = array.length;
    int d = distance % len; // eliminate distance overflow, e.g. for len=10, shift +28 is same as +8
    if (d == 0)
        return; // not rotating
    if (d < 0)
        d += len; // convert left shift to right shift, e.g. for len=10, -2 is same as +8
    if (d < len / 2) { // right shift less than half the array
        char[] temp = new char[d];
        System.arraycopy(array, len - d, temp, 0, d);  // save d values at end
        System.arraycopy(array, 0, array, d, len - d); // shift right by d
        System.arraycopy(temp, 0, array, 0, d);        // add saved value at start
    } else { // right shift more than half the array, so better to use left shift for smaller temp space
        d = len - d; // e.g. for len=10, right by 8 is left by 2
        char[] temp = new char[d];
        System.arraycopy(array, 0, temp, 0, d);        // save d values at start
        System.arraycopy(array, d, array, 0, len - d); // shift left by d
        System.arraycopy(temp, 0, array, len - d, d);  // add saved value at end
    }
}

测试

String s = "ABCDEFGHIJ";
for (int i = -11; i <= 11; i++) {
    char[] array = s.toCharArray();
    long start = System.nanoTime();
    rotate(array, i);
    long end = System.nanoTime();
    System.out.printf("%3d: %s   (%dns)%n", i, new String(array), end-start);
}

char[] x = new char[100_000];
for (int d : new int[] { 0, 1, 50_000, 99_999 }) {
    long start = System.nanoTime();
    rotate(x, d);
    long end = System.nanoTime();
    System.out.printf("%5d: %6dns = %fms%n", d, end-start, (end-start) / 1_000_000d);
}

输出

-11: BCDEFGHIJA   (7128ns)
-10: ABCDEFGHIJ   (285ns)
 -9: JABCDEFGHI   (856ns)
 -8: IJABCDEFGH   (855ns)
 -7: HIJABCDEFG   (855ns)
 -6: GHIJABCDEF   (855ns)
 -5: FGHIJABCDE   (855ns)
 -4: EFGHIJABCD   (855ns)
 -3: DEFGHIJABC   (856ns)
 -2: CDEFGHIJAB   (855ns)
 -1: BCDEFGHIJA   (855ns)
  0: ABCDEFGHIJ   (286ns)
  1: JABCDEFGHI   (855ns)
  2: IJABCDEFGH   (856ns)
  3: HIJABCDEFG   (1710ns)
  4: GHIJABCDEF   (856ns)
  5: FGHIJABCDE   (1141ns)
  6: EFGHIJABCD   (855ns)
  7: DEFGHIJABC   (856ns)
  8: CDEFGHIJAB   (855ns)
  9: BCDEFGHIJA   (571ns)
 10: ABCDEFGHIJ   (285ns)
 11: JABCDEFGHI   (855ns)

    0:    285ns = 0.000285ms
    1:  55885ns = 0.055885ms
50000:  43339ns = 0.043339ms
99999:  56169ns = 0.056169ms

java 堆栈溢出错误递归

java stack overflow error recursion

java

stack-overflow

arrays

sorting

recursion