Как вы улучшаете производительность foldLeft (или scanLeft), когда вам не всегда нужно проверять все элементы списка? - PullRequest
Новая
       9

Как вы улучшаете производительность foldLeft (или scanLeft), когда вам не всегда нужно проверять все элементы списка?

4 голосов
/ 22 января 2020

Например, если у вас есть миллионы элементов, но обычно вам нужно только изучить первый миллион (например, если вы накапливаете сумму и насыщаете ее каким-то максимальным значением, или у вас есть какая-то другая сложная структура данных, которую вы строите, но вы fini sh после изучения первых M элементов). FoldLeft всегда заставляет вас перебирать всю последовательность. В идеале, вы могли бы предоставить предикат, который позволит foldLeft знать, что вы закончили.

Если scanLeft оценивается лениво (?), Возможно, scanLeft вместе с find (find first valid element) может выполнить sh этого. Я полагаю, что что-то подобное будет работать в Haskell, но не уверен насчет Scala. 

numbers.scanLeft(0)((a, b) => a + b).find(_ >= 100)

Так что, если numbers = List (100,0,9,10), то scanLeft будет смотреть только на первый элемент.

1 Ответ

3 голосов
/ 22 января 2020

scanLeft создает коллекцию lazy для уже коллекций lazy , таких как Iterator или LazyList ( Стрем до 2.13) . Таким образом, вы можете использовать это для раннего прерывания.
Например: 

LazyList.continually(100)
  .scanLeft(0) { case (acc, n) => acc + n }
  .takeWhile(_ < 1000)
  .toList
// res: List[Int] = List(0, 100, 200, 300, 400, 500, 600, 700, 800, 900)

List(0, 100, 5, 300)
  .iterator
  .map(i => { println(i); i })
  .scanLeft(0) { case (acc, n) => acc + n }
  .find(_ >= 100)
// 0
// 100
// res: Option[Int] = Some(100)
...