Почему хвостовая рекурсия не приводит к лучшей производительности в этом коде? - PullRequest
Новая
       8

Почему хвостовая рекурсия не приводит к лучшей производительности в этом коде?

7 голосов
/ 29 июля 2011

Я создавал более быстрый метод разделения строк.Сначала я написал нехвостую рекурсивную версию, возвращающую List.Затем, хвостовой рекурсивный с использованием ListBuffer и последующим вызовом toList (+= и toList - O (1)).Я полностью ожидал, что хвостовая рекурсивная версия будет быстрее, но это не так.

Кто-нибудь может объяснить почему?

Оригинальная версия: 

def split(s: String, c: Char, i: Int = 0): List[String] = if (i < 0) Nil else {
  val p = s indexOf (c, i)
  if (p < 0) s.substring(i) :: Nil else s.substring(i, p) :: split(s, c, p + 1)
}

Хвостовая рекурсивная версия: 

import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer
def split(s: String, c: Char): Seq[String] = {
  val buffer = ListBuffer.empty[String]
  @tailrec def recurse(i: Int): Seq[String] =  {
    val p = s indexOf (c, i)
    if (p < 0) {
      buffer += s.substring(i)
      buffer.toList
    } else {
      buffer += s.substring(i, p)
      recurse(p + 1)
    }
  }
  recurse(0)
}

Это было сравнено с кодом здесь , с результатами здесь , по # jyxent # scala.

Ответы [ 2 ]

5 голосов
/ 29 июля 2011

Вы просто делаете больше работы во втором случае. В первом случае вы можете переполнить свой стек, но каждая операция действительно проста, и :: настолько мал, насколько вы можете получить оболочку (все, что вам нужно сделать, - это создать оболочку и указать ее на верхушку другой список). Во втором случае вы не только изначально создаете дополнительную коллекцию и должны формировать замыкание около s и buffer для использования вложенного метода, но вы также используете более тяжелый ListBuffer, который нужно проверять для каждого += независимо от того, был ли он уже скопирован в список и использует разные пути кода в зависимости от того, пуст он или нет (для того, чтобы O(1) append работал).

4 голосов
/ 29 июля 2011

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

def split3(s: String, c: Char): Seq[String] = {
  @tailrec def recurse(i: Int, acc: List[String] = Nil): Seq[String] =  {
    val p = s indexOf (c, i)
    if (p < 0) {
      s.substring(i) :: acc
    } else {
      recurse(p + 1, s.substring(i, p) :: acc)
    }
  }
  recurse(0) // would need to reverse
}

Я рассчитал, что split3 будет быстрее, за исключением, конечно, чтобы получить тот же результат, он должен был бы обратить вспять результат.

Кажется, ListBuffer вносит недостатки, которые не может компенсировать оптимизация хвостовой рекурсии.

Редактировать: думать о том, чтобы избежать обратного ... 

def split3(s: String, c: Char): Seq[String] = {
  @tailrec def recurse(i: Int, acc: List[String] = Nil): Seq[String] =  {
    val p = s lastIndexOf (c, i)
    if (p < 0) {
      s.substring(0, i + 1) :: acc
    } else {
      recurse(p - 1, s.substring(p + 1, i + 1) :: acc)
    }
  }
  recurse(s.length - 1)
}

Это имеет оптимизацию хвостового вызова и позволяет избежать ListBuffer.

...