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

Автор izbyshev, 15 лет назад, По-русски
На контестах довольно часто встречаются задачи, требующие применения глубокой рекурсии. Обычно это задачи на графы с большими ограничениями, решение которых использует поиск в глубину. А глубокая рекурсия требует большого размера доступного стека, часто несколько мегабайт.
В таких языках программирования, как C++ или Pascal/Delphi, размер стека можно установить с помощью директив компилятору. Однако в Java это сделать нельзя. Размер стека, выделяемый потоку Java по умолчанию, весьма мал, на 32-битной Windows всего 320kb. Самым простым способом установить размер стека для потока Java является использование ключа командой строки -Xss для JVM. Вот тут-то и начинаются проблемы.
Во-первых, об этом нужно знать) Практика показывает, что плохое представление о Java имеют не только низкоуровневые соревнования (Западно-Сибирский четвертьфинал ACM ICPC), но и вполне приличные архивы задач, например, TJU. В результате приходится писать либо нерекурсивный dfs, что не всегда тривиально и всегда лениво, либо писать/переписывать на C++, что просто печально.
Во-вторых, недостатки имеет сам ключ -Xss. При его использовании указанный размер стека выделяется всем потоками приложения. Для простого однопоточного приложения это не страшно, однако это может создать проблемы для тестирующей системы, если в ней одновременно могут выполняться много потоков Java.
Кроме того, возникает вопрос неучтенной памяти - если тестирующая выставляет ограничение по памяти с помощью ключа -Xmx, то программа, вообще говоря, может использовать больше памяти - добавляется стек. Поэтому контроль проверки на Memory Limit Exceeded с помощью перехватывания OutOfMemoryError будет работать не совсем корректно.
Стоит, однако, сказать, что эти недостатки вполне себе преспокойно игнорируются. Стандартная командная строка запуска jvm вида
  java -Xmx<?>М -Xss<?>M <class name>
используется на NEERC, что указано в раздаваемых перед контестом правилах (хотя об этом почему-то ничего нет на официальном сайте), на Timus и на петрозаводских сборах. Есть также подозрения, что что-то подобное используется на финале ACM ICPC, хотя опять же, только по словам на Q&A Session.
В-третьих, до Java 1.6 эта установка использовалась только во вновь созданных потоках, в то время как main thread использовал стандартный для ОС размер стека. Поэтому  приходилось писать в main-методе что-то вроде
        new Thread() {
            public void run() {
              new Main().run();
            }
        }.start();
С появлением 1.6 это стало не нужно, и я уже начал забывать о всех беспокойствах, связанных со стеком. Но тут появился Codeforces.
Не увидев в описании компиляторов нужных параметров, я поспешил написать коммент. Какого же было моё удивление, когда MikeMirzayanov ответил, что "Правильно запускать новый Thread с нужным размером стека и в нем осуществлять решение задачи". Я всю жизнь думал, что этого сделать нельзя) Но, посмотрев JavaDoc (почему я не сделал этого раньше?), я нашел такой вот замечательный конструктор у Thread:
public Thread(ThreadGroup group,
              Runnable target,
              String name,
              long stackSize).
Правда, в том же JavaDoc несколько раз было написано о том, что как будет использоваться параметр stackSize и будет ли использоваться вообще, зависит от системы. Тем не менее, проверка показала, что стек действительно выставляется, и не только на Codeforces, но и на TJU. В результате приходим к такому прекрасному оператору в main:
        new Thread(null, new Runnable() {
            public void run() {
                new Main().run();
            }
        }, "1", 1 << 23).start();
который устанавливает размер стека в 8 МБ для потока "1".
Может быть, у вас возникали какие-то еще проблемы со стеком или вы знаете другие способы его установить? Пишите в комментах)
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Помниться на одном контесте приходилось переписывать dfs на нерекурсивный, причем на С++, так как на сервера соревнований стоял какой-то кривой visual studio, который не умел менять размер стека.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Помнится, еще в школе приходилось заниматься нерекурсивными dfs-ами на тимусе, из-за того что не знал, как там установить размер стека. Но это все хорошо, пока у тебя нет кучи локальных переменных. Заводить для каждой из них стек и поддерживать его не сильно приятно.
    • 15 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится
      dfs можно запустить как bfs, только вместо очереди использовать dfs
      • 15 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        * Только вместо очереди использовать стек.

        Хочу посмотреть как ты сделаешь это легко для, допустим, поиска мостов или топологической сортировки.
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          В смысле, а в чем проблема? В стеке будет храниться три типа состояний: находимся в начале функции, находимся в середине функции, находимся в конце функции. Для большинства алгоритмов на графах этого более, чем достаточно.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В java даже есть выбор, хочешь ставь в строке компиляции размер стека по умолчанию, хочешь прямо в коде задавай. Я когда-то писал систему проверки для наших локальных олимпиад в Архангельске, и встала проблема как установить размер стека в VB.net и C#. Оказалось, что никаких ключей компилятора  на эту тему нет. В коде тоже ничего не поделаешь. Как быть? Насколько мне известно, и тут на CF и например на Тимусе у пользователей C# всего 1 мб стека, не разгуляешься... Но выход есть! :) В комплекте с Visual Studio идет утилита editbin, которая способна брать готовый exe файл и проставлять там произвольный размер стека, что замечательно работает и для C# и для VB.net. В принципе никаких чудес тут нет, дефолтный размер стека - это одно из полей заголовка PE, но почему-то про эту возможность иногда забывают.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот уж действительно странно, неужели ни у кого не возникает необходимости изменять размер стека на C#? Может же понадобиться не только увеличить, но и уменьшить его, если надо очень много потоков. Интересно, что Petr делает в таких случах? Пишет на Java?)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Выходит, что плохое представление о Java имеют не только низкоуровневые соревнования, но и участники, много лет пишущие на Java.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    О языке и его возможностях всегда можно узнать что-то новое, даже если писать на нем полжизни. К тому же, эти участники, в отличие от низкоуровневых соревнований, идут вперед, а не наступают каждый год на одни и те же грабли, делая серьезную мину.
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Дело в том, что Java -- это не просто язык программирования, а движение, которое верит, что нашло панацею от всего.

      Оно считает, что проблемы, возникающие при работе с другими языками, имеют причиной эти самые языки, а проблемы при работе на их любимом языке происходят по причине кого-то еще: пользователей программы, разработчиков ОС, на которой эта программа работает, жюри олимпиад и т.д.


15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Штука в том, что конструктор java.lang.Thread с размером стека работает не на всех операционных системах одинаково. В javadoc

Перед каким-то из полуфиналов я проверял все это под виндой, и там параметр глубины стека игнорировался. Когда мы на финале - а там линукс - не были уверены в том, дадут ли нам стек с помощью ключей, мы попробовали использовать этот конструктор, и там он заработал. Может быть, сейчас и с виндой изменилась ситуация, я не слежу.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А я сколько себя помню - под Windows это работало. Разумеется, jvm была от Sun.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Аккорд на клавиатуре оказался фальшивым. Конец первого абзаца: "В javadoc написано, что параметр величины стека может, в принципе, игнорироваться".
»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Dude thanks a lot . I used this in getting AC in a problem involving Kosaraju's algorithm

»
9 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Codeforces doesn't create a lot of threads. So why do you need to reduce stack size?

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

Actually this is really useful if you need to do dfs . Without increasing the stack size I wouldn't have got AC in this problem https://www.hackerearth.com/problem/algorithm/a-walk-to-remember-qualifier2/

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

Will you please provide a example program using Runnable interface. It will be a great help.

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

    This is how I do every problem that involves deep recursion.

    public class Example implements Runnable {
         public static void main(String[] args) {
             new Thread(null, new Example(), "whatever", 1<<26).start();
         }
    
         public void run() {
            // Do whatever you want in this function instead of main
         }
    }