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 を超えると、次のようになります(の 9000 ではなく 10000 から開始するようにStackOverflowError変更します)。iA

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

再帰的にではなく、繰り返し実行してください。(また、「不変リスト」は、リンクされたリストとして、あなたがやっているように設計する必要はありません。)

于 2013-07-12T16:39:27.743 に答える
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 に答える