достали тут
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
snowps тут уверял программистов, что его циклы шибче, чем наши тут всякие флип-консы. Ну бля, ну вот навалял я код, вот его результаты (а код под кутом)
Running 70000 elements
Recursively: 12 ms
FlipCons: 28 ms
Snowps: 12110 ms
70 тыс, конечно, полная фигня, jit еще не разогрелся - но мне надоело ждать, слишком этот вариант с переменными медленный. Да все понятно и так. Даже без разогрева.
Впрочем, хотите поправить - поправьте, конечно.
Дисклеймер. Наш оппонент тут сообщил: "каждый студент знает, как написать О(N/2)" - я думаю, с оппонентами такого уровня невежества можно уже и не беседовать.
( код на скале )
import scala.annotation.tailrec
object Reverse {
def recurse[X](list: List[X]): List[X] = {
@tailrec def doit(from: List[X], to: List[X]): List[X] =
from match {
case Nil => to
case x::xs => doit(xs, x::to)
}
doit(list, Nil)
}
def tonymorris[X](list: List[X]): List[X] = (List[X]() /: list) {
case (xs, x) => x::xs
}
case class Var[X](var x: X)
def snowps[X](list: List[Var[X]]): List[Var[X]] = {
val n = list.length
for {
i <- 0 until list.length / 2
} {
val xi = list(i).x
val j = n - i - 1
list(i).x = list(j).x
list(j).x = xi
}
list
}
def time(what: String)(op: => Unit): Unit = {
val t0 = System.currentTimeMillis
op
val t1 = System.currentTimeMillis
val dt = t1 - t0
println(s"$what: $dt ms")
}
def main(args: Array[String]): Unit = {
val n = 70000
val sut = (for { i <- 0 until n} yield s"<<$i>>") toList
val sut1 = sut map (Var(_))
println(s"Running $n elements")
time("Recursively")(recurse(sut1))
time("FlipCons")(tonymorris(sut1))
time("Snowps")(snowps(sut1))
}
}