Подтвердить что ты не робот

Создание частотной карты для строки в Scala

Скажем, у меня есть строка, "привет", и я хочу создать частотную карту символов:

Map[Char,Int] = Map(h -> 1, e -> 1, o -> 1, l -> 2)

Я мог бы сделать это итеративно:

val str = "hello"
var counts = new scala.collection.mutable.HashMap[Char,Int]
for (i <- str) {
    if (counts.contains(i))
        counts.put(i, counts(i) + 1)
    else
        counts.put(i, 1)
}

Взаимодействуя в REPL, я обнаружил, что могу сделать что-то более сжатое и не использовать изменяемую коллекцию:

> str.groupBy(_.toChar).map{ p => (p._1, p._2.length)}
scala.collection.immutable.Map[Char,Int] = Map(h -> 1, e -> 1, o -> 1, l -> 2)

Но я не знаю о характеристиках производительности groupBy() и того, что происходит в блоке, переданном на карту (например, что именно, p).

Как я могу сделать это с помощью функциональных парадигм в Scala?

Для фона, я просто прихожу к Scala в первый раз из Ruby. В Ruby я использовал бы inject, но я не уверен, что параллельный способ сделать это в Scala:

counts = str.each_byte.inject(Hash.new(0)){ |h, c| h[c] += 1; h}
4b9b3361

ОТВЕТЫ

Ответ 1

1) Что означает p?

groupBy принимает функцию, которая отображает элементы в ключ типа K. При вызове в некоторой коллекции Coll он возвращает Map[K, Coll], который содержит сопоставления из ключей K ко всем элементам, которые сопоставлены с одним и тем же ключом.

Итак, в вашем случае str.groupBy(_.toChar) выводит отображение карты из ключа K (который является символом) в строку со всеми элементами (символами) c такими, что k == c.toChar. Вы получите следующее:

Map(e -> "e", h -> "h", l -> "ll", o -> "o")

A Map - это итерабельность пар ключей и значений. В этом случае каждая пара является символом и строкой элементов. Вызов операции Map в Map включает отображение этих пар - p - это пара, где p._1 - символ, а p._2 - связанная строка (на которую вы можете вызвать length, as вы сделали это выше).

2) Как это сделать идиоматически

Выше описано, как это сделать идиоматически - используя groupBy и Map. В качестве альтернативы вы можете использовать неизменяемую карту и рекурсию по длине строки для вычисления частот или неизменяемой карты и foldLeft.

3) Характеристика характеристик

Лучше всего > оценить. Вот пара микрочипов для сильно повторяющейся строки (~ 3GHz iMac, JDK7, Scala 2.10.0 в ночное время):

object Imperative extends testing.Benchmark {
  val str = "abc" * 750000

  def run() {
    var counts = new scala.collection.mutable.HashMap[Char,Int]
    var i = 0
    val until = str.length
    while (i < until) {
      var c = str(i)
      if (counts.contains(c))
        counts.put(c, counts(c) + 1)
      else
        counts.put(c, 1)
      i += 1
    }

    //println(f)
  }
}


object Combinators extends testing.Benchmark {
  val str = "abc" * 750000

  def run() {
    val f = str.groupBy(_.toChar).map(p => (p._1, p._2.length))
  }
}


object Fold extends testing.Benchmark {
  val str = "abc" * 750000

  def run() {
    val f = str.foldLeft(Map[Char, Int]() withDefaultValue 0){(h, c) => h.updated(c, h(c)+1)}
  }
}

Результаты:

  • Императив: $ 103 57 53 58 53 53 53 53 53 53

  • Комбинаторы: $ 72 51 63 56 53 52 52 54 53 53

  • Сложить: $ 163 62 71 62 57 57 57 58 57 57

Обратите внимание, что изменение императивной версии для использования withDefaultValue:

var counts = new scala.collection.mutable.HashMap[Char,Int].withDefaultValue(0)
var i = 0
val until = str.length
while (i < until) {
  var c = str(i)
  counts.put(c, counts(c) + 1)
  i += 1
}

по-видимому, ужасно медленный из-за пересылки каждого вызова put:

  • withDefaultValue: $ 133 87 109 106 101 100 101 100 101 101

Заключение: бокс и распаковка символов в этом случае достаточно высока, так что различия в производительности между этими подходами трудно наблюдать.

EDIT:

Обновление. Вместо тэга Benchmark вы можете использовать встроенный бенчмаркинг ScalaMeter.

Ответ 2

Расширение ответа Axel.

Ваше решение groupBy уже работает. Там крошечная крошечная коррекция, которая могла бы сделать ее более чистой:

str.groupBy(_.toChar).mapValues(_.size)

Альтернативой Scala для inject является foldLeft, foldRight, reduce, reduceOption в зависимости от того, как вы ее используете. То, как вы использовали inject в Ruby, не работает, так как ваше решение основано на мутации h, а в функциональном мире изменчивость - это "нет-нет". Здесь, как бы вы сделали решение рядом с вашим inject, но в функциональном стиле в Scala:

str.foldLeft( Map[Char, Int]() ){ (m, c) => m + (c -> (m.getOrElse(c, 0) + 1)) }

Очевидно, что groupBy выглядит намного лучше.

Ответ 3

Ваш пример по ruby ​​может быть почти непосредственно переведен на Scala с помощью foldLeft и неизменяемым Map.

Вот одно из возможных решений:

str.foldLeft(Map[Char, Int]() withDefaultValue 0){(h, c) => h.updated(c, h(c)+1)}

Собственно, если вы в порядке с локальной изменчивостью, вы можете сделать что-то вроде этого:

def charFrequencies(str: String): collection.Map[Char, Int] = {
  val hash = collection.mutable.HashMap.empty[Char, Int] withDefaultValue 0
  str foreach { hash(_) += 1 }
  hash
}

Выражение hash(_) += 1 будет отложено до c => hash(c) = hash(c) + 1, а затем до c => hash.update(c, hash.apply(c) + 1)

Это решение должно быть более эффективным, чем функциональное, поскольку оно не создает промежуточные коллекции. Кроме того, поскольку метод возвращает неизменяемый collection.Map[Char, Int], результат будет считаться неизменным (пока никто не будет выполнять небезопасное понижение на нем).