Ad

Use Of Find In Foreach In Kotlin

- 1 answer

Hey I am working in kotlin. I make a solution for my work. But I am little bit confused that about my approach is efficient or not. I am thinking is that my approach is for speed, memory and proper optimize solution or not? Can someone guide me

val listOne = listOf<Int>(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
val listTwo = listOf(4, 7, 9, 10, 12, 15, 18)
fun main() {
    val secondList = mutableListOf<Second>()
    listOne.forEachIndexed { index, value ->
        val present = listTwo.find {
            value == it
        }
        secondList.add(
            Second(
                index,
                present != null
            )
        )
    }

    secondList.forEach { println(it) }
}

data class Second(
    val value: Int,
    val present: Boolean = false
)

I have two list listOne, listTwo. listOne is main list I want to find the value of present in listTwo and add into new secondList. Is there any better approach for this?

Ad

Answer

No, this code is not optimal for the performence. But the fix is actually very easy - just change the type of the data structure you use.

The problem is that lists are not optimized for searching. For each item from listOne we have to iterate over elements in listTwo. As a result, the time complexity is O(N*M) where N and M are sizes of listOne and listTwo accordingly. We can replace/convert listTwo with a set. Sets are good for searching, they search in constant time, so the resulting time complexity is just O(N+M). M for preparing a set and N for iterating over listOne and searching.

Additionally, your code can be greatly simplified by using mapIndexed() and replacing find() with simple in:

val s = listTwo.toSet()
val secondList = listOne.mapIndexed { index, item ->
    Second(index, item in s)
}

You can also create a set directly, using setOf() instead of listOf().

Ad
source: stackoverflow.com
Ad