Bloomfilter w Kotlinie

Question

Chciałbym przejrzeć kod. Nie tyle o tym, czy implementacja jest dobra lub wydajna, prawdopodobnie nie, bardziej o stylu kodu i czytelności.

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

Oto, jak wyczyściłbym klasę ConfusionMatrix. Nie wiem nic o tym algorytmie, ale powinien to być kod równoważny. Możesz obliczyć i ustawić te wartości tylko do odczytu w ich witrynach deklaracji, jeśli wykonasz je po kolei. Zatem wszystkie parametry mogą być vali nie są potrzebne lazy, co powoduje umieszczenie Twojej właściwości w Lazyklasie. Nie ma żadnych niestandardowych metod pobierających ani ustawiających, więc cała klasa jest niezmienna i zwarta, bez odniesień do niczego innego po jej utworzeniu.

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

Nie wiedząc nic o algorytmie, powiedziałbym, że BloomFilter jest całkiem czysty, ale możesz bardziej naturalnie napisać deklarację w saltsten sposób:

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

lub

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

Druga forma jest zwykle preferowana niż wyrażenia lambda, gdy istnieje funkcja, która dokładnie pasuje do wymaganego podpisu, ponieważ pokazuje typ. Niezbyt pomocne w tym miejscu, ale pomocne w łańcuchu wywołań funkcjonalnych, aby później było bardziej czytelne.

W twojej głównej metodzie kilka małych wskazówek ...

Jeśli chcesz wykonać pewnego rodzaju rejestrowanie akcji bez skutków ubocznych, ponieważ przypisujesz coś do zmiennej, możesz użyć also. W pewnym sensie zmniejsza to znaczenie dla kogoś, kto czyta Twój kod, zwłaszcza jeśli jest to działanie, które wymaga kilku wierszy kodu. Nie jest to aż tak przydatne, ponieważ jest to takie proste, ale może być przydatne w innych sytuacjach.

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

Jest też funkcja do potwierdzania czegoś i wyrzucania wyjątku czasu wykonania, jeśli się nie powiedzie, więc ostatni bit może zostać wyczyszczony:

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

Answer 2

Po obejrzeniu tego trochę

hashedIndex robi wiele rzeczy. Solą dane wejściowe, haszują je, owijają i upewniają się, że pasują do rozmiaru. Czy można by to podzielić i wyjaśnić, co się dzieje?

Macierz zamieszania wydaje się być ogólną sprawą matematyczną, dlaczego ma bezpośrednią zależność od BloomFiltera i jego danych? Spróbuj wymyślić jakiś sposób na oddzielenie ich, aby matryca pomyłek mogła zostać ponownie wykorzystana do innych celów statystycznych.

countTruePositiveAndFalseNegative i countFalsePositiveAndTrueNegative wygląda podobnie do powtórzeń, czy logikę można przenieść do jednej implementacji?

Żadna z klas nie implementuje interfejsów ani metod abstrakcyjnych, więc ich użycie wymagałoby zależności od konkretnej implementacji, przez co zależność byłaby niepotrzebnie trudna do przetestowania i zmiany.

Istnieje możliwość podzielenia przez zero, jeśli inFilterCount lub notInFilterCount ma wartość zero.