Время, затраченное на цикл и рекурсию

Question

Я не спрашиваю, должен ли я использовать рекурсию или итерацию, или что быстрее между ними.Я пытался понять, сколько времени занимает итерация и рекурсия, и я обнаружил интересную закономерность в отношении времени, затрачиваемого обоими, и то, что когда-либо вверху файла занимало больше времени, чем другое.

Например: если я пишу для цикла в начале, это займет больше времени, чем рекурсия и наоборот.Разница между временем, затрачиваемым на оба процесса, существенно огромна примерно от 30 до 40 раз.

Мои вопросы: -

1. Это порядок циклаа рекурсия имеет значение?
2. Есть ли что-то, связанное с печатью?
3. Что может быть причиной такого поведения?

Ниже приведен код, который я имею в том же файле, иЯзык, который я использую, это scala?

  def count(x: Int): Unit = {
    if (x <= 1000) {
      print(s"$x ")
      count(x + 1)
    }
  }

  val t3 = System.currentTimeMillis()
  count(1)
  val t4 = System.currentTimeMillis()
  println(s"\ntime taken by the recursion look = ${t4 - t3} mili second")

  var c = 1

  val t1 = System.currentTimeMillis()
  while(c <= 1000)
    {
      print(s"$c ")
      c+=1
    }
  val t2 = System.currentTimeMillis()

  println(s"\ntime taken by the while loop = ${t2 - t1} mili second")

В этой ситуации время, необходимое для рекурсии и цикла while, составляет 986 мс, 20 мс соответственно.

Когда я переключаю положение цикла и рекурсии, что означаетпервый цикл, затем рекурсия, время, затрачиваемое на рекурсию, и время цикла равны 1,69 с и 28 мс соответственно.

Edit 1: Я могу видеть то же поведение с bufferWriter, если код рекурсии находится наТоп.Но не тот случай, когда рекурсия находится ниже цикла.Когда рекурсия находится ниже цикла, она занимает почти то же время с разницей от 2 до 3 мс.

Answer 1

Если вы хотите убедить себя в том, что tailrec-оптимизация работает, не полагаясь на какие-либо инструменты профилирования, вот что вы можете попробовать:

• Использовать гораздо больше итераций
• Броситьотбросьте первые несколько итераций, чтобы дать JIT время для пробуждения и выполнения оптимизаций горячих точек
• Удалите все непредсказуемые побочные эффекты, такие как печать, на стандартный вывод
• Удалите все дорогостоящие операции, которые являютсято же самое в обоих подходах (форматирование чисел и т. д.)
• Измерение в нескольких раундах
• Рандомизация количества повторений в каждом раунде
• Рандомизация порядка вариантов в каждом раунде, чтобыизбегайте любого «катастрофического резонанса» с циклами сборщика мусора
• Предпочтительно, не запускайте больше ничего на компьютере

Что-то в этом роде:

def compare(
  xs: Array[(String, () => Unit)],
  maxRepsPerBlock: Int = 10000,
  totalRounds: Int = 100000,
  warmupRounds: Int = 1000
): Unit = {
  val n = xs.size
  val times: Array[Long] = Array.ofDim[Long](n)
  val rng = new util.Random
  val indices = (0 until n).toList
  var totalReps: Long = 0

  for (round <- 1 to totalRounds) {
    val order = rng.shuffle(indices)
    val reps = rng.nextInt(maxRepsPerBlock / 2) + maxRepsPerBlock / 2
    for (i <- order) {
      var r = 0
      while (r < reps) {
        r += 1
        val start = System.currentTimeMillis
        (xs(i)._2)()
        val end = System.currentTimeMillis
        if (round > warmupRounds) {
          times(i) += (end - start)
        }
      }
    }
    if (round > warmupRounds) {
      totalReps += reps
    }
  }

  for (i <- 0 until n) {
    println(f"${xs(i)._1}%20s : ${times(i) / totalReps.toDouble}")
  }
}

def gaussSumWhile(n: Int): Long = {
  var acc: Long = 0
  var i = 0
  while (i <= n) {
    acc += i
    i += 1
  }
  acc
}

@annotation.tailrec
def gaussSumRec(n: Int, acc: Long = 0, i: Int = 0): Long = {
  if (i <= n) gaussSumRec(n, acc + i, i + 1)
  else acc 
}

compare(Array(
  ("while", { () => gaussSumWhile(1000) }),
  ("@tailrec", { () => gaussSumRec(1000) })
))

Вот что он печатает:

           while : 6.737733046257334E-5
        @tailrec : 6.70325653896487E-5

Даже приведенных выше простых подсказок достаточно для создания эталона, который показывает, чтоЦикл le и функция хвостовой рекурсии принимают примерно одновременно.

Answer 2

Scala компилируется не в машинный код, а в байт-код для «Виртуальной машины Java» (JVM), которая затем интерпретирует этот код на собственном процессоре.JVM использует несколько механизмов для оптимизации кода, который часто запускается, и в конечном итоге преобразует часто вызываемые функции («горячие точки») в чистый машинный код.

Это означает, что тестирование первого запуска функции не даетхорошая мера возможной производительности.Вам нужно «разогреть» JIT-компилятор, выполнив тестовый код много раз, прежде чем пытаться измерить время, необходимое.

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