Преобразовать проблему L oop в рекурсивное решение в Scala - PullRequest
Новая
       31

Преобразовать проблему L oop в рекурсивное решение в Scala

1 голос
/ 12 февраля 2020

Я написал следующий метод (работает отлично), который берет список и возвращает список списков, содержащих элементы, так что первый список содержит половину элементов списка, следующий содержит половину оставшихся элементов, и скоро. Например, 

repHalve(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15))

Возвращение: 

List(List(1, 2, 3, 4, 5, 6, 7, 8), List(9, 10, 11, 12), List(13, 14), List(15))

Вопрос в том, что я новичок в Scala и хотел преобразовать этот метод в рекурсивный подход. Пожалуйста, дайте мне знать, как мне это преобразовать. Я знаю, что базовый случай может быть таким же, как условие внутри, пока l oop, но все еще не в состоянии понять это. Любая помощь будет высоко ценится. Спасибо 

def repHalve(list:List[Any]){

    var local_list:List[Any] = list
    var list_of_lists:List[Any] = List.empty

    while(local_list.length>1){
      val sub = local_list.slice(0, (local_list.length/2)+1)
      list_of_lists  ++= List(sub)
      local_list = local_list.slice(local_list.length/2+1, local_list.length)
    }

    list_of_lists ++= List(List(list.last))
    println(list_of_lists)
  }

Ответы [ 2 ]

2 голосов
/ 12 февраля 2020

Рассмотрим аналогичное решение для Luis ', но используя splitAt

def repHalve(l: List[Int]): List[List[Int]] = {
  def half(i: Int): Int = if ((i % 2) == 0) i / 2 else (i + 1) / 2

  @annotation.tailrec
  def loop(l: List[Int], size: Int, acc: List[List[Int]]): List[List[Int]] = l match {
    case x :: Nil => (List(x) :: acc).reverse
    case _ =>
      val (left, right) = l.splitAt(half(size))
      loop(right, right.size, left :: acc)
  }
  loop(l, l.size, Nil)
}

jmh, используя (1 to 200).toList в качестве входных данных, указывающих, что решение Luis быстрее 

[info] So60178352._luis   thrpt    5  666357.490 ± 165323.129  ops/s
[info] So60178352._mario  thrpt    5  591174.959 ± 118097.426  ops/s
2 голосов
/ 12 февраля 2020

Вот полностью хвостовая рекурсивная реализация.
Дайте мне знать, если у вас есть какие-либо вопросы. 

def repHalve[T](list: List[T]): List[List[T]] = {
  def half(i: Int): Int = 
    if ((i % 2) == 0) i / 2 else (i + 1) / 2

  @annotation.tailrec
  def loop(remaining: List[T], targetLength: Int, acc: List[List[T]]): List[List[T]] =
    remaining match {
      case Nil => acc.reverse

      case list =>
        @annotation.tailrec
        def innerLoop(remaining: List[T], currentLength: Int, acc: List[T]): (List[T], List[T]) =
          remaining match {
            case x :: xs =>
              if (currentLength != targetLength)
                innerLoop(remaining = xs, currentLength + 1, x :: acc)
              else
                (x :: xs, acc.reverse)
            case Nil =>
              (Nil, acc.reverse)
          }

        val (remaining, newList) = innerLoop(remaining = list, currentLength = 0, acc = List.empty)
        loop(remaining, half(targetLength), newList :: acc)
    }

  loop(remaining = list, targetLength = half(list.length), acc = List.empty)
}

Которые вы можете использовать следующим образом: 

repHalve((1 to 20).toList)
// res: List[List[Int]] = List(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), List(11, 12, 13, 14, 15), List(16, 17, 18), List(19, 20))
...