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

Question

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

Совпадения слов:
То есть у нас естьList [List [Int]] (фактически список слов),
, мы сгенерируем комбинацию для каждого List [Int],
, затем мы объединяем все комбинации в карту и суммируем значение для каждого дублирующегося ключа..

Комбинация:
[0,1,2] -> [((0,1), 1), ((0,2), 1), ((1,2), 1)]

Комбинация слияний:
[((0,1), 1), ((0,2), 1), ((1,2), 1)] + [((0, 1), 1), ((0,2), 1), ((1,2), 1)] =
HashMap {(0,1): 2, (0,2): 2, (1,2): 2}

Вот версия Scala:

val arr = Array.range(0, 1000)
val counter = scala.collection.mutable.HashMap[(Int, Int), Int](  )
arr.combinations(2).toArray.map{
    row=>
        val key = (row(0), row(1))
        if (!counter.contains(key)) {
            counter(key) = 1
        }
        else {
            counter(key) += 1
        }
}
assert(counter.size == 499500)

Версия Scala 2:

val counter = arr.combinations(2).map(x => ((x(0),x(1)), 1)).toArray
.groupBy(_._1).mapValues(_.map(_._2).sum)

Вот версия Python:

import itertools    
arr = range(0, 1000)
combs = list(itertools.combinations(arr, 2))
counter = dict()
for key in combs:
    try:
        counter[key] += 1
    except KeyError:
        counter[key] = 1
assert len(counter) == 499500

Обе версии Scala стоят 9 секунд, в то время как версия Python стоит 1 секунду.
Я думаю, что я определенно делаю что-то не так с кодом, но я не мог придумать другие способы улучшить его (я новичок в Scala).

Кроме того, причина, по которой я былиспользуя mutable.HashMap - это то, что я хочу уменьшить использование памяти.

Любая помощь будет оценена, спасибо.

Answer 1

Проблема в методе объединения из коллекции.Это создает итератор, который не эффективен.Я создал еще один пример, который в 10 раз быстрее без использования комбайна:

  def time[R](block: => R): R = {
    val t0 = System.currentTimeMillis()
    val result = block    // call-by-name
    val t1 = System.currentTimeMillis()
    println("Elapsed time: " + (t1 - t0) + "ms")
    result
  }

  val arr = Array.range(0, 1000).toList

  def combinations2[A](input: List[A]): Iterator[(A, A)] =
    input.tails.flatMap(_ match {
      case h :: t => t.iterator.map((h, _))
      case Nil => Iterator.empty
    })

  val counter = scala.collection.mutable.HashMap[(Int, Int), Int](  )
  time {
    combinations2(arr).foreach {
      row =>
        val key = row
        if (!counter.contains(key)) {
          counter(key) = 1
        }
        else {
          counter(key) += 1
        }
    }
    assert(counter.size == 499500)
  }

зацените

Answer 2

Вам необходимо преобразовать arr в параллельную коллекцию.В идеале, к СДР.Так что создайте искровой контекст, получите RDD из вашего массива, как показано ниже, а затем запустите ваши операции на этом.