Home > database >  Find first occurrence index value in efficent way in kotlin
Find first occurrence index value in efficent way in kotlin

Time:10-18

Hey i have nested list and i wanted find first occurrence index value.

data class ABC(
    val key: Int,
    val value: MutableList<XYZ?>
)

data class XYZ)
    val isRead: Boolean? = null,
    val id: String? = null
)

I added code which find XYZ object, but i need to find index. So how can i achieved in efficient way. How can i improve my code?

list?.flatMap { list ->
    list.value
}?.firstOrNull { it?.isRead == false }

CodePudding user response:

If you would like to stick to functional style then you can do it like this:

val result = list.asSequence()
    .flatMapIndexed { outer, abc ->
        abc.value.asSequence()
            .mapIndexed { inner, xyz -> Triple(outer, inner, xyz) }
    }
    .find { it.third?.isRead == false }

if (result != null) {
    val (outer, inner) = result
    println("Outer: $outer, inner: $inner")
}

For each ABC item we remember its index as outer and we map/transform a list of its XYZ items into a list of tuples: (outer, inner, xyz). Then flatMap merges all such lists (we have one list per ABC item) into a single, flat list of (outer, inner, xyz).

In other words, the whole flatMapIndexed() block changes this (pseudo-code):

[ABC([xyz1, xyz2]), ABC([xyz3, xyz4, xyz5])]

Into this:

[
    (0, 0, xyz1),
    (0, 1, xyz2),
    (1, 0, xyz3),
    (1, 1, xyz4),
    (1, 2, xyz5),
]

Then we use find() to search for a specific xyz item and we acquire outer and inner attached to it.

asSequence() in both places changes the way how it works internally. Sequences are lazy, meaning that they perform calculations only on demand and they try to work on a single item before going to another one. Without asSequence() we would first create a full list of all xyz items as in the example above. Then, if xyz2 would be the one we searched, that would mean we wasted time on processing xyz3, xyz4 and xyz5, because we are not interested in them.

With asSequence() we never really create this flat list, but rather perform all operations per-item. find() asks for next item to check, mapIndexed maps only a single item, flatMapIndexed also maps only this single item and if find() succeed, the rest of items are not processed.

In most cases using sequences here could greatly improve the performance. In some cases, like for example when lists are small, sequences may degrade the performance by adding an overhead. However, the difference is very small, so it is better to leave it as it is.

As we can see, functional style may be pretty complicated in cases like this. It may be a better idea to use imperative style and good old loops:

list.indicesOfFirstXyzOrNull { it?.isRead == false }

inline fun Iterable<ABC>.indicesOfFirstXyzOrNull(predicate: (XYZ?) -> Boolean): Pair<Int, Int>? {
    forEachIndexed { outer, abc ->
        abc.value.forEachIndexed { inner, xyz ->
            if (predicate(xyz)) {
                return outer to inner
            }
        }
    }

    return null
}

CodePudding user response:

In Kotlin, you can use the indexOf() function that returns the index of the first occurrence of the given element, or -1 if the array does not contain the element.

Example:

fun findIndex(arr: Array<Int>, item: Int): Int {
    return arr.indexOf(item)
}
  • Related