Скалярное преобразование итеративный подход к функциональному подходу для итератора

Question

У меня есть следующая функция, которая имеет дело с серией поисковых событий, которые должны быть сгруппированы в потоки поиска, если они связаны.

  def split(eventsIterator: Iterator[SearchFlowSearchEvent]): Iterator[SearchFlow] = {

    val sortedEventsIterator = eventsIterator.toList.sortBy(_.evTimeMillis).iterator


    val searchFlowsEvents: mutable.MutableList[mutable.MutableList[SearchFlowSearchEvent]] = mutable.MutableList()
    var currentSearchFlowEvents: mutable.MutableList[SearchFlowSearchEvent] = mutable.MutableList()
    var previousEvent: SearchFlowSearchEvent = null
    while (sortedEventsIterator.hasNext) {
      val currentEvent = sortedEventsIterator.next()

      if (isSameFlow(previousEvent, currentEvent)) {
        currentSearchFlowEvents += currentEvent
      } else {
        currentSearchFlowEvents = mutable.MutableList()
        currentSearchFlowEvents += currentEvent
        searchFlowsEvents += currentSearchFlowEvents
      }

      previousEvent = currentEvent
    }


    searchFlowsEvents
      .map(searchFlowEvents => model.SearchFlow(searchFlowEvents.toList))
      .iterator
  }

Подход к выполнению группировки перечисленных событийВыше приведен итеративный (я из мира Java).

Может ли кто-нибудь дать мне несколько советов о том, как добиться таких же результатов функциональным способом.

Answer 1

Это та вещь, для которой вы хотите использовать хвостовую рекурсию:

        @tailrec 
        def groupEvents(
          in: Iterator[SearchFlowSearchEvent],
          out: List[List[SearchFlowSearchEvent]] = Nil
        ): List[List[SearchFlowSearchEvent]] = if (in.hasNext) {
          val next = in.next
          out match {
            case Nil => groupEvents(in, List(List(next)))
            case (head :: tail) :: rest if isSameFlow(head, next) => groupEvents(in, (next :: head :: tail) :: rest)
            case rest => groupEvents(in, List(next) :: rest)
          }
       } else out.map(_.reverse).reverse 

out содержит группы, собранные на данный момент (в обратном порядке - см. Ниже). Если он пуст, просто начните новый. В противном случае посмотрите на первый элемент (последнюю группу) и проверьте первый элемент там (последнее событие). Если поток такой же, добавьте текущее событие в эту группу, в противном случае добавьте новую группу. Повторите.

В конце (если итератор пуст), переверните списки и создайте потоки.

В таких случаях в scala принято собирать списки в обратном порядке. Это потому, что добавление в конец связанного списка (или просмотр последнего элемента) занимает линейное время, что делает всю операцию квадратичной. Вместо этого мы всегда добавляем (постоянное время), а затем обращаемся в самом конце (линейно).

В качестве альтернативы, вы можете написать то же самое с помощью foldLeft, но лично я нахожу рекурсивную реализацию немного более понятной в этом случае, хотя и немного дольше (функционально, они эквивалентны):

    in.foldLeft[List[List[SearchFlowSearchEvent]]](Nil) {
       case (Nil, next) => List(List(next))
       case ((head :: tail) :: rest, next) if isSameFlow(head, next) => 
          (next :: head :: tail) :: rest
       case (rest, next) => List(next) :: rest
    }.map { l => SearchFlow(l.reverse) }.reverse

ОБНОВЛЕНИЕ Для решения проблем производительности, поднятых в комментариях к другому посту. Я протестировал три решения для MacBook Pro, Mac OS 10.13.5, 2,9 ГГц i7, 16 ГБ оперативной памяти со scala 2.11.11 (настройки REPL по умолчанию).

Входные данные были 100000 событий, которые разбиты на 14551 групп. Я запускал каждую реализацию примерно 500 раз после прогрева и брал среднее время всех выполнений.

Первоначальная реализация заняла около 42 мс за цикл. Рекурсивный алгоритм занимает около 28 мс FoldLeft был около 29 мс

Простая сортировка массива событий и преобразование его в итератор заняла около 20 мс.

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

Answer 2

Насколько я знаю, в библиотеке коллекций нет простого встроенного решения для этого.Как сказал @Dima, для этого вам следует использовать рекурсию.

Обратите внимание, что если вы сильно заботитесь о производительности, ваше первоначальное решение с использованием коллекций var и mutable будет, вероятно, самым быстрым.Изменчивость хороша, если у вас есть для этого веские причины, и пока мутация остается локальной для определенного метода.

Чтобы прояснить ситуацию, я НЕ поощряю вас к микрооптимизации, если у вас нет эталона, показывающего, что это помогает производительности вашего приложения в незначительной степени.