performance - 在 DNA 中寻找基序

Question

问题可以在这里找到: 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 会花费很多时间。迭代器只是迭代器？

谢谢!

Answer 1

滑动 对于字符串来说效率不高。它将字符串分解为字符，将它们装箱，然后将它们重新组合成一个字符串。

最快的方法是使用 String 上的 regionMatches 方法，但并不难。 (更快的 DNA 是将所有内容转换为字节，更快的是将其转换为 2 位半字节并打包成 int 数组。)