Оптимизация метода Scala - PullRequest
Новая
       22

Оптимизация метода Scala

1 голос
/ 23 мая 2019

У меня есть def, который вызывается рекурсивно, и я использую несколько случаев.Мне интересно, есть ли хорошее решение, чтобы избавиться от этих случаев, не теряя читабельность определения. 

 @tailrec
  def getElements(existent:List[List[String]], proposed: List[List[String]], result: List[(String,List[String])]): List[(String, List[String])]= {

    proposed match {
      case head :: tail => {
        existent.find(element => identicalOfMatch(element, head)) match {

          case Some(elem) => getElements(existent.filterNot(e => e == elem), tail, ("Same", elem) :: result)
          case None =>   {
            existent.find(element => noneOfMatch(element, head) && canDelete(proposed, element)) match {

              case Some(elem) => getElements(existent.filterNot(e => e == elem), head::tail, ("Delete", elem) :: result)
              case None => {
                existent.find(element => firstOfMatch(element, head)) match {

                  case Some(elem) => getElements(existent.filterNot(e => e == elem), tail, ("Update", head) :: result)
                  case None => {
                    existent.find(element => anyOfMatch(element, head) && firstOfNotPresent(proposed, head.head) && firstOfNotPresent(existent, head.head)) match {

                      case Some(elem) =>  getElements(existent.filterNot(e => e == elem), tail, ("Update", head) :: result)

                      case None =>        getElements(Nil, Nil, existent.map(element => ("Deleted", element)) ::: proposed.map(element => ("Created", element)) ::: result)
                    }
                  }
                }
              }
            }
          }
        }
      }
      case Nil => result
    }
  }

1 Ответ

1 голос
/ 23 мая 2019

Ваша читаемость метода значительно улучшится, если вы сможете разделить его на несколько методов. К сожалению, вы не можете этого сделать, если хотите, чтобы ваша функция была хвостовой рекурсивной.

Но есть решение, которое называется trampoline , которое позволит вам создать сколь угодно глубокую цепочку рекурсивных вызовов функций, которые безопасны для стека.

Батуты реализованы в стандартной библиотеке Scala в пакете scala.util.control.TailCalls. Я переопределил ваш метод, чтобы воспользоваться им.

Первым делом я удалил параметр аккумулятора из getElements, он нам больше не нужен.

Затем я разделил getElements на три функции. Я назвал вложенные функции ifNoneMatched и ifNoneMatched2, но вы могли бы придумать более значимые имена.

Затем я обернул каждый вызов функции, находящейся в цепочке, в tailcall, а каждую константу - в done (в нашем случае Nil). Когда мне нужно было добавить что-то в список, возвращенный из рекурсивного вызова, я использовал flatMap из TailRec. 

import scala.util.control.TailCalls._

def getElements(existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]]= {

    proposed match {
      case head :: tail => {
        existent.find(element => identicalOfMatch(element, head)) match {
          case Some(elem) => tailcall(getElements(existent.filterNot(e => e == elem), tail).map(("Same", elem) :: _))
          case None => tailcall(ifNoneMatched(head, tail, existent, proposed))
        }
      }
      case Nil => done(Nil)
    }
}

def ifNoneMatched(head: List[String], tail: List[List[String]], existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]] = {
    existent.find(element => noneOfMatch(element, head) && canDelete(proposed, element)) match {

      case Some(elem) => tailcall(getElements(existent.filterNot(e => e == elem), proposed)).map(("Delete", elem) :: _)
      case None => tailcall(ifNoneMatched2(head, tail, existent, proposed))
    }
}

def ifNoneMatched2(head: List[String], tail: List[List[String]], existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]] = {
    existent.find(element => firstOfMatch(element, head)) match {

      case Some(elem) => getElements(existent.filterNot(e => e == elem), tail).map(("Update", head) :: _)
      case None => {
        existent.find(element => anyOfMatch(element, head) && firstOfNotPresent(proposed, head.head) && firstOfNotPresent(existent, head.head)) match {
          case Some(elem) =>  tailcall(getElements(existent.filterNot(e => e == elem), tail)).map(("Update", head) :: _)
          case None => getElements(Nil, Nil).map(existent.map(element => ("Deleted", element)) ::: proposed.map(element => ("Created", element)) ::: _)
        }
      }
    }
}

getElements возвращается сейчас TailRec[List[(String, List[String])]], но вы можете развернуть его, просто позвонив result.

Конечно, вы можете вкладывать методы еще глубже. Пока вы не заключите вызовы методов в tailcall, ваш стек безопасен.

Я не переопределял ваши методы, такие как identicalOfMatch и т. Д., Поэтому я не мог реально проверить, работает ли моя реализация. Если что-то сломается, пожалуйста, дайте мне знать;)

...