Kotlin의 Bloomfilter

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클래스 에서 속성을 래핑합니다 . 사용자 정의 getter가없고 setter가 없으므로 전체 클래스는 인스턴스화되면 다른 항목에 대한 참조없이 변경 불가능하고 압축됩니다.

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)

두 번째 형식은 형식을 표시하기 때문에 필요한 서명과 정확히 일치하는 함수가있을 때 일반적으로 람다보다 선호됩니다. 여기에서는별로 도움이되지 않지만 나중에 더 쉽게 읽을 수 있도록 일련의 기능 호출에 도움이됩니다.

주요 방법에서 몇 가지 작은 팁 ...

변수에 무언가를 할당 할 때 부작용없이 일종의 로깅 유형의 작업을 수행하려면 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가 0이면 0으로 나누기 문제가 발생할 수 있습니다.