我有一個地圖初始化為
val cache: SortedMap<String, String> = sortedMapOf()
地圖用作快取，可以包含具有自己唯一鍵的重復值。我想檢查并計算快取中有多少重復值。請注意，快取可以包含數百萬個條目。
截至目前，我以這種方式檢查重復項
val uniqueValueSet = hashSetOf<String>()
val numDuplicates = cache.filter {!uniqueValueSet.add(it.value)}.count()
但是，我覺得這種檢查記憶體效率低下，將所有不同的值添加到集合中會創建一個可能包含數百萬個元素的過時集合。
是否有更好、更優化的方法來檢查地圖中值之間的重復項？
uj5u.com熱心網友回復：
如果你只對重復的數量感興趣，你可以這樣做：
val numOfDuplicates = cache.size - cache.values.toHashSet().size
它仍然會創建一個具有所有不同值的集合，但這將是唯一的開銷。
另一種選擇是交換空間復雜度 (O(N) -> O(M)，其中 N - 大小cache，M - 唯一重復項的數量；如果 M << N) 到時間復雜度 (O(N*logN) -> O(N^2))：
var numOfDuplicates = 0
val duplicates = hashSetOf<String>()
for (value in cache.values) {
if (value in duplicates) {
numOfDuplicates
} else if (cache.values.atLeastTwo { it == value }) {
duplicates.add(value)
}
}
public inline fun <T> Iterable<T>.atLeastTwo(predicate: (T) -> Boolean): Boolean {
var atLeastOne = false
for (it in this) {
if (predicate(it)) {
if (!atLeastOne) {
atLeastOne = true
} else {
return true
}
}
}
return false
}
uj5u.com熱心網友回復：
這應該是最快的（受 Михаил Нафталь 的解決方案啟發）：
val numDuplicates = cache.size - cache.values.distinct().size
編輯 1：我做了一些測驗和多達 50.000 個條目（鍵和值每個 10 個字母數字字符的隨機字串）這確實更快。超過大約 50.000 個條目 Михаил Нафталь 的解決方案變得非常快：
val numOfDuplicates = cache.size - cache.values.toHashSet().size
編輯 2：添加了一些簡單的測驗：
val count_of_entries = 1_000_000
val lengthOfRandomKey = 10
val lengthOfRandomValue = 10
fun randomString(length: Int): String {
val charPool: List<Char> = ('a'..'z') ('A'..'Z') ('0'..'9')
return (1..length).map { _ -> kotlin.random.Random.nextInt(0, charPool.size) }.map(charPool::get)
.joinToString("")
}
val cache: java.util.SortedMap<String, String> = sortedMapOf()
repeat (count_of_entries) { cache[randomString(lengthOfRandomKey)] = randomString(lengthOfRandomValue) }
val uniqueValueSet = hashSetOf<String>()
val start1 = System.nanoTime()
val numDuplicates1 = cache.filter { !uniqueValueSet.add(it.value) }.count()
val end1 = System.nanoTime()
println("$numDuplicates1 duplicates, time ${(end1 - start1).toDouble() / 1_000_000_000} s")
val start2 = System.nanoTime()
val numDuplicates2 = cache.size - cache.values.toHashSet().size
val end2 = System.nanoTime()
println("$numDuplicates2 duplicates, time ${(end2 - start2).toDouble() / 1_000_000_000} s")
val start3 = System.nanoTime()
val numDuplicates3 = cache.size - cache.values.distinct().size
val end3 = System.nanoTime()
println("$numDuplicates3 duplicates, time ${(end3 - start3).toDouble() / 1_000_000_000} s")
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/345178.html
上一篇：kotlin.UninitializedPropertyAccessException：lateinit屬性layoutManager尚未初始化