Как написать эффективный фильтр groupBy-size в Scala, можно примерно

Учитывая List[Int] в Скала, я хочу получить Set[Int] из всех Intс, которые появляются по крайней мере thresh раз. Я могу сделать это с помощью groupBy или же foldLeft, затем filter, Например:

val thresh = 3
val myList = List(1,2,3,2,1,4,3,2,1)
myList.foldLeft(Map[Int,Int]()){case(m, i) => m + (i -> (m.getOrElse(i, 0) + 1))}.filter(_._2 >= thresh).keys

дам Set(1,2),

Теперь предположим, List[Int] очень большой Насколько сложно сказать, но в любом случае это кажется расточительным, так как меня не волнует каждый из Intс частотами, и мне все равно, если они хотя бы thresh, Как только это прошло thresh больше нет необходимости проверять, просто добавьте Int к Set[Int],

Вопрос: могу ли я сделать это более эффективно для очень большого List[Int],

а) если мне нужен истинный, точный результат (нет места для ошибок)

б) если результат может быть приблизительным, например, с использованием некоторого хеширования или фильтров Блума, где Set[Int] может включать некоторые ложные срабатывания, или {частота Int > thresh} на самом деле не Boolean но Double в [0-1],

Источник

4 ответа

Решение

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

Теперь, что вы можете попробовать, чтобы повысить эффективность:

  • обновлять карту только тогда, когда текущее значение счетчика меньше или равно пороговому значению. Это исключит огромное количество самых дорогих операций - обновления карты
  • попробуйте быстрее карту вместо IntMap. Если вы знаете, что значения исходного списка находятся в фиксированном диапазоне, вы можете использовать Array вместо IntMap (индекс в качестве ключа). Другой возможный вариант будет изменчивым HashMap с достаточной первоначальной емкостью. Как показывает мой тест, это на самом деле имеет большое значение
  • Как предложил @ixx, после увеличения значения на карте проверьте, равно ли оно 3, и в этом случае немедленно добавьте его в список результатов. Это избавит вас от одного линейного обхода (кажется, не столь значительным для большого ввода)

Я не понимаю, как какое-то приблизительное решение может быть быстрее (только если вы случайно игнорируете некоторые элементы). В противном случае это все равно будет O(N).

Обновить

Я создал микробенчмарк для измерения фактической производительности различных реализаций. Для достаточно большого ввода и вывода предложение Ixx относительно немедленного добавления элементов в список результатов не дает существенного улучшения. Однако аналогичный подход может быть использован для устранения ненужных обновлений карты (что представляется наиболее дорогой операцией).

Результаты тестов (среднее время работы на 1000000 элементов с предварительным прогревом):

Authors solution:
447 ms
Ixx solution:
412 ms
Ixx solution2 (eliminated excessive map writes):
150 ms
My solution:
57 ms

Мое решение предполагает использование изменчивых HashMap вместо неизменного IntMap и включает в себя все другие возможные оптимизации.

Обновленное решение Ixx:

val tuple = (Map[Int, Int](), List[Int]())
val res = myList.foldLeft(tuple) {
  case ((m, s), i) =>
    val count = m.getOrElse(i, 0) + 1
    (if (count <= 3) m + (i -> count) else m, if (count == thresh) i :: s else s)
}

Мое решение:

val map = new mutable.HashMap[Int, Int]()
val res = new ListBuffer[Int]
myList.foreach {
  i =>
    val c = map.getOrElse(i, 0) + 1
    if (c == thresh) {
      res += i
    }
    if (c <= thresh) {
      map(i) = c
    }
}

Полный источник микробенчмарка доступен здесь.

Источник

Если под "более эффективным" вы подразумеваете эффективность использования пространства (в крайнем случае, когда список бесконечен), существует вероятностная структура данных, называемая Count Min Sketch, для оценки частоты элементов внутри нее. Затем вы можете отказаться от тех с частотой ниже вашего порога.

Есть реализация Scala из библиотеки Algebird.

Источник

Вы могли бы использовать foldleft собрать соответствующие элементы, например так:

val tuple = (Map[Int,Int](), List[Int]())
myList.foldLeft(tuple) {
  case((m, s), i) => {
    val count = (m.getOrElse(i, 0) + 1) 
    (m + (i -> count), if (count == thresh) i :: s else s)
  }
}

Я мог бы измерить улучшение производительности примерно на 40% с помощью небольшого списка, так что это определенно улучшение...

Отредактировано для использования List и prepend, который занимает постоянное время (см. комментарии).

Источник

Вы можете изменить свой foldLeft Пример немного с использованием mutable.Set который строится постепенно и в то же время используется как фильтр для перебора ваших Seq используя withFilter, Тем не менее, потому что я использую withFilterя не могу использовать foldLeft и должен обойтись foreach и изменчивая карта:

import scala.collection.mutable

def getItems[A](in: Seq[A], threshold: Int): Set[A] = {
  val counts: mutable.Map[A, Int] = mutable.Map.empty
  val result: mutable.Set[A] = mutable.Set.empty

  in.withFilter(!result(_)).foreach { x =>
    counts.update(x, counts.getOrElse(x, 0) + 1)

    if (counts(x) >= threshold) {          
      result += x
    }
  }
  result.toSet
}

Таким образом, это приведет к удалению элементов, которые уже были добавлены в набор результатов при выполнении Seq в первый раз, потому что withFilterфильтрует Seqв добавленной функции (map, flatMap, foreach) вместо возврата отфильтрованного Seq,

РЕДАКТИРОВАТЬ:

Я изменил свое решение, чтобы не использовать Seq.countЭто было глупо, как правильно указал Айвен.

Используя микробенч Aiveans, я вижу, что он все еще немного медленнее, чем его подход, но все же лучше, чем первый подход авторов.

Authors solution
377
Ixx solution: 
399
Ixx solution2 (eliminated excessive map writes): 
110
Sascha Kolbergs solution: 
72
Aivean solution: 
54
Источник
Другие вопросы по тегам