Нахождение мотива в ДНК

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 и просто работать со значениями, чтобы сделать его короче, но это не было моей целью.

После просмотра 2-го решения я был очень разочарован из-за длины кода. Проверил библиотеку scala, чтобы увидеть, почему работает 2-е решение, а затем заново внедрил его. Мысль о проверке производительности обоих решений и сделал огромные 30 миллионов нитей ДНК.

Удивление!

Спектакль:

Первое число - это длина ДНК, а следующие два числа представляют время выполнения 1-го и 2-го решения (в мс).

11,226,096 - 4921 - 14503

33 678 288 - 6448 - 35150

Почему производительность так сильно отличается?

Я попытался проверить библиотеку scala, но не смог найти ничего, что объясняет такое поведение.

Я предположил, что первое решение заключается в создании множества объектов, что потребляет больше памяти и занимает много времени, но кажется, что по какой-то причине оно работает намного быстрее. Я сомневаюсь, что это хвостовая рекурсия, и я сомневаюсь, что zipWithIndex занимает много времени. Итераторы просто итераторы?

Спасибо!

Answer 1

sliding не эффективен со строками. Он разбивает строку на символы, упаковывает их в блоки, а затем собирает их в строку.

Самый быстрый способ сделать это, который все еще не невероятно труден, - это regionMatches метод на String, (Быстрее, но с ДНК - конвертировать все в байты, быстрее - конвертировать его в 2-битные кусочки и упаковывать в массивы int.)