Bloomfilter di Kotlin

Question

Saya ingin review kode. Tidak terlalu banyak tentang apakah implementasinya baik atau efisien, mungkin tidak, lebih pada gaya kode dan keterbacaan.

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

Inilah cara saya membersihkan kelas ConfusionMatrix. Saya tidak tahu apa-apa tentang algoritme ini, tetapi ini harus kode yang setara. Anda dapat menghitung dan menyetel nilai-nilai hanya-baca ini di situs deklarasi mereka jika Anda melakukannya secara berurutan. Jadi semua parameter bisa valdan Anda tidak perlu lazy, yang membungkus properti Anda dalam sebuah Lazykelas. Tidak ada pengambil kustom dan tidak ada penyetel, jadi seluruh kelas tidak dapat diubah dan kompak tanpa referensi ke apa pun setelah dibuat.

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

Karena tidak mengetahui apa-apa tentang algoritme, menurut saya BloomFilter cukup bersih, tetapi Anda dapat secara lebih alami menulis deklarasi saltsseperti ini:

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

atau

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

Bentuk kedua biasanya lebih disukai daripada lambda ketika ada fungsi yang sama persis dengan tanda tangan yang diperlukan karena memperlihatkan tipe. Tidak terlalu membantu di sini, tetapi membantu dalam rangkaian panggilan fungsional agar lebih mudah dibaca nanti.

Dalam metode utama Anda, beberapa tip kecil ...

Bila Anda ingin melakukan semacam tindakan pencatatan tanpa efek samping saat Anda menetapkan sesuatu ke variabel, Anda dapat menggunakan also. Ini semacam tidak menekankannya untuk seseorang yang membaca kode Anda, terutama jika itu beberapa tindakan yang membutuhkan beberapa baris kode. Ini tidak terlalu berguna di sini karena ini sangat sederhana, tetapi mungkin berguna untuk Anda dalam situasi lain.

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

Dan ada fungsi untuk menegaskan sesuatu dan melontarkan pengecualian waktu proses jika gagal, sehingga bit terakhir Anda dapat dibersihkan:

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

Answer 2

Setelah melihatnya sedikit

hashedIndex melakukan banyak hal. Ini mengasinkan masukan, meng-hash, membungkusnya, dan memastikannya sesuai dengan ukurannya. Mungkinkah itu terpecah dan lebih jelas apa yang terjadi?

Matriks konfusi tampak seperti hal matematika umum, mengapa ia memiliki ketergantungan langsung pada BloomFilter dan datanya? Cobalah untuk mencari cara untuk memisahkan ini sehingga matriks kebingungan dapat digunakan kembali untuk keperluan statistik lainnya.

countTruePositiveAndFalseNegative dan countFalsePositiveAndTrueNegative terlihat sangat mirip pengulangan, dapatkah logikanya dipindahkan ke implementasi tunggal?

Tidak ada kelas yang mengimplementasikan antarmuka atau metode abstrak, jadi menggunakannya akan membutuhkan ketergantungan pada implementasi konkret, membuat ketergantungan yang tidak perlu sulit untuk diuji dan diubah.

Ada kemungkinan pembagian dengan nol masalah jika inFilterCount atau notInFilterCount adalah nol.