?

Log in

Функциональное Решение - Язык программирования Scala

> Recent Entries
> Archive
> Friends
> Profile
> Официальный сайт Scala

March 6th, 2017


Previous Entry Share Next Entry
mikkim08
06:21 pm - Функциональное Решение
Я тут попробовал продемонстрировать на простом и знакомом примере преимущество функционального подхода.
Надеюсь, что в решении ничего не упустил. Насколько корректным и, главное, убедительным Вам представляется это решение ?

--

Допустим, нам нужно найти одну какую-нибудь пару элементов в отсортированном массиве целых чисел, сумма которых равна заданному числу 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 и упростить решение.

(6 comments | Leave a comment)

Comments:


[User Picture]
From:juan_gandhi
Date:March 6th, 2017 04:25 pm (UTC)
(Link)
Wow, отлично! Красиво.
From:mikkim08
Date:March 6th, 2017 06:15 pm (UTC)
(Link)
Спасибо !
From:nigredo_tori
Date:March 6th, 2017 05:25 pm (UTC)
(Link)
Насчёт "упростить" - не факт. Например, за красивостью и функциональностью незаметен тот факт что алгоритм стал квадратичным (init и tail от массива линейные).
From:mikkim08
Date:March 6th, 2017 06:16 pm (UTC)
(Link)
Спасибо. А чего это они линейные для массива ?

Edited at 2017-03-06 06:32 pm (UTC)
From:nigredo_tori
Date:March 7th, 2017 12:25 am (UTC)
(Link)
Потому что Array - это изменяемая структура. И tail/init у него происходят через копирование элементов в новый массив.
http://docs.scala-lang.org/overviews/collections/performance-characteristics.html
From:mikkim08
Date:April 15th, 2017 04:58 am (UTC)
(Link)
Упустил Ваш комментарий. Насчёт массива посмотрю. Спасибо ещё раз.

> Go to Top
LiveJournal.com