Bloomfilter в Котлине

Aug 23 2020

Я хочу код-обзор. Не столько о том, хороша ли реализация или эффективна, скорее всего, нет, скорее о стиле кода и удобочитаемости.

import java.lang.Exception
import java.nio.ByteBuffer
import java.security.MessageDigest
import java.util.*
import kotlin.math.abs

fun main() {
    val filterSize = 1_000_000
    val numberOfEntries = 100_000

    val filter = BloomFilter(filterSize, numberOfHashes = 4)
    val entriesInFilter = Array(numberOfEntries) { randomString() }
    val entriesNotInFilter = Array(numberOfEntries) { randomString() }

    for (entry in entriesInFilter)
        filter.add(entry)

    val confusionMatrix = ConfusionMatrix(filter, entriesInFilter, entriesNotInFilter)
    confusionMatrix.printReport()

    if (confusionMatrix.falseNegativeRate > 0.0) {
        throw Exception("This should not happen, if it does the implementation of the bloom filter is wrong.")
    }
}

class BloomFilter(private val size: Int, numberOfHashes: Int) {
    private val flags = BitSet(size)
    private val salts = IntArray(numberOfHashes) { it }.map { it.toString() }
    private val sha = MessageDigest.getInstance("SHA-1")

    fun add(entry: String) {
        for (salt in salts) {
            val index = hashedIndex(entry, salt)
            flags.set(index)
        }
    }

    fun maybeExists(entry: String): Boolean {
        for (salt in salts) {
            val index = hashedIndex(entry, salt)
            if (!flags[index]) {
                return false
            }
        }
        return true
    }

    private fun hashedIndex(entry: String, salt: String): Int {
        val salted = entry + salt
        val hash = sha.digest(salted.toByteArray())
        val wrapped = ByteBuffer.wrap(hash)
        return abs(wrapped.int) % size
    }
}

class ConfusionMatrix(filter: BloomFilter, entriesInFilter: Array<String>, entriesNotInFilter: Array<String>) {
    private val inFilterCount = entriesInFilter.size
    private val notInFilterCount = entriesNotInFilter.size

    private var truePositiveCount = 0
    private var trueNegativeCount = 0
    private var falsePositiveCount = 0
    private var falseNegativeCount = 0

    val accuracyRate by lazy { (truePositiveCount + trueNegativeCount).toDouble() / (notInFilterCount + inFilterCount) }
    val misclassificationRate by lazy { 1.0 - accuracyRate }
    val truePositiveRate by lazy { truePositiveCount.toDouble() / inFilterCount }
    val trueNegativeRate by lazy { trueNegativeCount.toDouble() / notInFilterCount }
    val falsePositiveRate by lazy { falsePositiveCount.toDouble() / notInFilterCount }
    val falseNegativeRate by lazy { falseNegativeCount.toDouble() / inFilterCount }

    init {
        countTruePositiveAndFalseNegative(entriesInFilter, filter)
        countFalsePositiveAndTrueNegative(entriesNotInFilter, filter)
    }

    private fun countTruePositiveAndFalseNegative(entriesInFilter: Array<String>, filter: BloomFilter) {
        for (entryInFilter in entriesInFilter) {
            if (filter.maybeExists(entryInFilter)) {
                truePositiveCount++
            } else {
                falseNegativeCount++
            }
        }
    }

    private fun countFalsePositiveAndTrueNegative(entriesNotInFilter: Array<String>, filter: BloomFilter) {
        for (entryNotInFilter in entriesNotInFilter) {
            if (filter.maybeExists(entryNotInFilter)) {
                falsePositiveCount++
            } else {
                trueNegativeCount++
            }
        }
    }

    fun printReport() {
        val dataRows = mapOf(
            "Accuracy" to accuracyRate,
            "Misclassification rate" to misclassificationRate,
            "True positive rate" to truePositiveRate,
            "True negative rate" to trueNegativeRate,
            "False positive rate" to falsePositiveRate,
            "False negative rate" to falseNegativeRate
        )
        val printer = Printer(dataRows)
        printer.print()
    }
}

class Printer(private val dataRows: Map<String, Double>) {
    private val spacing = 2
    private val longestLabelLength = getLongestString(dataRows.keys, default=50) + spacing
    private val stringBuilder = StringBuilder()

    private fun getLongestString(labels: Set<String>, default: Int): Int {
        return labels.map { it.length }.max() ?: default
    }

    fun print() {
        for ((label, value) in dataRows) {
            printLabel(label)
            printPadding(label)
            printFormattedValue(value)
            println()
        }
    }

    private fun printLabel(label: String) {
        print("$label:")
    }

    private fun printPadding(label: String) {
        val paddingNeeded = longestLabelLength - label.length
        stringBuilder.clear()
        for (x in 0 until paddingNeeded) stringBuilder.append(" ")
        print(stringBuilder.toString())
    }

    private fun printFormattedValue(value: Double) {
        val width6digits2 = "%6.2f"
        val percentage = String.format(width6digits2, value * 100) + "%"
        print(percentage)
    }
}

private fun randomString(): String {
    return UUID.randomUUID().toString()
}

Ответы

2 Tenfour04 Aug 28 2020 at 03:04

Вот как бы я очистил класс ConfusionMatrix. Я ничего не знаю об этом алгоритме, но это должен быть эквивалентный код. Вы можете рассчитать и установить эти доступные только для чтения значения на их сайтах объявлений, если вы сделаете их по порядку. Таким образом, все параметры могут быть valи вам не нужны lazy, что превращает вашу собственность в Lazyкласс. Нет никаких пользовательских геттеров и сеттеров, поэтому весь класс неизменен и компактен, без ссылок на что-либо еще после его создания.

class ConfusionMatrix(filter: BloomFilter, entriesInFilter: Array<String>, entriesNotInFilter: Array<String>) {
    private val inFilterCount = entriesInFilter.size
    private val notInFilterCount = entriesNotInFilter.size

    private val truePositiveCount = entriesInFilter.count { filter.maybeExists(it) }
    private val falseNegativeCount = entriesInFilter.size - truePositiveCount
    private val falsePositiveCount = entriesNotInFilter.count { filter.maybeExists(it) }
    private val trueNegativeCount = entriesNotInFilter.size - truePositiveCount

    val accuracyRate = (truePositiveCount + trueNegativeCount).toDouble() / (notInFilterCount + inFilterCount)
    val misclassificationRate = 1.0 - accuracyRate
    val truePositiveRate = truePositiveCount.toDouble() / inFilterCount 
    val trueNegativeRate = trueNegativeCount.toDouble() / notInFilterCount
    val falsePositiveRate = falsePositiveCount.toDouble() / notInFilterCount
    val falseNegativeRate = falseNegativeCount.toDouble() / inFilterCount

    fun printReport() {
        val dataRows = mapOf(
            "Accuracy" to accuracyRate,
            "Misclassification rate" to misclassificationRate,
            "True positive rate" to truePositiveRate,
            "True negative rate" to trueNegativeRate,
            "False positive rate" to falsePositiveRate,
            "False negative rate" to falseNegativeRate
        )
        val printer = Printer(dataRows)
        printer.print()
    }
}

Ничего не зная об алгоритме, я бы сказал, что BloomFilter довольно чистый, но вы могли бы более естественно написать такое объявление salts:

private val salts = (0..numberOfHashes).map { it.toString() }

или

private val salts = (0..numberOfHashes).map(Int::toString)

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

В вашем основном методе пара маленьких советов ...

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

val confusionMatrix = ConfusionMatrix(filter, entriesInFilter, entriesNotInFilter)
    also { it.printReport() }

И есть функция для утверждения чего-либо и выдачи исключения времени выполнения в случае сбоя, так что ваш последний бит можно очистить:

require(confusionMatrix.falseNegativeRate > 0.0) {
    "This should not happen, if it does the implementation of the bloom filter is wrong."
}
Peheje Aug 23 2020 at 23:32

Посмотрев на это немного

hashedIndex многое делает. Он солит ввод, хеширует его, упаковывает и проверяет, соответствует ли он размеру. Можно ли разбить его на части и прояснить, что происходит?

Матрица путаницы кажется общей математикой, почему она напрямую зависит от BloomFilter и его данных? Попробуйте придумать способ их разделения, чтобы матрицу путаницы можно было повторно использовать для других статистических целей.

countTruePositiveAndFalseNegative и countFalsePositiveAndTrueNegative очень похожи на повторение, можно ли перенести логику в одну реализацию?

Ни один из классов не реализует интерфейсы или абстрактные методы, поэтому их использование потребует зависимости от конкретной реализации, что излишне затруднит тестирование и изменение этой зависимости.

Если inFilterCount или notInFilterCount равно нулю, возможна проблема деления на ноль.