Kotlinのブルームフィルター
Aug 23 2020
コードレビューをお願いします。実装が優れているか効率的であるかについてはそれほど重要ではありませんが、コードスタイルと読みやすさについてはおそらくそうではありません。
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()
}
回答
2 Tenfour04 Aug 28 2020 at 03:04
これが、ConfusionMatrixクラスをクリーンアップする方法です。このアルゴリズムについては何も知りませんが、これは同等のコードである必要があります。これらの読み取り専用値は、順番に実行すれば、宣言サイトで計算して設定できます。したがって、すべてのパラメータを指定できますが、プロパティをクラスにラップするval必要lazyはありませんLazy。カスタムゲッターやセッターがないため、クラス全体が不変でコンパクトであり、インスタンス化されると他のものへの参照はありません。
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)
2番目の形式は、タイプを示すため、必要なシグネチャに完全に一致する関数がある場合、通常、ラムダよりも優先されます。ここではあまり役に立ちませんが、後で読みやすくするための一連の機能呼び出しには役立ちます。
あなたの主な方法では、いくつかの小さなヒント...
変数に何かを割り当てているときに、副作用なしにある種のロギングタイプのアクションを実行したい場合は、を使用できます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."
}
Peheje Aug 23 2020 at 23:32
少し見てから
hashedIndexは多くのことを行います。入力をソルトし、ハッシュし、ラップして、サイズに収まるようにします。それを分割して、何が起こっているのかをより明確にすることができますか？
混同行列は一般的なマシーなもののように見えますが、なぜブルームフィルターとそのデータに直接依存しているのですか？混同行列を他の統計目的で再利用できるように、これらを分離する方法を考え出すようにしてください。
countTruePositiveAndFalseNegativeとcountFalsePositiveAndTrueNegativeは繰り返しによく似ていますが、ロジックを単一の実装に移動できますか？
どのクラスもインターフェースや抽象メソッドを実装していないため、それらを使用するには具体的な実装への依存関係が必要になり、依存関係のテストと変更が不必要に困難になります。
inFilterCountまたはnotInFilterCountがゼロの場合、ゼロ除算の問題が発生する可能性があります。