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

#scala #data-structures #functional-programming #case-class #bloom-filter

#scala #структуры данных #функциональное программирование #case-класс #bloom-filter

Вопрос:

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

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

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

Итак, как я должен смоделировать это в Scala?

Комментарии:

1. Я бы подумал, что вы хотели бы сохранить битовый массив private для экземпляра, создавая новый для каждого экземпляра add , а хэш-функции private — для сопутствующего объекта. (Но это просто не укладывается у меня в голове.)

Ответ №1:

[ Изменено для использования 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 обращаетесь к фильтру.

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

Комментарии:

1. Может быть, BitSet вместо Set[Int] ?

2. В рамках наивного подхода я использовал Array[Boolean] и переключаю логические значения по индексам, заданным моими хэш-функциями @AlexanderAzarov. Но я просмотрел другие реализации, и они действительно используют BitSet. В чем было бы преимущество использования BitSet (или Set[Int])?

3. @AlexanderAzarov Спасибо, я изменил код для использования BitSet , который, вероятно, будет быстрее как для добавления, так и для обновления.