Blütenfilter in Kotlin

Question

Ich hätte gerne einen Code-Review. Nicht so sehr darauf, ob die Implementierung gut oder effizient ist, wahrscheinlich nicht, mehr auf Codestil und Lesbarkeit.

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()
}

Answer 1

So würde ich die ConfusionMatrix-Klasse bereinigen. Ich weiß nichts über diesen Algorithmus, aber das sollte äquivalenter Code sein. Sie können diese schreibgeschützten Werte auf ihren Deklarationsseiten berechnen und einstellen, wenn Sie sie der Reihe nach ausführen. Alle Parameter können also sein valund Sie brauchen nicht lazy, was Ihre Eigenschaft in eine LazyKlasse einschließt. Es gibt keine benutzerdefinierten Getter und keine Setter, sodass die gesamte Klasse unveränderlich und kompakt ist und keine Verweise auf etwas anderes enthält, sobald sie instanziiert wurde.

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()
    }
}

Da ich nichts über den Algorithmus weiß, würde ich sagen, dass BloomFilter ziemlich sauber ist, aber Sie könnten die Deklaration natürlicher so schreiben salts:

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

oder

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

Die zweite Form wird normalerweise Lambdas vorgezogen, wenn es eine Funktion gibt, die genau mit der erforderlichen Signatur übereinstimmt, da sie den Typ anzeigt. Hier nicht wirklich hilfreich, aber hilfreich in einer Kette von funktionalen Aufrufen, um es später besser lesbar zu machen.

In Ihrer Hauptmethode ein paar kleine Tipps ...

Wenn Sie eine Art Protokollierungsaktion ohne Nebeneffekte ausführen möchten, während Sie einer Variablen etwas zuweisen, können Sie also. Es schwächt es für jemanden ab, der Ihren Code liest, besonders wenn es sich um eine Aktion handelt, die ein paar Zeilen Code erfordert. Es ist hier nicht allzu nützlich, da es so einfach ist, aber es könnte für Sie in anderen Situationen nützlich sein.

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

Und es gibt eine Funktion, um etwas zu bestätigen und eine Laufzeitausnahme auszulösen, wenn dies fehlschlägt, damit Ihr letztes Bit aufgeräumt werden kann:

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

Answer 2

Nachdem ich es mir ein bisschen angeschaut habe

HashedIndex macht viele Dinge. Es salzt den Input, hasht ihn, verpackt ihn und stellt sicher, dass er in die Größe passt. Könnte es aufgeteilt werden und klarer, was passiert?

Die Verwirrungsmatrix scheint eine allgemeine mathematische Sache zu sein, warum hat sie eine direkte Abhängigkeit von einem BloomFilter und seinen Daten? Versuchen Sie, diese irgendwie zu entkoppeln, damit die Konfusionsmatrix für andere statistische Zwecke wiederverwendet werden kann.

countTruePositiveAndFalseNegative und countFalsePositiveAndTrueNegative sieht sehr nach Wiederholung aus, kann die Logik auf eine einzelne Implementierung verschoben werden?

Keine der Klassen implementiert Schnittstellen oder abstrakte Methoden, sodass ihre Verwendung eine Abhängigkeit von der konkreten Implementierung erfordern würde, was das Testen und Ändern der Abhängigkeit unnötig erschwert.

Es gibt ein mögliches Problem bei der Division durch Null, wenn inFilterCount oder notInFilterCount null ist.