3

问题可以在这里找到： http ://rosalind.info/problems/subs/

我的问题与下面提供的两种解决方案的性能有关。

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(" "))

第二种解决方案漂亮、实用且简短。

第一个解决方案有点大，但它仍然有效。我本可以省略 val 并使用这些值使其更短，但这不是我的目标。

在看到第二个解决方案后，由于代码的长度，我对我的解决方案感到非常失望。检查了 scala 库以了解为什么第二个解决方案有效，然后我自己重新实现了它。考虑检查这两种解决方案的性能，并制作了一条巨大的 3000 万条 DNA 链。

惊讶！

表现：

第一个数字是 DNA 长度，接下来的两个数字表示第一个和第二个解决方案的执行时间（以毫秒为单位）。

11,226,096 - 4921 - 14503

33,678,288 - 6448 - 35150

为什么性能差别这么大？

我试过检查 scala 库，但找不到解释这种行为的东西。

我假设第一个解决方案是创建许多对象，因此会消耗更多内存并花费大量时间，但似乎由于某种原因它工作得更快。我怀疑这是尾递归，我怀疑 zipWithIndex 需要很多时间。迭代器只是迭代器？

谢谢！

4

1 回答 1

2

sliding对字符串无效。它将字符串分解为字符，将它们装箱，然后将它们重新组合成一个字符串。

最快的方法是使用regionMatcheson 方法String。（更快的 DNA 是将所有内容转换为字节，更快的是将其转换为 2 位半字节并打包成 int 数组。）

于 2012-11-08T22:17:09.307 回答