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

Всем привет Язык JAVA
Автор KRISTALL, 11 лет назад, По-русски

Всем привет. Писать на java недавно начал. Так вот дело в том что есть задача на рекурсию условие можно пасареть по этой ссылке я вроде сделал ее, но проходит из 10 тестов 9 тестов. 1 тест пишет Превышено максимальное время работы вот код http://paste.ideaslabs.com/show/Q6lWOyFdXZ

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

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

Писать на java недавно начал.

Уважаемый Йода, Вам скорее всего стоит отказаться от множественного x[i] + " ".

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

    Почему?

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

      Каждый раз при этом создается новый экземпляр String. И потом вас радует garbage collector.

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

        Можно на более понятном языке, я же только начинающий...

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

          Особенности Java. Каждый раз при выполнении x[i] + " " создается новая строка, сохранаяется в памяти и затем подается методу println. Эти строки постепенно накапливаются в памяти и тут в дело вступает garbage collector (сборщик мусора).

          На практике получается примерно так: выводится примерно 10^6 чисел, для каждого из них у вас создается новая строка и в итоге у вас 2 мегабайта занято. Через какое-то время, когда памяти станет не хватать, запустится сборщик мусора и удалит ненужные экземпляры, а на это затрачивается время.

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

            И как быть?

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              11 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

              Варианты:

              1. Два вызова print() — один с числом, другой — с пробелом.

              2. Переписать под один длинный StringBuilder. Т.е. по ходу выполнения программы вы не выводите всё сразу на консоль, а сначала складываете в StringBuilder. Этот StringBuilder имеет смысл создать с запасом по памяти изначально. В конце делаете ему ToString() и результат отправляете на консоль.

              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                11 лет назад, # ^ |
                ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                1. Кстати, пробовал заслать с двумя вызовами print — не заходит. Маловероятно это причина, но судя по документации println делает за собой flush. Нет, с print('\n') то же самое. Странно. Разве у PrintWriter'а нету буферизации?

                2. А вот через StringBuffer заходит

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

                  По умолчанию включен автоматический сброс, который реализован вот так:

                  if (autoFlush && (s.indexOf('\n') >= 0))
    out.flush();
                  → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

        Какой тут GC, если программа жрёт меньше 1 мб. Да и создание объектов тут совсем в смешных масштабах. Но в целом проблема с излишним выделеним объектом вполне встречается (несмотря на то, что компилятор может заменить конкатенацию на работу с StringBuilder/StringBuffer). В данном случае педалей добавляет периодический сброс буфера System.out в консоль( или на диск). Если весь вывод хранить в StringBuilder и сбросить его весь целиком в конце, то получите ускорение раз в 8-10 на вашей задаче.

        → Ответить