Bloomfilter trong Kotlin

Question

Tôi muốn xem lại mã. Không phụ thuộc nhiều vào việc triển khai có tốt hay hiệu quả hay không, có lẽ là không, nhiều hơn về kiểu mã và khả năng đọc.

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

Đây là cách tôi dọn dẹp lớp ConfusionMatrix. Tôi không biết bất cứ điều gì về thuật toán này, nhưng đây phải là mã tương đương. Bạn có thể tính toán và đặt các giá trị chỉ đọc này tại các trang khai báo của chúng nếu bạn làm theo thứ tự. Vì vậy, tất cả các tham số có thể có valvà bạn không cần lazy, bao bọc thuộc tính của bạn trong một Lazylớp. Không có getters tùy chỉnh và không có setters, vì vậy toàn bộ lớp là bất biến và nhỏ gọn mà không có tham chiếu đến bất kỳ thứ gì khác sau khi nó được khởi tạo.

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

Không biết gì về thuật toán, tôi muốn nói BloomFilter khá sạch sẽ, nhưng bạn có thể viết khai báo saltsnhư thế này một cách tự nhiên hơn :

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

hoặc là

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

Dạng thứ hai thường được ưu tiên hơn lambdas khi có một hàm khớp chính xác với chữ ký được yêu cầu vì nó hiển thị kiểu. Không thực sự hữu ích ở đây, nhưng hữu ích trong một chuỗi các lệnh gọi chức năng để làm cho nó dễ đọc hơn sau này.

Trong phương pháp chính của bạn, một vài mẹo nhỏ ...

Khi bạn muốn thực hiện một số loại hành động ghi nhật ký mà không có tác dụng phụ vì bạn đang gán một thứ gì đó cho một biến, bạn có thể sử dụng also. Nó loại bỏ nhấn mạnh nó đối với ai đó đang đọc mã của bạn, đặc biệt nếu đó là một số hành động cần một vài dòng mã. Nó không phải là tất cả những gì hữu ích ở đây vì điều này rất đơn giản, nhưng có thể hữu ích cho bạn trong các tình huống khác.

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

Và có một chức năng để xác nhận một cái gì đó và ném một ngoại lệ thời gian chạy nếu nó không thành công, vì vậy bit cuối cùng của bạn có thể được dọn dẹp:

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

Answer 2

Sau khi xem xét nó một chút

hashedIndex làm được nhiều thứ. Nó muối đầu vào, băm nó, bọc nó và đảm bảo nó vừa với kích thước. Nó có thể được tách ra và rõ ràng hơn những gì đang xảy ra?

Ma trận nhầm lẫn có vẻ giống như một thứ ma mị chung chung, tại sao nó lại phụ thuộc trực tiếp vào BloomFilter và dữ liệu của nó? Cố gắng tìm ra một số cách tách chúng để có thể sử dụng lại ma trận nhầm lẫn cho các mục đích thống kê khác.

countTruePositiveAndFalseNegative và countFalsePositiveAndTrueNegative trông rất giống sự lặp lại, liệu logic có thể được chuyển sang một triển khai duy nhất không?

Không có lớp nào triển khai các giao diện hoặc các phương thức trừu tượng, vì vậy việc sử dụng chúng sẽ yêu cầu sự phụ thuộc vào việc triển khai cụ thể, khiến cho phần phụ thuộc khó kiểm tra và thay đổi một cách không cần thiết.

Có thể xảy ra sự cố chia cho 0 nếu inFilterCount hoặc notInFilterCount bằng 0.