Создание итерируемой памяти O (1) из исходного объекта и функции, которая генерирует следующий объект в Scala - PullRequest
Новая
       17

Создание итерируемой памяти O (1) из исходного объекта и функции, которая генерирует следующий объект в Scala

6 голосов
/ 24 сентября 2010

Мне нужен удобный способ для генерации Iterable, учитывая исходный объект и функцию для создания следующего объекта из текущего, который потребляет O (1) памяти (т. Е. Он не кэширует старые результаты;если вы хотите выполнить итерацию во второй раз, функция должна быть применена снова).

Не похоже, что для этого есть поддержка библиотек.В Scala 2.8 метод scala.collection.Iterable.iterate имеет сигнатуру 

def iterate [A] (start: A, len: Int)(f: (A) ⇒ A) : Iterable[A]

, поэтому он требует, чтобы вы заранее определили, сколько приложений с итерационными функциями вам интересно, и мое понимание документации таково, что Iterable.iterate фактически вычисляет все эти значения немедленно.С другой стороны, метод scala.collection.Iterator.iterate имеет сигнатуру 

def iterate [T] (start: T)(f: (T) ⇒ T) : Iterator[T]

, которая выглядит великолепно, но мы получаем только Iterator, который не предлагает все удобства map, filter идрузья.

Есть ли удобный метод библиотеки для производства того, что я хочу?

, а если нет,

Может кто-нибудь предложить для этого «разговорный» код Scala?

Подводя итог, учитывая начальный объект a: A и функцию f: A => A, я быкак TraversableLike (например, вероятно Iterable), который генерирует a, f(a), f(f(a)), ... и использует O (1) память, с функциями map, filter и т. д., которые также возвращают что-то, что O (1) впамять.

Ответы [ 4 ]

10 голосов
/ 24 сентября 2010

Stream будет делать то, что вы хотите, только не держитесь за клетки; перебирать только значения.

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

Если вы напишите это: 

val s1: Stream[Thing] = initialValue #:: «expression computing next value»

тогда действительно каждое значение, созданное потоком, сохраняется, но это не обязательно. Если вы напишите: 

def s2: Stream[Thing] = initialValue #:: «expression computing next value»

и если вызывающая сторона просто перебирает значения потока, но не запоминает само значение потока (в частности, ни одну из его cons-ячеек), то нежелательное сохранение не произойдет. Конечно, в этой формулировке каждый вызов создает новый Stream, начиная с фиксированного начального значения. Это не обязательно: 

def s3(start: Thing): Stream[Thing] = start #:: «expression computing next value»

Единственное, на что вам нужно обратить внимание, это передать Stream методу. При этом будет зафиксирован заголовок потока, переданного в параметре метода. Одним из способов решения этой проблемы является обработка потока с помощью хвостового рекурсивного кода.

3 голосов
/ 24 сентября 2010

Iterator.iterate демо с фильтром: 

object I {
  def main(args:Array[String]) {
    val mb = 1024 * 1024
    val gen = Iterator.iterate(new Array[Int](10 * mb)){arr => 
      val res = new Array[Int](10 * mb)
      arr.copyToArray(res)
      println("allocated 10mb")
      res(0) = arr(0) + 1 // store iteration count in first elem of new array
      res
    }
    // take 1 out of 100
    val gen2 = gen filter (arr => arr(0) % 100 == 0) 
    // print first 10 filtered
    gen2.take(10).foreach { arr => println("filtered " + arr(0)) } 
  }
}

(это может не работать в REPL, так как шаг PRINT может испортить управление памятью)

JAVA_OPTS="-Xmx128m" scala -cp classes I покажет, что фильтрация работает и ленива. Если бы это не было сделано в постоянной памяти, это вызвало бы ошибку кучи (поскольку она выделяет что-то вроде 900 * 10 МБ).

Используйте JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I для просмотра событий сборки мусора.

2 голосов
/ 24 сентября 2010

Итератор это то, что вы хотите.Итератор do имеет map, filter, takeWhile и многие другие методы, которые в памяти имеют значение O (1). Не думаю, что в памяти есть другой тип коллекции с O (1).

1 голос
/ 24 сентября 2010 
val it = new Iterable[Int] {
  def iterator = Iterator.iterate(0)(_+1)
  override
  def toString: String = "Infinite iterable"
}

Не пытайтесь использовать его в REPL (за исключением того, что внедряете его в объект или класс), так как REPL попытается напечатать его, и он не использует toString.

...