Bloomfilter dans Kotlin
Je voudrais une revue de code. Pas tellement sur si l'implémentation est bonne ou efficace, ce n'est probablement pas le cas, plus sur le style de code et la lisibilité.
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()
}
Réponses
Voici comment je nettoierais la classe ConfusionMatrix. Je ne sais rien de cet algorithme, mais cela devrait être un code équivalent. Vous pouvez calculer et définir ces valeurs en lecture seule sur leurs sites de déclaration si vous les faites dans l'ordre. Ainsi, tous les paramètres peuvent être valet vous n'avez pas besoin lazyde , ce qui encapsule votre propriété dans une Lazyclasse. Il n'y a pas de getters personnalisés et il n'y a pas de setters, donc toute la classe est immuable et compacte sans référence à quoi que ce soit d'autre une fois qu'elle est instanciée.
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()
}
}
Ne connaissant rien à l'algorithme, je dirais que BloomFilter est assez propre, mais vous pourriez plus naturellement écrire la déclaration de saltscomme ceci :
private val salts = (0..numberOfHashes).map { it.toString() }
ou alors
private val salts = (0..numberOfHashes).map(Int::toString)
La deuxième forme est généralement préférée aux lambdas lorsqu'il existe une fonction qui correspond exactement à la signature requise car elle affiche le type. Pas vraiment utile ici, mais utile dans une chaîne d'appels fonctionnels pour le rendre plus lisible plus tard.
Dans votre méthode principale, quelques petites astuces...
Lorsque vous souhaitez effectuer une sorte d'action de journalisation sans effets secondaires lorsque vous affectez quelque chose à une variable, vous pouvez utiliser also. Cela l'atténue en quelque sorte pour quelqu'un qui lit votre code, surtout s'il s'agit d'une action qui prend quelques lignes de code. Ce n'est pas très utile ici puisque c'est si simple, mais cela pourrait être utile pour vous dans d'autres situations.
val confusionMatrix = ConfusionMatrix(filter, entriesInFilter, entriesNotInFilter)
also { it.printReport() }
Et il existe une fonction pour affirmer quelque chose et lancer une exception d'exécution en cas d'échec, afin que votre dernier bit puisse être nettoyé :
require(confusionMatrix.falseNegativeRate > 0.0) {
"This should not happen, if it does the implementation of the bloom filter is wrong."
}
Après avoir regardé un peu
hashedIndex fait beaucoup de choses. Il sale l'entrée, la hache, l'enveloppe et s'assure qu'elle s'adapte à la taille. Pourrait-il être divisé et plus clair ce qui se passe?
La matrice de confusion semble être une chose mathématique générale, pourquoi dépend-elle directement d'un BloomFilter et de ses données ? Essayez de trouver un moyen de les découpler afin que la matrice de confusion puisse être réutilisée à d'autres fins statistiques.
countTruePositiveAndFalseNegative et countFalsePositiveAndTrueNegative ressemble beaucoup à une répétition, la logique peut-elle être déplacée vers une seule implémentation ?
Aucune des classes n'implémente des interfaces ou des méthodes abstraites, donc leur utilisation nécessiterait une dépendance à l'implémentation concrète, rendant la dépendance inutilement difficile à tester et à modifier.
Il y a un problème possible de division par zéro si inFilterCount ou notInFilterCount est égal à zéro.