StackOverFlow Error while handling input of size 100000 and more

Question

I am using Collections.sort()in a List of size 100000 and getting StackOverFlow error. How can I scale this up? Here is the code:

This is a part of a big project. Collections.sort() is being called iteratively over the list as follows: The list size decreases at each step and the process iterates until the size of the list becomes 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 ;

}

possible duplicate of [How to increase to Java stack size?](http://stackoverflow.com/questions/3700459/how-to-increase-to-java-stack-size) — Jeffrey, Jan 03 '13 at 20:45
Collections.sort() should have no trouble with a list of 100000 items. Are you sure the problem isn't elsewhere? Can you post a complete example? — Alex, Jan 03 '13 at 21:01
This is a part of a big project. Collections.sort() is being called iteratively over the list as follows: The list size decreases at each step and the process iterates until the size of the list becomes 1.: — Esha Ghosh, Jan 03 '13 at 21:07
@LouisWasserman is right. Take the case where the input list has 3 identical items - none is less than the median, so your left side will be empty and your right side the same as the input list. — Alex, Jan 03 '13 at 21:17

score 3 · Accepted Answer · answered Jan 03 '13 at 21:16

3

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.

answered Jan 03 '13 at 21:16

Louis Wasserman

191,574
25
345
413

A good example of **"select" isn't broken** from http://pragprog.com/the-pragmatic-programmer/extracts/tips – Alex Jan 03 '13 at 21:22
Thanks. This was the problem. – Esha Ghosh Jan 03 '13 at 21:53

score 1 · Answer 2 · answered Jan 03 '13 at 20:51

1

You just have to change the stack size in VM arguments using -Xss option.

answered Jan 03 '13 at 20:51

sacrepit

126
4

Andrew Logvinov · Answer 3 · 2013-01-03T21:14:18.667

1

Collections.sort() according to javadocs uses a modified mergesort (which is a recursive algorithm). On each iteration of this algorithm a recursive call is made which increases stack size.

You have to increase the stack size with -Xss option or redesign your program to make it work.

edited Jan 03 '13 at 21:14

answered Jan 03 '13 at 20:52

Andrew Logvinov

21,181
6
52
54

Even if Collections.sort is implemented recursively, it's going to be O(log(n)) in stack size - not enough to blow the stack on 100000 items. – Alex Jan 03 '13 at 21:04
@Alex Probably you're right. 100K is not such a big collection to cause `SOE`. – Andrew Logvinov Jan 03 '13 at 21:16

score 0 · Answer 4 · answered Jan 03 '13 at 20:54

0

You should increase stack size

java -Xss4m Program

answered Jan 03 '13 at 20:54

Marcin Szymczak

11,199
5
55
63

StackOverFlow Error while handling input of size 100000 and more

4 Answers4