java - サイズ 100000 以上の入力を処理中に StackOverFlow エラーが発生しました

Question

サイズ 100000 のリストで Collections.sort() を使用していて、StackOverFlow エラーが発生しています。どうすればこれをスケールアップできますか? コードは次のとおりです。

これは大きなプロジェクトの一部です。Collections.sort() は、次のようにリストに対して繰り返し呼び出されます。リストのサイズは各ステップで減少し、リストのサイズが 1 になるまでプロセスが繰り返されます。

public static Node buildTree(int d,  List<kdtrees.DataPoint> list) 
{
   if(list.isEmpty())
   {   
       return null;
   }

   else if(list.size() == 1) // S is singleton, return leaf
   {  
       System.out.println(list.get(list.size() - 1).text);
       Node t = new Node(0,0,null,null,list.get(list.size() - 1));

       return t;
   }

   else
   {           


      Collections.sort(list, compByX);
       double m = findMedian(d, list);


       List<kdtrees.DataPoint> left = new ArrayList<kdtrees.DataPoint>();
       List<kdtrees.DataPoint> right = new ArrayList<kdtrees.DataPoint>();

       for(DataPoint i: list)
       {
           if(i.Xvalue < m) 
           {
             left.add(i);
           }
           else
           {
             right.add(i);
           }


       }


        Node t = new Node(d, m, buildTree((d+1)%3,left)buildTree((d+1)%3,right), null);

        return t ;

}

Answer 1

It looks like the problem isn't in Collections.sort, it's that you're missing a scenario in which the list size doesn't decrease at each step. (Specifically: what happens if all the elements of the list are equal?)

The stack overflow is caused by your code, not Collections.sort.

Answer 2

-Xss オプションを使用して VM 引数のスタック サイズを変更するだけです。

Answer 3

Collections.sort()javadocsの使用によるとa modified mergesort（これは再帰アルゴリズムです）。このアルゴリズムの反復ごとに再帰呼び出しが行われ、スタック サイズが増加します。

オプションでスタックサイズを増やす-Xssか、プログラムを再設計して機能させる必要があります。

Answer 4

スタックサイズを増やす必要があります

java-Xss4mプログラム