Я создавал более быстрый метод разделения строк. Сначала я написал версию без хвостовой рекурсии, возвращающую 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.