Блог пользователя javanetbeans

Автор javanetbeans, 12 лет назад, По-английски

Today I was going through SRM-556 DIV-2 500 question.

I tried to implement the solution in Java. It didn't work. Then implemented in C++. It worked. In Java I got stackoverflow error. While in C++, it ran perfectly.

Please refer this post

For the last test cases, the number of recursive calls made is 25600. Doesn't Java have enough space to accomodate this much instances (copies) of program.

Please help me why I am getting such strange behavior in Java????

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

There is no "stack size in C++" or "stack size in Java" — these values could be configured at compilation / runtime (though at TopCoder you, perhaps, could not control it).

You wrote:

Stack size for last test cases is roughly 25600. Is it that Java's available stack size is less than this?

But stack size is not measured in stack frames. Stack size is defined in bytes (and sometimes you can change this setting, for example from command line) — and it depends on your implementation how much each stack frame takes. For example you could try and make the method static, or use arguments of smaller size (shorts, for example). However, I do not believe such monkeying is a good approach.

I think when you see that recursion could be too deep, you need to use external stack (and iteration) or something like it. It would never do to write programs which are at the edge of failing by design.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Try this

new Thread(null, new Runnable() {
            public void run() {
                new Main().run();
            }
        }, "1", 1 << 23).start();

Executes .run() method with 8Mb stacksize. (Last parametr == (1 << 23) )

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    In your case:

    new Thread (null, new Runnable() {
    	public void run() {
    		dfs(0, ans);				
    	}
    }, "1", 1 << 23);
    
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Since this is competitive problem, I am not allowed to use threads.... :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It is not cheating, it is quite old recipe found in old submission of Petr Mitrichev, for example. The idea is that newly created threads could use larger stack. However I do not remember whether it makes sense for nowadays versions of java.

        Read the post thoroughly and perform some experiments if you want.