Как преобразовать алгоритм возврата в поток?

Есть ли способ определить stream с алгоритмом backtracking в Scala?

Например, следующий алгоритм backtracking печатает все «двоичные» строки заданного размера.

def binaries(s:String, n:Int) {
  if (s.size == n)
    println(s)
  else {
    binaries(s + '0', n)
    binaries(s + '1', n)
  }
}

Я считаю, что могу определить stream "двоичных" строк заданного размера, используя другой итеративный алгоритм. Однако мне интересно, смогу ли я преобразовать алгоритм возврата выше в stream.


stream scala backtracking
person Michael    schedule 24.12.2011    source источник

Ответы (2)


arrow_upward
11
arrow_downward

Это довольно просто:

def binaries(s: String, n: Int): Stream[String] = 
  if (s.size == n) Stream(s) 
  else binaries(s + "0", n) append binaries(s + "1", n)

Обратите внимание на использование append -- этот метод нестандартен для других коллекций, что является требованием, поскольку он должен принимать свой параметр по имени.

person Daniel C. Sobral    schedule 24.12.2011
comment
Спасибо, это именно то, что я ищу :) Это выглядит более эффективным (с точки зрения потребления памяти стека), чем исходная версия с возвратом, не так ли? - person Michael; 25.12.2011
comment
@Майкл Возможно. Мне неудобно анализировать эффективность кода с помощью Stream. Если я считаю необходимым их использовать, я обязательно тестирую код на REPL, чтобы убедиться, что он не переполняется. - person Daniel C. Sobral; 25.12.2011
comment
@Michael, потоковая версия менее эффективна с точки зрения использования фрейма стека. Каждый рекурсивный вызов использует 4 кадра стека по сравнению с одним в вашей версии. На практике это не должно быть проблемой для этого примера. Что касается использования памяти кучи, класс Stream является одним из наименее эффективных в коллекции scala с точки зрения использования памяти на каждую сохраненную ссылку, но обычно это нормально, если вы случайно не удерживаете голову потока... - person huynhjl; 25.12.2011

arrow_upward
3
arrow_downward

Вы можете, но он не будет лениво оценивать:

def bin(s: String, n: Int): Stream[String] = {
  if (s.length == n) { 
    println("got " + s) // for figuring out when it's evaluated
    Stream(s)
  } else {
    val s0 = s + '0'
    val s1 = s + '1'
    bin(s0, n) ++ bin(s1, n)
  }
}

Например, при выполнении bin("", 2).take(2).foreach(println) вы получите следующий вывод:

scala> bin("", 2).take(2).foreach(println)
got 00
got 01
got 10
got 11
00
01

Если вы не возражаете против использования TraversableView, вы можете использовать преобразование, описанное здесь https://stackoverflow.com/a/3816012/257449< /а>. Итак, код становится:

def toTraversable[T]( func : (T => Unit) => Unit) = new Traversable[T] {
  def foreach[X]( f : T => X) = func(f(_) : Unit)                       
}  

def bin2(str: String, n: Int) = {
  def recurse[U](s: String, f: (String) => U) {
    if (s.length == n) { 
      println("got " + s) // for figuring out when it's evaluated
      f(s)
    } else {
      recurse(s + '0', f)
      recurse(s + '1', f)
    }
  }
  toTraversable[String](recurse(str, _)) view
}

потом

scala> bin2("", 2).take(2).foreach(println)
got 00
00
got 01
01
got 10
person huynhjl    schedule 24.12.2011
comment
Немного поиска ScalaDoc может иметь большое значение... :-) - person Daniel C. Sobral; 25.12.2011
comment
@DanielC.Sobral, действительно, я никогда раньше не использовал и не видел append. - person huynhjl; 25.12.2011