Как смоделировать фильтр Блума в Scala - PullRequest
Новая
       84

Как смоделировать фильтр Блума в Scala

0 голосов
/ 04 марта 2019

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

Моя проблема заключается в следующем: если я использую класс case, янужен конструктор для генерации хеш-функций и массива битов, в котором будут храниться фактические данные фильтра Блума.Но затем, в таком методе, как «add», который изменит содержимое массива битов, мне нужно вернуть новый фильтр Блума, а не изменять содержимое существующего, чтобы мой метод был прозрачно ссылочным.

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

Так как же мне это моделировать в Scala?

1 Ответ

0 голосов
/ 04 марта 2019

[Изменено для использования BitSet, следующий комментарий]

Это краткое описание того, как это может работать. 

trait HashFunctions[T] {
  def apply(value: T): BitSet
}

object Bloom {
  class BloomFactory[T](hash: HashFunctions[T]) {
    case class Bloom(flags: BitSet) {
      def add(value: T): Bloom =
        Bloom(flags union hash(value))
      def test(value: T): Boolean =
        hash(value).subsetOf(flags)
    }
  }

  def apply[T](): BloomFactory[T]#Bloom = new BloomFactory(DefaultHashFunctions[T]).Bloom(BitSet.empty)
}

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

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

...