Kotlin'de Bloomfilter

Question

Bir kod incelemesi istiyorum. Uygulamanın iyi veya verimli olup olmadığı konusunda pek bir şey yok, muhtemelen değil, daha çok kod stili ve okunabilirlik üzerine.

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

ConfusionMatrix sınıfını şu şekilde temizlerim. Bu algoritma hakkında hiçbir şey bilmiyorum ama bu eşdeğer kod olmalı. Sırayla yaparsanız, bu salt okunur değerleri beyan sitelerinde hesaplayabilir ve ayarlayabilirsiniz. Böylece tüm parametreler olabilir valve ihtiyacınız yoktur lazy, bu da mülkünüzü bir Lazysınıfta sarar . Özel alıcılar yoktur ve ayarlayıcılar yoktur, bu nedenle tüm sınıf değişmez ve küçüktür ve somutlaştırıldıktan sonra başka hiçbir şeye referans yoktur.

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

Algoritma hakkında hiçbir şey bilmeden, BloomFilter'in oldukça temiz olduğunu söyleyebilirim, ancak daha doğal olarak şöyle bir açıklama yazabilirsiniz salts:

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

veya

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

Tipini gösterdiği için gerekli imzayla tam olarak eşleşen bir işlev olduğunda, ikinci form genellikle lambdalara tercih edilir. Burada pek yararlı değil, ancak daha sonra daha okunabilir hale getirmek için bir işlevsel çağrılar zincirinde yardımcı oluyor.

Ana yönteminizde, birkaç küçük ipucu ...

Bir değişkene bir şey atarken yan etkiler olmadan bir tür günlük kaydı türü eylem yapmak istediğinizde, kullanabilirsiniz also. Kodunuzu okuyan biri için, özellikle de birkaç satır kod gerektiren bir eylemse, onu biraz vurgular. Bu çok basit olduğu için burada o kadar da kullanışlı değil, ancak başka durumlarda sizin için kullanışlı olabilir.

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

Ve bir şey iddia etme ve başarısız olursa bir çalışma zamanı istisnası atma işlevi vardır, böylece son bitiniz temizlenebilir:

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

Answer 2

Biraz baktıktan sonra

hashedIndex pek çok şey yapar. Girdiyi tuzlar, hashler yapar, sarar ve boyutuna uymasını sağlar. Bölünebilir ve neler olduğu daha net olabilir mi?

Karışıklık matrisi genel bir matematiksel şey gibi görünüyor, neden bir BloomFilter'e ve verilerine doğrudan bağımlı? Bunları ayırmanın bir yolunu bulmaya çalışın, böylece karışıklık matrisi başka istatistiksel amaçlar için yeniden kullanılabilir.

countTruePositiveAndFalseNegative ve countFalsePositiveAndTrueNegative, tekrara çok benziyor, mantık tek bir uygulamaya taşınabilir mi?

Sınıfların hiçbiri arayüzler veya soyut yöntemler uygulamaz, bu nedenle onları kullanmak somut uygulamaya bir bağımlılık gerektirir, bu da dependenin test edilmesini ve değiştirilmesini gereksiz yere zorlaştırır.

İnFilterCount veya notInFilterCount sıfır ise, olası bir sıfıra bölme sorunu vardır.