在Kotlin中获取两个列表的差异

1. Introduction

Lists in programming constitute an important data structure that can be used to solve a myriad of problems. The list is a data structure that most developers, if not all, have had to use at some point.

In this tutorial, we’ll focus on various ways we can get the difference between two lists in Kotlin.

2. Solutions to the Problem

Now, let’s dive straight into the various ways of getting the difference between two lists. Throughout this section, we’ll use the User data class for items for our lists:

data class User(val id: Int, val name: String)

2.1. Brute-Force Approach

The first method we’ll investigate is the brute-force approach. Although this method always gives us the longest running time for our program, it usually provides us with a starting point for optimization:

var list1 = listOf(User(1, "John"), User(2, "Fil"))
var list2 = listOf(User(1, "John"), User(3, "Nappy"), User(2, "Fil"))

var res = mutableListOf<User>()

for (user in list1) {
    if (!list2.contains(user))
        res.add(user)
}
for (user in list2) {
    if (!list1.contains(user))
        res.add(user)
}

assertContentEquals(listOf(User(id = 3, name = "Nappy")), res)

First, we iterate through the items in one list and check if that item exists in the other list. If it doesn’t, we add the item to our results. We’ll do the same thing while iterating over the second list, identifying items that don’t exist in the first list and adding them to our results.

2.2. Using groupBy()

Since User has an id, we can use Kotlin’s groupBy() function to create a map with the id as the key and the values as lists of Users having the same identifier. Next, we remove entries that have a size other than one. Finally, we use the flatMap() function to convert our lists into a single list of Users:

val sum = list1 + list2
var res =  sum.groupBy { it.id }
   .filter { it.value.size == 1 }
   .flatMap { it.value }
assertContentEquals(listOf(User(id=3, name="Nappy")), res)

2.3. Using the HashMap Method

In this method, we merge both lists into a variable sum and keep track of a HashMap with User as key and Int as value. We then iterate the merged list and increment the occurrence of each user in the HashMap by one:

val userOccurrences = HashMap<User, Int>()
val sum = list1 + list2
for (user in sum) {
    val numberOfOccurrences = userOccurrences[user]
    userOccurrences[user] = if(numberOfOccurrences == null) 1 else numberOfOccurrences + 1
}
var res = sum.filter { user -> userOccurrences[user] == 1 }
assertContentEquals(listOf(User(id=3, name="Nappy")), res)

This works because User is a data class that provides equals() and hashCode() implementations.

2.4. Using an Extension Function on Collections

We can create an extension function on a Collection that assumes how to identify a generic element specified by type T. It returns a Set:

infix fun <T> Collection<T>.symmetricDifference(other: Collection<T>): Set<T> {
    val left = this subtract other
    val right = other subtract this
    return left union right
}

Considering our example that comprises a list of Users, the extension function on the Collection class accepts another Collection object as an argument specified by other. Next, it subtracts both Collections from each other, so that we’re left with the unique items of each Collection.

The complete difference between the two collections can be calculated by performing a union of the two sets of unique items, as indicated by left and right variables in the code.

Finally, let’s test our extension function:

val res = list1 symmetricDifference list2
assertContentEquals(listOf(User(id=3, name="Nappy")), res)

2.5. Using Ids From List Items

We can leverage some Integer ids from both lists and find the ids common to both lists. Next, we merge both lists and filter the merged list based on the ids that are not common to both lists:

val list1Ids = list1.map { it.id }
val list2Ids = list2.map { it.id }
val commonIds = list1Ids.intersect(list2Ids)

val sum = list1 + list2
var res = sum.filter { it.id !in commonIds }

assertContentEquals(listOf(User(id=3, name="Nappy")), res)

3. Conclusion

In this article, we’ve explored different ways to get the difference between two lists in Kotlin. However, it’s important to mention that it is possible to have other methods or algorithms to solve this problem besides those discussed in this article.

As always, the code samples and relevant test cases pertaining to this article can be found over on GitHub.

Persistence

REST

Security