問題はここにあります: http://rosalind.info/problems/subs/
私が持っている質問は、以下に示す 2 つのソリューションのパフォーマンスに関係しています。
1.
def indexOfAppearances(strand: String, subStrand: String): List[Int] = {
def help0(x: String, y: String, accu: List[Int]): List[Int] =
(x contains y) match {
case true => {
val index = (x indexOfSlice y) /* index where substring appears */
val adjust = strand.length - x.length
/* adjustment since the x has all the previous
* nucleotides removed.
*/
val newX = x.drop(index + 1).mkString
/* here's the drop of index + 1 elements */
help0(newX, y, (index + adjust) :: accu) /* tail recursive call */
}
case false => accu
}
help0(strand, subStrand, List()).reverse.toList.map(x => x + 1)
//indexes are not from 0 but from 1
}
2.
val s = "ACGTACGTACGTACGT"
val t = "GTA"
val combs = s.sliding(t.length).zipWithIndex
val locations = combs.collect { case (sub, i) if (sub == t) => i + 1 }
println(locations.mkString(" "))
2 番目の解決策は、美しく機能的で短いものです。
最初のソリューションは少し大きいですが、それでも機能します。val を省略して、値を操作して短くすることもできましたが、それは私の目標ではありませんでした。
2番目の解決策を見た後、コードの長さのために私はかなりがっかりしました。scala ライブラリをチェックして、2 番目のソリューションが機能する理由を確認し、自分で再実装しました。両方のソリューションのパフォーマンスをチェックすることを考え、巨大な 3000 万の DNA ストランドを作成しました。
驚いた！
パフォーマンス：
最初の数字は DNA の長さで、次の 2 つの数字は 1 番目と 2 番目のソリューションの実行時間 (ms) を表します。
11,226,096 - 4921 - 14503
33,678,288 - 6448 - 35150
性能がこんなに違うのはなぜ？
scala ライブラリをチェックしてみましたが、この動作を説明するものは見つかりませんでした。
最初の解決策は多くのオブジェクトを作成するため、より多くのメモリを消費し、それを行うのに多くの時間がかかると思いましたが、何らかの理由ではるかに高速に動作するようです. 末尾の再帰ではないかと思いますし、zipWithIndex に時間がかかるとは思えません。イテレータは単なるイテレータですか?
ありがとう！