1

我正在使用一个 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 开始而不是 9000 in A）：

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 个元素，这就是我设置为 50000 时发生的i情况A：

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），而且我自己也无法让它工作。其他开发人员如何能够取得这样的成就？

4

3 回答 3

1

Do it iteratively, instead of recursively. (Also, "immutable lists" don't have to be designed the way you're doing it, as a linked list.)

于 2013-07-12T16:39:27.743 回答
0

不要使用递归。使用迭代循环：

class B {
    static List<Integer> incrementList(List<Integer> l) {
        ArrayList<Integer> elements = new ArrayList<Integer>();
        while (l != null) {
            elements.add(l.e + 1);
            l = l.next; 
        }
        List<Integer> result = null;
        for (int i = elements.length - 1; i >= 0; i--) {
            result = new List<Integer>(elements.get(i), result);
        }  
        return result;
    }
}

也就是说，这样的 List 实现，特别是像标准一样命名为 List java.util.List，并不是一个好主意。

于 2013-07-12T16:44:54.073 回答
0

您将递归函数转换为循环（伪代码）：

List increment(List in) {
    List out = new empty list;

    while (in is not empty) {
         out = new out(in.e+1, out);
         in = in.next;
    }
    return need it in same order as before? reverse(out) : out;
}

通常，不需要反转结果列表，因为顺序无关紧要，或者无论如何您还有另一个转换要做。

于 2013-07-12T16:52:33.077 回答