Scala, сортировка

Question

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

Answer 1

Пусть у нас есть:

val text: List[String] = """
У меня живет козленок
 Я сама его пасу
 Я козленка в сад зеленый
 Рано утром отнесу
 Он заблудится в саду
 Я в траве его найду
""".replace("\n", "").split(" ").toList

Тогда смотри, есть простое решение, однако долгое решение


val result = desiredWords.map(word => word -> text.count(_ == word)).toMap

// result = Map(Я -> 3, в -> 3, его -> 2, Ленин -> 0)

Его сложность в данный момент составляет O(N * T), где N - кол-во искомых слов, а T кол-во слов в тексте. Если ты собираешься искать все слова в тексте, то тогда такое вычисление займет O(N^2), что как бы плохо.

Альтернативное решение:

import scala.collection.mutable

val result = mutable.HashMap.empty[String, Int]

text.foreach{ word => 
  val nTimesFound = result.getOrElse(word, 0)
  result.update(word, nTimesFound + 1)
}

Давай пробежимся по тексту один раз и просто посчитаем кол-во всех слов в нужном тебе тексте. Для места хранения выберем mutable.HashMap. Согласно вот этому источнику, скорость добавления нового элемента или изменения элемента в этой HashMap составляет eC (амортизированная константа). Тогда конечная производительность O(N) - значительно лучше чем было раньше.

P.S. Вообще изменяемые коллекции в Scala не особо частый выбор разработчика, ведь у НЕизменяемых коллекций есть ряд преимуществ, а их недостатки легко компенсируются тем как разработчики обычно пишут код. Если надо, могу далее привести пример того как можно решить подобную задачу быстрее чем за O(n^2) на неизменяемой коллекции. ?

БЛОГ НА HUSL

Scala, сортировка

Ответы (1 шт):