Filtro Bloom a Kotlin
Vorrei una revisione del codice. Non tanto sul fatto che l'implementazione sia buona o efficiente, probabilmente non lo è, più sullo stile del codice e sulla leggibilità.
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()
}
Risposte
Ecco come pulirei la classe ConfusionMatrix. Non so nulla di questo algoritmo, ma questo dovrebbe essere un codice equivalente. È possibile calcolare e impostare questi valori di sola lettura nei relativi siti di dichiarazione se li si esegue in ordine. Quindi tutti i parametri possono essere vale non ti servono lazy, il che racchiude la tua proprietà in una Lazyclasse. Non ci sono getter personalizzati e non ci sono setter, quindi l'intera classe è immutabile e compatta senza riferimenti a nient'altro una volta istanziata.
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()
}
}
Non sapendo nulla dell'algoritmo, direi che BloomFilter è abbastanza pulito, ma potresti scrivere in modo più naturale la dichiarazione in saltsquesto modo:
private val salts = (0..numberOfHashes).map { it.toString() }
o
private val salts = (0..numberOfHashes).map(Int::toString)
La seconda forma è solitamente preferita a lambda quando c'è una funzione che corrisponde esattamente alla firma richiesta perché mostra il tipo. Non molto utile qui, ma utile in una catena di chiamate funzionali per renderlo più leggibile in seguito.
Nel tuo metodo principale, un paio di piccoli consigli...
Quando vuoi eseguire una sorta di tipo di azione di registrazione senza effetti collaterali mentre assegni qualcosa a una variabile, puoi usare also. In un certo senso lo de-enfatizza per qualcuno che legge il tuo codice, specialmente se si tratta di un'azione che richiede poche righe di codice. Non è poi così utile qui poiché è così semplice, ma potrebbe esserti utile in altre situazioni.
val confusionMatrix = ConfusionMatrix(filter, entriesInFilter, entriesNotInFilter)
also { it.printReport() }
E c'è una funzione per affermare qualcosa e lanciare un'eccezione di runtime se fallisce, quindi il tuo ultimo bit può essere ripulito:
require(confusionMatrix.falseNegativeRate > 0.0) {
"This should not happen, if it does the implementation of the bloom filter is wrong."
}
Dopo averlo guardato un po'
hashIndex fa molte cose. Sala l'input, lo hash, lo avvolge e si assicura che si adatti alle dimensioni. Potrebbe essere diviso e più chiaro cosa sta succedendo?
La matrice di confusione sembra una cosa matematica generale, perché ha una dipendenza diretta da un BloomFilter e dai suoi dati? Prova a trovare un modo per disaccoppiarli in modo che la matrice di confusione possa essere riutilizzata per altri scopi statistici.
countTruePositiveAndFalseNegative e countFalsePositiveAndTrueNegative assomiglia molto alla ripetizione, la logica può essere spostata in una singola implementazione?
Nessuna delle classi implementa interfacce o metodi astratti, quindi utilizzarli richiederebbe una dipendenza dall'implementazione concreta, rendendo la dipendenza inutilmente difficile da testare e modificare.
Esiste un possibile problema di divisione per zero se inFilterCount o notInFilterCount è zero.