Блум-фильтр реализация в Clojure


Фон

Блум-фильтр - это структура данных, к которой мы можем вставлять элементы, и проверить, если он уже содержится данный элемент. Особенность заключается в том, что если contains запрос возвращает trueтогда это может быть возможным, что, собственно, этот элемент не был вставлен в фильтр. (Если, с другой стороны, он возвращает falseэтот элемент был определенно не вставлен ранее.)

Реализация состоит из бит-вектор длины n (изначально все биты 0), и k хэш-функций, отображающих любые значения в диапазоне ([0...n)т. е. 0 включительно, n эксклюзивный). При добавлении элемента, мы вычисляем его отображаемое значение для всех n хэш-функции, и установить соответствующие биты в один, в битовый вектор. Аналогично, при запросе, если элемент был добавлен, мы вычисляем значение для всех хэш-функций и возвращение trueесли все соответствующие биты trueи false в противном случае (т. е. если соответствующий бит по крайней мере одна функция равна нулю).

Цели обзора

Пока ни одного замечания/предложения всегда приветствуются, я в основном заинтересованы в следующих аспектах:

  1. Это правильная реализация структуры данных, или вы видите какие-либо недостатки?

  2. Есть ли способ, чтобы сделать осуществление более оптимальный? (Напр. есть ли элегантный способ в bloom-contains выпрыгнуть из reduce если мы сталкиваемся немного не равны 1?)

  3. В связи с выше: есть ли способ сделать этот код более идиоматические? (Т. е., соответствуя в Clojure лучшие практики.)

  4. Можете ли вы вспомнить какие недостающие анализы? Или некоторые другие пограничные случаи, которые не подпадают?

Из области

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

Код

core.clj

(ns bloom-filter.core)


(defn bloom-create [numbits hash-functions]
      (if (or (nil? numbits) (nil? hash-functions)) nil
          {:bits (vec (repeat numbits 0)) :hash-functions hash-functions}))

(defn bloom-add [bloom-filter value]
      (when-not (nil? bloom-filter) 
      (let [hash-functions (:hash-functions bloom-filter)
            bits           (:bits bloom-filter)
            new-bits (reduce (fn [actual-bits hash-function] (assoc actual-bits (hash-function value) 1)) bits hash-functions)]
      (assoc-in bloom-filter [:bits] new-bits))))

(defn bloom-contains [bloom-filter value] 
      (let [hash-functions (:hash-functions bloom-filter)
            bits (:bits bloom-filter)]
      (reduce (fn [actual-value hash-function] (and actual-value (= 1 (bits (hash-function value))))) true hash-functions)))

core-test.clj

(ns bloom-filter.core-test

(:require [clojure.test :refer :all]
          [bloom-filter.core :refer :all]))

(defn mod7-fun [num] (mod num 7))
(defn always-zero-fun [dontcare] 0)  

(deftest create-test
  (testing "create bloom filter"
    (is (= nil (bloom-create nil nil)))
    (is (= nil (bloom-create 0 nil)))
    (is (= nil (bloom-create nil [])))
    (is (= {:bits [] :hash-functions []} (bloom-create 0 [])))
    (is (= {:bits [0] :hash-functions []} (bloom-create 1 [])))
    (is (= {:bits [] :hash-functions [always-zero-fun]} (bloom-create 0 [always-zero-fun])))
))

(deftest add-test
  (let [empty-filter (bloom-create 7 [])
        single-fun-filter (bloom-create 7 [mod7-fun])
        two-fun-filter (bloom-create 7 [mod7-fun always-zero-fun])]
  (testing "add to bloom filter"
    (is (= nil (bloom-add nil 3)))
    (is (= empty-filter (bloom-add empty-filter nil)))
    (is (= empty-filter (bloom-add empty-filter 10)))
    (is (= {:bits [0 0 0 1 0 0 0] :hash-functions [mod7-fun]}
           (bloom-add single-fun-filter 3)))
    (is (= {:bits [1 0 0 1 0 0 0] :hash-functions [mod7-fun always-zero-fun]}
           (bloom-add two-fun-filter 3)))
)))

(deftest contains-test
  (let [empty-filter (bloom-create 7 [])
        simple-filter (bloom-create 7 [mod7-fun])
        filter-with-element (bloom-add simple-filter 3)]
  (testing "bloom filter contains"
    (is (true? (bloom-contains empty-filter 0)))
    (is (false? (bloom-contains simple-filter 0)))
    (is (true? (bloom-contains filter-with-element 3)))
    (is (true? (bloom-contains filter-with-element 10)))
)))

GitHub РЕПО

Версии на этот вопрос.



163
2
задан 7 февраля 2018 в 08:02 Источник Поделиться
Комментарии
1 ответ

Во-первых, это очень хороший вопрос и постановка задачи. Мой комментарий состоит в основном из усовершенствований стиль код купить, может быть, вы все равно найдете его полезным.

bloom-create функция


  • Вместо (if ... nil ...) вы можете использовать (when-not ... ...).

  • Аргумент hash-functions это набор функций, так что вы должны
    писать (empty? hash-functions) вместо (nil? hash-functions).
    Помните, что это меняет семантику программы.

  • Я предпочитаю писать простым аргументом проверки assertвыражения.
    Как: (assert (every? ifn? hash-functions)) и (assert (number? numbits)).

  • Вместо вектор нулей можно использовать (vector-of :boolean ...)для
    более высокую производительность.

  • Я думаю, что вы должны убедиться, что хэш-функция не возвращает значение из диапазона. Вы можете сделать это путем составления их с #(mod % numbits).

bloom-add функция


  • Вместо (when-not (nil? bloom-filter) ...) you can write (when bloom-filter ...)

  • Вы можете использовать деструктурируется , чтобы получить
    Содержание bloom-filter параметр.

  • Вы должны использовать (assoc ... :bits ...) вместо (assoc-in ... [:bits] ...).

  • Вы можете использовать нить в прошлом
    макрос для организации кода.

  • Можно использовать переходные структуры данных в reduce чтобы быстрее думает. К сожалению, они не работают с vector-of на данный момент :(

bloom-contains функция

Тестовые случаи


  • Ваша структура данных является неизменным, поэтому вы можете использовать empty-filter, single-fun-filter и two-fun-filter между тестов.

  • В add-test вы можете только проверить :bits часть результата таким образом делая тестов короче.

Код

(defn bloom-create [numbits hash-functions]
(when-not (or (nil? numbits) (empty? hash-functions))
(assert (number? numbits))
(assert (every? ifn? hash-functions))
{:bits (apply vector-of :boolean (repeat numbits false))
:hash-functions (mapv (partial comp #(mod % numbits)) hash-functions)}))

(defn bloom-add [{:keys [hash-functions bits] :as bloom-filter} value]
(when-not (nil? bloom-filter)
(->> hash-functions
(reduce (fn [actual-bits hash-function]
(assoc actual-bits (hash-function value) true)) bits)
(assoc bloom-filter :bits))))

(defn bloom-contains? [{:keys [hash-functions bits]} value]
(some (map #(false? (bits (% value))))))

(require '[clojure.test :refer :all])

(defn mod7-fun [num] (mod num 7))
(defn always-zero-fun [dontcare] 0)
(def single-fun-filter (bloom-create 7 [mod7-fun]))
(def two-fun-filter (bloom-create 7 [mod7-fun always-zero-fun]))

(deftest add-test
(testing "add to bloom filter"
(is (= nil (bloom-add nil 3)))
(is (= [false false false true false false false]
(:bits (bloom-add single-fun-filter 3))))
(is (= [true false false true false false false]
(:bits (bloom-add two-fun-filter 3))))))

1
ответ дан 9 февраля 2018 в 09:02 Источник Поделиться