java - 如何在堆栈有限的情况下实际使用 Java 中的不可变列表？

Question

我正在使用一个 API，它为我提供了大型不可变列表，如下所示:

class List<T> {
    final T e;
    final List<T> next;
    public List(T e, List<T> next) {
        this.e = e;
        this.next = next;
    }
}

我想创建列表的副本，其中某些元素以某种方式发生了更改。事实证明，事情并不像我最初想象的那么简单。此测试代码创建一个从 0 到 9000 的整数列表。这是为了模拟我将从 API 返回的数据类型:

class A {
    static {
        List<Integer> l = null;
        for (int i = 9000; i >= 0; i--) l = new List<Integer>(i,l);
        List<Integer> l2 = B.incrementList(l);
        System.out.println(l.e           + " -> " + l2.e);
        System.out.println(l.next.e      + " -> " + l2.next.e);
        System.out.println(l.next.next.e + " -> " + l2.next.next.e);
    }
}

我使用递归递增每个项目，因为没有其他方法:

class B {
    static List<Integer> incrementList(List<Integer> l) {
        return l == null ? null : 
            new List<Integer>(l.e+1, incrementList(l.next));
    }
}

这工作正常:

0 -> 1
1 -> 2
2 -> 3
Exception in thread "main" java.lang.NoSuchMethodError: main

但是一旦我有超过 9000 个元素，我就会得到 StackOverflowError (将 i 更改为从 10000 开始，而不是 A 中的 9000):

javac A.java && java A
Exception in thread "main" java.lang.StackOverflowError
    at B.incrementList(A.java:33)
    at B.incrementList(A.java:33)
    at B.incrementList(A.java:33)
    [...]
    at B.incrementList(A.java:33)
    at B.incrementList(A.java:33)
    at B.incrementList(A.java:33)
Could not find the main class: A. Program will exit.

因此我更改了 B 以使用不同的策略来增加列表元素:

class B {
    static List<Integer> incrementList(List<Integer> l) {
        return ListIncrementer.call(l);
    }
}

class ListIncrementer extends Thread {
    List<Integer> l;
    List<Integer> result;
    ListIncrementer(List<Integer> l) {
        this.l = l;
    }
    public void run() {
        if (l == null) {
            result = null;
            return;
        }
        result = new List<Integer>(l.e+1,call(l.next));
    }
    static List<Integer> call(List<Integer> l) {
        ListIncrementer li = new ListIncrementer(l);
        li.start();
        try { li.join(); } catch (Exception _) {}
        return li.result;
    }
}

它不使用堆栈，而是创建一个新线程来计算每个下一个元素。这可以避免出现任何StackOverflowError:

javac A.java && java A
0 -> 1
1 -> 2
2 -> 3
Exception in thread "main" java.lang.NoSuchMethodError: main

它有效，正如预期的那样。

但是，使用此方法我仍然只能处理大约 30000 个元素，这就是当我将 A 中的 i 设置为 50000 时发生的情况:

Exception in thread "Thread-32290" java.lang.OutOfMemoryError: unable to create new native thread
    at java.lang.Thread.start0(Native Method)
    at java.lang.Thread.start(Thread.java:657)
    at ListIncrementer.call(A.java:25)
    at ListIncrementer.run(A.java:21)
0 -> 1
1 -> 2
2 -> 3
Exception in thread "main" java.lang.NoSuchMethodError: main

(请注意，列表的开头已成功创建，但在末尾的某个地方它会中断并以 null 结束)

这意味着它仍然不如用于构建列表的简单迭代。这让我想到也许操纵大型不可变列表是不可能的。我经常听到 Java 开发人员说最佳实践是使用不可变结构，但是，我找不到任何可以执行此操作的库(除了我提到的 API)，而且我无法让它自己工作。其他开发人员是如何取得如此成就的？

Answer 1

迭代地执行，而不是递归地执行。 (此外，“不可变列表”不必按照您的方式设计，如链接列表。)