Найти первые N чисел в бесконечном потоке целых чисел в стиле функционального программирования - PullRequest
Новая
       40

Найти первые N чисел в бесконечном потоке целых чисел в стиле функционального программирования

0 голосов
/ 28 июня 2019

Я столкнулся с этой интересной проблемой Scala и не уверен, как ее решить: 

class TopN {
  def findTopN(n: Int)(stream: Stream[Int]): List[Int] = {
   ???
  }
}

Это тест на навыки абстрактной обработки данных.

Функция findTopN (...) в TopN предполагается найти верхние N старших уникальных целых чисел в предполагаемом бесконечном потоке целых чисел.Для обработки Stream of Int вы можете хранить только несколько значений в памяти в данный момент времени.Следовательно, для обработки этого списка требуется эффективный для памяти способ.

Редактировать : Поскольку это бесконечный поток, я понимаю вопрос о том, каковы верхние N числа пока .Таким образом, вы должны поддерживать состояние в памяти.

Ответы [ 3 ]

2 голосов
/ 28 июня 2019

Тот факт, что вы хотите следить за верхним N «пока», указывает мне, что доступ к элементу Stream состоит в том, чтобы потреблять его. Другими словами, будет проще воспринимать Stream как Interator. 

class TopN[A](n: Int, infinite: Stream[A])(implicit ev :Ordering[A]) {

  // reverse priority queue - rpq.head will always be minimum
  private val rpq = collection.mutable.PriorityQueue[A]()(Ordering[A].reverse)
  def sofar :List[A] = rpq.toList.sorted

  // turn infinite Stream to infinite Iterator
  private val itr = infinite.iterator
  def next() :A = {
    val nxt = itr.next()
    if (rpq.size < n) rpq.enqueue(nxt)
    else if (ev.lt(rpq.head, nxt)) {rpq.dequeue();rpq.enqueue(nxt)}
    nxt
  }
  // use next() to implement other methods such as take() or drop()
}
2 голосов
/ 28 июня 2019

Если у вас есть функция topNSoFar: 

def topNSoFar(n: Int)(prev: List[Int], next: Int): List[Int] = ???

Затем вы можете запустить это в потоке как: 

def findTopN(n: Int)(stream: Stream[Int]): Stream[List[Int]] =
  stream.foldLeft(List.empty[Int])(topNSoFar(n))

Тогда просто остановись, где хочешь.

1 голос
/ 28 июня 2019

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

def findTopN(n: Int)(stream: Stream[Int]): Stream[List[Int]]

, то это будет означать, что изменит бесконечный поток случайного числа на бесконечный поток списков из лучших n случайныхчисла , и мы могли бы написать это как: 

def findTopN(n: Int)(stream: Stream[Int]): Stream[List[Int]] = {
    randomStream.scanLeft(List.empty[Int])((list, next) => {
      (next :: list).sorted(Ordering[Int].reverse) match {
        case m if m.size > n => m.init
        case m => m
      }
    })
}

val random = Random

val randomStream = Stream.iterate(random.nextInt(1000))(_ => random.nextInt(1000))

findTopN(5)(randomStream).take(10).toList.foreach(println)

И это привело бы к чему-то вроде: 

List()
List(868)
List(868, 695)
List(868, 695, 214)
List(868, 695, 453, 214)
List(973, 868, 695, 453, 214)
List(973, 868, 695, 453, 255)
List(973, 868, 695, 453, 271)
List(973, 868, 759, 695, 453)
List(973, 868, 759, 695, 466)

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

...