Michael (mikkim08) wrote in ru_scala,
Michael
mikkim08
ru_scala

Функциональное Решение

Я тут попробовал продемонстрировать на простом и знакомом примере преимущество функционального подхода.
Надеюсь, что в решении ничего не упустил. Насколько корректным и, главное, убедительным Вам представляется это решение ?

--

Допустим, нам нужно найти одну какую-нибудь пару элементов в отсортированном массиве целых чисел, сумма которых равна заданному числу target.

Решение заключается в проходе по массиву слева направо и справа налево с помощью двух индексов right и left: right указывает на правый текущий элемент, а left на левый. На каждой итерации проверяется сумма текущего левого и правого элементов. Если она равна target'у, то искомая пара найдена, если меньше, то right сдвигается влево, а если больше, то left сдвигается вправо.
def pair(a: Array[Int], target: Int): Option[(Int, Int)] = {

    var left = 0
    var right = a.length - 1
    var result: Option[(Int, Int)] = None
    while (left < right && result.isEmpty) {
      (a(left), a(right)) match {
        case (x, y) if x + y == target => result = Some(x, y)
        case (x, y) if x + y < target => left = left + 1
        case (x, y) if x + y > target => right = right - 1
      }
    }
    result
  }
А что если нам нужно найти не одну а все пары элементов массива, сумма которых равна target'у ?
Тогда придётся переписать наше решение:
def pairs(a: Array[Int], target: Int): List[(Int, Int)] = {

    var left = 0
    var right = a.length - 1
    var result: List[(Int, Int)] = List()
    while (left < right) {
      (a(left), a(right)) match {
        case (x, y) if x + y == target => result = result :+ (x, y); left = left + 1
        case (x, y) if x + y < target => left = left + 1
        case (x, y) if x + y > target => right = right - 1
      }
    }
    result
  }
А можно обойтись без copy-paste ?

Оказывается можно, если написать "функциональное" решение !
Сначала мы сформируем ленивый список (stream) всех "кандидатов":
def streamOfPairs(a: Array[Int], target: Int): Stream[(Int, Int)] =
    Stream.iterate(a) { xs => if (xs.head + xs.last > target) xs.init else xs.tail }
      .take(a.length - 1)
      .map { xs => (xs.head, xs.last) }
А теперь из полученного "стрима" легко получим как одну, так и все искомые пары:
 def pair(a: Array[Int], target: Int): Option[(Int, Int)] =
    streamOfPairs(a, target) find { case (x, y) => x + y == target }

  def pairs(a: Array[Int], target: Int): List[(Int, Int)] =
    (streamOfPairs(a, target) filter { case (x, y) => x + y == target }).toList
Как видим, "функциональный подход" помог нам избавиться от copy-paste и упростить решение.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 6 comments