Хвост Рекурсия Vs. Рефакторинг - PullRequest
Новая
       11

Хвост Рекурсия Vs. Рефакторинг

1 голос
/ 15 марта 2011

У меня есть этот метод 

  private def getAddresses(data: List[Int], count: Int, len: Int): Tuple2[List[Address], List[Int]] = {
    if (count == len) {
      (List.empty, List.empty)
    } else {
      val byteAddress = data.takeWhile(_ != 0)
      val newData = data.dropWhile(_ != 0).tail
      val newCount = count + 1
      val newPosition = byteAddress.length + 1
      val destFlag = byteAddress.head
      if (destFlag == SMEAddressFlag) {
        (SMEAddress().fromBytes(byteAddress) :: getAddresses(newData, newCount, len)._1, newPosition :: getAddresses(newData, newCount, len)._2)
      } else {
        (DistributionList().fromBytes(byteAddress) :: getAddresses(newData, newCount, len)._1, newPosition :: getAddresses(newData, newCount, len)._2)
      }
    }
  }

Я испытываю желание переписать это таким образом 

  private def getAddresses(data: List[Int], count: Int, len: Int): Tuple2[List[Address], List[Int]] = {
    if (count == len) {
      (List.empty, List.empty)
    } else {
      val byteAddress = data.takeWhile(_ != 0)
      val newData = data.dropWhile(_ != 0).tail
      val newCount = count + 1
      val newPosition = byteAddress.length + 1
      val destFlag = byteAddress.head
      val nextIter = getAddresses(newData, newCount, len)
      if (destFlag == SMEAddressFlag) {
        (SMEAddress().fromBytes(byteAddress) :: nextIter._1, newPosition :: nextIter._2)
      } else {
        (DistributionList().fromBytes(byteAddress) :: nextIter._1, newPosition :: nextIter._2)
      }
    }
  }

Мои вопросы

  1. Является ли первый хвост рекурсивным?
  2. Как это работает? Я вызываю метод дважды в последней строке. Оценивается ли разделение вызовов методов, что?
  3. Какая версия более эффективна или как я могу написать ее более эффективно.

Простите, если код пахнет Я новичок в Scala.

Спасибо

Ответы [ 4 ]

6 голосов
/ 15 марта 2011

Ни один из них не является хвостовой рекурсией.Это происходит только тогда, когда рекурсивные вызовы происходят только как самый последний элемент вдоль некоторого пути выполнения.Если вы могли бы заменить вызов переходом к началу кода, не сохраняя состояния, а переименовывая входные переменные, то это хвостовая рекурсия.(Внутренне это именно то, что делает компилятор.)

Чтобы преобразовать обычную рекурсивную функцию в хвостовую рекурсивную функцию, когда это возможно, вам необходимо передать любые сохраненные данные, например, так: 

private def getAddresses(
  data: List[Int], count: Int, len: Int,    // You had this already
  addresses: List[Address] = Nil,           // Build this as we go, starting with nothing
  positions: List[Int] = Nil                // Same here
): (List[Address], List[Int]) {
  if (count==len) {
    (addresses.reverse, positions.reverse)  // Return what we've built, reverse to fix order
  }    
  else {
    val (addr,rest) = data.span(_ != 0)
    val newdata = rest.tail
    val position = addr.length + 1
    val flag = addr.head
    val address = (
      if (flag) SMEAddress().fromBytes(addr)
      else DistributionList().fromBytes(addr)
    )
    getAddresses(newdata, count+1, len, address :: addresses, position :: positions)
  }
}

Хвосто-рекурсивные версии более эффективны, чем нехвосто-рекурсивные версии, если все остальное равно.(В этом случае это может быть не так, поскольку список должен быть полностью изменен в конце, но у него есть огромное преимущество: он не переполняет стек, если вы используете большой len.)

Вызов метода дважды всегда запускает его дважды.Автоматическое запоминание результатов вызовов методов отсутствует - это будет чрезвычайно сложно сделать автоматически.

1 голос
/ 15 марта 2011

Поскольку все ваши входные данные являются неизменяемыми, а итоговые списки всегда будут иметь одинаковую длину, я подумал об этом решении. 

private def getAddresses(data:List[Int], count:Int, len:Int):Stream[(Address,Int)] = {
   if (count == len) {
      Stream.empty
   }else{
      val (byteAddress, _::newData) = data.span(_ != 0)
      val newAddress =
         if (byteAddress.head == SMEAddressFlag) SMEAddress().fromBytes(byteAddress)
         else DistributionList().fromBytes(byteAddress)

      (newAddress, byteAddress.length + 1) #:: getAddresses(newData, count+1, len)
}

  1. Вместо возврата пары списков, она возвращает список пар. Это позволяет легко повторить один раз. Если вам нужны отдельные списки, вы можете использовать map для их извлечения, но вы можете перезапустить другие части вашей программы, чтобы более аккуратно работать со списком пар, вместо того, чтобы использовать 2 списка в качестве параметра. *

  2. Вместо возврата списка он возвращает поток, который лениво оценивается. Эта не является хвостовой рекурсией, но способ, которым потоки лениво оцениваются, также предотвращает переполнение стека. Если вам нужен строгий список, вы можете вызвать toList для результата этой функции.

  3. Демонстрирует другие полезные методы, например, использование span с сопоставлением с шаблоном для вычисления byteAddress и newData в одной строке кода. Вы можете добавить некоторые из val, которые я удалил, если полезно иметь их имена для удобства чтения.

1 голос
/ 15 марта 2011

Просто, чтобы сделать его более «Scala'y», вы можете определить внутреннюю рекурсивную функцию для getAddresses примерно так: 

def getAddresses(data: List[Int], len: Int) = {
  def inner(count: Int, addresses: List[Address] = Nil, positions: List[Int] = Nil): (List[Address], List[Int]) = {
    if (count == len) {
     (addresses.reverse, positions.reverse)
    } else {
      val (byteAddress, rest) = data.span(_ != 0)
      val newData = rest.tail
      val newPosition = byteAddress.length + 1
      val destFlag = byteAddress.head
      val newAddress = (if (destFlag == SMEAddressFlag) SMEAddress else DistributionList()).fromBytes(byteAddress)
      inner(count+1, newAddress :: addresses, newPosition :: positions)
    }
  }

  inner(0)   //Could have made count have a default too
}
0 голосов
/ 15 марта 2011
  1. Нет.Метод является рекурсивным, если последний вызов в заданном пути выполнения является рекурсивным вызовом.Последний оцененный здесь вызов будет ::, который не является рекурсивным, поэтому он не является хвостовым рекурсивом.
  2. Да, если вы вызываете метод дважды, он будет оцениваться дважды.
  3. Второй способ более эффективен, так как здесь вы вызываете метод только один раз.
...