Bloomfilter ใน Kotlin

Question

ฉันต้องการตรวจสอบโค้ด ไม่มากนักหากการนำไปใช้งานนั้นดีหรือมีประสิทธิภาพก็อาจจะไม่ได้เพิ่มเติมเกี่ยวกับรูปแบบโค้ดและความสามารถในการอ่าน

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 ฉันไม่รู้อะไรเลยเกี่ยวกับอัลกอริทึมนี้ แต่ควรเป็นรหัสที่เทียบเท่ากัน คุณสามารถคำนวณและตั้งค่าแบบอ่านอย่างเดียวเหล่านี้ได้ที่ไซต์การประกาศหากคุณทำตามลำดับ ดังนั้นพารามิเตอร์ทั้งหมดสามารถเป็นได้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)

รูปแบบที่สองมักจะนิยมใช้กับ lambdas เมื่อมีฟังก์ชันที่ตรงกับลายเซ็นที่ต้องการทั้งหมดเนื่องจากแสดงประเภท ที่นี่ไม่มีประโยชน์จริง ๆ แต่มีประโยชน์ในสายการโทรที่ใช้งานได้เพื่อให้อ่านได้ง่ายขึ้นในภายหลัง

ในวิธีการหลักของคุณเคล็ดลับเล็ก ๆ น้อย ๆ ...

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."
}

Answer 2

ตามมาดูกันสักหน่อย

hashedIndex ทำหลายอย่าง ใส่เกลือลงแฮชห่อและทำให้แน่ใจว่าพอดีกับขนาด มันสามารถแยกออกและชัดเจนมากขึ้นว่าเกิดอะไรขึ้น?

เมทริกซ์ความสับสนดูเหมือนจะเป็นเรื่องปกติทั่วไปเหตุใดจึงมีการพึ่งพา BloomFilter และข้อมูลโดยตรง พยายามหาวิธีแยกส่วนสิ่งเหล่านี้เพื่อให้เมทริกซ์ความสับสนสามารถนำกลับมาใช้เพื่อวัตถุประสงค์ทางสถิติอื่น ๆ ได้

countTruePositiveAndFalseNegative และ countFalsePositiveAndTrueNegative ดูเหมือนการทำซ้ำมากตรรกะสามารถย้ายไปยังการใช้งานเดียวได้หรือไม่

ไม่มีคลาสใดที่ใช้อินเทอร์เฟซหรือวิธีนามธรรมดังนั้นการใช้คลาสเหล่านี้จะต้องมีการพึ่งพาการนำไปใช้อย่างเป็นรูปธรรมทำให้การทดสอบและเปลี่ยนแปลงการอ้างอิงยากโดยไม่จำเป็น

มีปัญหาในการหารด้วยศูนย์ที่เป็นไปได้ถ้า inFilterCount หรือ notInFilterCount เป็นศูนย์