Tengo un mapa inicializado como
val cache: SortedMap<String, String> = sortedMapOf()El mapa se usa como caché y puede contener valores duplicados con su propia clave única. Quiero verificar y contar cuántos valores duplicados hay en el caché. Tenga en cuenta que la memoria caché puede contener millones de entradas.
A partir de ahora, busco duplicados de esta manera
val uniqueValueSet = hashSetOf<String>() val numDuplicates = cache.filter {!uniqueValueSet.add(it.value)}.count()Sin embargo, siento que esta verificación es ineficiente para la memoria, donde agregar todos los valores distintos a un conjunto crea un conjunto obsoleto con posiblemente millones de elementos.
¿Existe una forma mejor y más optimizada de comprobar los duplicados entre los valores de un mapa?
Si solo está interesado en la cantidad de duplicados, puede hacer lo siguiente:
val numOfDuplicates = cache.size - cache.values.toHashSet().sizeTodavía creará un conjunto con todos los valores distintos, pero será la única sobrecarga.
Otra opción es cambiar la complejidad del espacio (O(N) -> O(M), donde N - tamaño de la cache , M - cantidad de duplicados únicos; tiene sentido si M << N) a la complejidad del tiempo (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 }Este debería ser el más rápido (inspirado en la solución de Михаил Нафталь):
val numDuplicates = cache.size - cache.values.distinct().sizeEdición 1: hice algunas pruebas y hasta 50.000 entradas (clave y valor cada cadena aleatoria de 10 caracteres alfanuméricos), esto es realmente más rápido. Por encima de aproximadamente 50.000 entradas, la solución de Михаил Нафталь se vuelve drásticamente más rápida:
val numOfDuplicates = cache.size - cache.values.toHashSet().sizeEdición 2: se agregaron algunas pruebas simples:
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")