preface

  • Item: Consider Aggregating Elements to a map
  • Original address: blog.kotlin-academy.com/item……
  • Original article by Marcin Moskala
  • Introduction: Marcin Moskala is a god with at least 5K+ followers on Medium and 4K+ followers on Twitter, and is one of the authors of Effective Kotlin. “Effective Kotlin” summarizes the best practices and experiences of the Kotlin community, many cases from Google engineers, and reveals the magic behind the hidden Kotlin.

This article is a sequel to the [2.4K Start] Surrender Dagger Hug Koin article, which explains the consequences of over-using the Inline modifier, As well as the performance optimisations the Koin team is doing to fix the 1x version, this article will continue to learn how to improve Kotlin’s query speed.

Through this passage you will learn the following, which will be answered in the thinking section of the translator

  • How do I speed up Kotlin’s queries?
  • How do you choose between performance and code readability?
  • Kotlin memory leak stuff, eliminating expired object references?
  • How can I improve the readability of Kotlin code?
  • Kotlin algorithm: One Line of Code implementation of Yang Hui triangle?

This article covers a lot of important points, so please read on patiently with your own understanding. You should learn a lot of skills from it

The translation

It’s not uncommon for us to need to access large amounts of data multiple times, such as:

  • Cache: Data downloaded from a service and stored in local memory for faster access
  • Repository: Loads data from files
  • In-memory repository: Used for different types of memory tests

This data may represent some user, ID, configuration, and so on, and is usually returned to us as a list, which may be stored in memory in the same way:

class NetworkUserRepo(val userService: UserService): UserRepo { private var users: List<User>? = null override fun getUser(id: UserId): User? { if(users == null) { users = userService.getUsers() } return users? .firstOrNull { it.id == id } } } class ConfigurationsRepository( val configurations: List<Configuration> ) { fun getByName(name: String) = configurations .firstOrNull { it.name == name } } class InMemoryUserRepo: UserRepo { private val users: MutableList<User> = mutableListOf() override fun getUser(id: UserId): User? = users.firstOrNull { it.id == id } fun addUser(user: User) { user.add(user) } }Copy the code

This could be the best way to store these elements, pay attention to how we load the data on how to use, we use an identifier or name to access these elements (they are related to the unique value when we design a database), when n is equal to the list of size, look for the complexity of the elements in a list is O (n), more accurately, On average, it takes n / 2 comparisons to find an element. If it’s a large list, the search efficiency is extremely inefficient, A good way to solve this problem is to use maps instead of lists. Kotlin uses a hash Map by default, more specifically LinkedHashMap, The performance is much better when we use a Hash Map to look up elements. In fact, the size of the Hash Map used by the JVM is adjusted to the size of the map itself, and if hashCode is implemented correctly, looking up an element requires only one comparison.

This is InMemoryRepo using map instead of list

class InMemoryUserRepo: UserRepo {
   private val users: MutableMap<UserId, User> = mutableMapOf()
   override fun getUser(id: UserId): User? = users[id]
   
   fun addUser(user: User) {
      user.put(user.id, user)
   }
}
Copy the code

Most of the other operations, such as modifying or iterating the data (possibly using the collection methods filter, map, flatMap, sorted, sum, etc.) are similar for list and Map.

So how do we convert from list to map, or from map to list, using the associate method to do list to map, the most common method is associateBy, which builds a map where the values are the elements in the list, The key is provided through a lambda expression.

data class User(val id: Int, val name: String)
val users = listOf(User(1, "Michal"), User(2, "Marek"))
val byId = users.associateBy { it.id }
byId == mapOf(1 to User(1, "Michal"), 2 to User(2, "Marek")) 
val byName = users.associateBy { it.name }
byName == mapOf("Michal" to User(1, "Michal"), 
              "Marek" to User(2, "Marek"))
Copy the code

Note that the key in the map must be unique, otherwise elements with the same key value will be deleted, which is why we should associate by unique identifier (for keys that are not unique, we should use the groupBy method)

val users = listOf(User(1, "Michal"), User(2, "Michal"))
val byName = users.associateBy { it.name }
byName == mapOf("Michal" to User(2, "Michal"))
Copy the code

Converting from map to list uses the values method

val users = listOf(User(1, "Michal"), User(2, "Michal"))
val byId = users.associateBy { it.id }
users == byId.values
Copy the code

How to improve element access performance with Map in Repositories

class NetworkUserRepo(val userService: UserService): UserRepo { private var users: Map<UserId, User>? = null override fun getUser(id: UserId): User? { if(users == null) { users = userService.getUsers().associateBy { it.id } } return users? .get(id) } } class ConfigurationsRepository( configurations: List<Configuration> ) { val configurations: Map<String, Configuration> = configurations.associateBy { it.name } fun getByName(name: String) = configurations[name] }Copy the code

This technique is very important, but not for all cases, and is useful when we need to access large lists, which are very important in the background, where lists can be accessed many times per second, It doesn’t matter in the foreground (Android or iOS in this case) that users will only access Repository a few times at most. It is important to note that converting a List to a map takes time, and if you overuse it, it can have a negative impact on performance.

The translator think

Configurations tell us how to go from list to map or from map to List in three aspects: Network, InMemory, and Map should be used in large data sets that require multiple accesses in the background. Overuse can only negatively impact performance.

  • The list-to-map call takes a lambda expression using the associateBy method
val users = listOf(User(1, "Michal"), User(2, "Michal"))
val byName = users.associateBy { it.name }
byName == mapOf("Michal" to User(2, "Michal"))
Copy the code
  • Call the values method from map to list
val users = listOf(User(1, "Michal"), User(2, "Michal"))
val byId = users.associateBy { it.id }
users == byId.values
Copy the code

[2.4K Start] Drop Dagger hug Koin [2.4K Start] Drop Dagger hug Koin [2.4K Start] Drop Dagger hug Koin For those of you who have used this version, the Koin team’s solution uses HashMap to trade space for time, and finding a Definition’s time complexity becomes O(1), from improved access speed.

In fact we should be in your mind, keep in memory management consciousness, and in every time before optimization, modify the code, do not have to rush to write code, organize ideas first, in the mind over his own plan, we should find a compromise solution for project, should not only consider the memory and performance, but also consider the readability of the code. When we make an application, readability is more important in most cases. When we develop a library, performance and memory are often more important.

How do you choose between performance and code readability

If Java and Kotlin languages are used to brush LeetCode and implement the same algorithm using the same idea, in a normal Case, the difference between Kotlin and Java execution time is very small, and the gap between Kotlin and Java will become bigger and bigger when the amount of data is larger. Kotlin execution times are getting slower and slower, but why is Kotlin still the preferred language for Android development? Take a look at the quick sorting algorithm shown in My Favorite Examples of Functional Programming in Kotlin by Marcin Moskala.

We’ve shared this algorithm in previous articles, so let’s take a look at it.

fun <T : Comparable<T>> List<T>.quickSort(): List<T> = if(size < 2) this else { val pivot = first() val (smaller, Greater) = drop(1).partition {it <= pivot} smaller. QuickSort () + pivot + greater.quicksort ()} // use [2,5,1] -> [1,2,5] ListOf,5,1 (2). QuickSort () / /,2,5 [1]Copy the code

This is a very cool example of functional programming, and when you look at the algorithm at first glance, it’s very concise and very readable, and then when you look at the algorithm execution time, it’s not optimized for performance at all.

If you need to use a high-performance algorithm, you can use a Java library function. The Kotlin extension sorted() uses a Java library function. Functions in the Java library are much more efficient, but what about the actual execution time? Generate a random array of numbers, sort them using the quickSort() and sorted() methods, and compare their execution times as follows:

val r = Random() listOf(100_000, 1_000_000, 10_000_000) .asSequence() .map { (1.. it).map { r.nextInt(1000000000) } } .forEach { list: List<Int> -> println("Java stdlib sorting of ${list.size} elements took ${measureTimeMillis { list.sorted() }}") println("quickSort sorting of ${list.size} elements took ${measureTimeMillis { list.quickSort() }}") }Copy the code

The following information is displayed:

Java stdlib sorting of 100000 elements took 83
quickSort sorting of 100000 elements took 163
Java stdlib sorting of 1000000 elements took 558
quickSort sorting of 1000000 elements took 859
Java stdlib sorting of 10000000 elements took 6182
quickSort sorting of 10000000 elements took 12133`
Copy the code

As you can see, quickSort() is about twice as slow as the sorted() sorting algorithm, and the difference is usually between 0.1ms and 0.2ms under normal conditions, which is essentially negligible, but it’s cleaner and more readable. This explains that in some cases we can consider using a less optimized but more readable and concise function. Do you agree with the author?

Kotlin memory leaks all that stuff, eliminating expired object references

I’ve read a lot of articles about Kotlin’s brevity and efficiency, and Kotlin is very succinct. I’ll give some examples in the section “How to Make Kotlin Code More readable,” but there’s a cost to efficiency that’s often overlooked. This requires us to study the magic behind Kotlin syntactic sugar. When we are developing, we should choose appropriate syntactic sugar to avoid errors such as high-order functions with lnMBA expressions, not using Inline modifiers, compiling to anonymous inner classes, etc. [2.4K Start] Discard the performance penalty caused by the Dagger embrace Koin Inline modifier.

One of the most important rules of memory management is that unused objects should be freed

Article Effective Java in Kotlin, Item 7: Eliminate OBSOLETE Object References The author also lists some examples of Kotlin, for example, we need to use the mutableLazy attribute delegate, which works like lazy.

fun <T> mutableLazy(initializer: () -> T): ReadWriteProperty<Any? , T> = MutableLazy(initializer) private class MutableLazy<T>( val initializer: () -> T ) : ReadWriteProperty<Any? , T> { private var value: T? = null private var initialized = false override fun getValue( thisRef: Any? , property: KProperty<*> ): T { synchronized(this) { if (! initialized) { value = initializer() initialized = true } return value as T } } override fun setValue( thisRef: Any? , property: KProperty<*>, value: T ) { synchronized(this) { this.value = value initialized = true } } }Copy the code

How to use:

var game: Game? by mutableLazy { readGameFromSave() }

fun setUpActions() {
    startNewGameButton.setOnClickListener {
        game = makeNewGame()
        startGame()
    }
    resumeGameButton.setOnClickListener {
        startGame()
    }
}
Copy the code

Is mutableLazy implemented correctly? It has an error that lnMBA expression initializer was not deleted after use. This means that as long as a reference to a MutableLazy instance exists, it will be kept, even if it is no longer useful.

fun <T> mutableLazy(initializer: () -> T): ReadWriteProperty<Any? , T> = MutableLazy(initializer) private class MutableLazy<T>( var initializer: (() -> T)? ) : ReadWriteProperty<Any? , T> { private var value: T? = null override fun getValue( thisRef: Any? , property: KProperty<*> ): T { synchronized(this) { val initializer = initializer if (initializer ! = null) { value = initializer() this.initializer = null } return value as T } } override fun setValue( thisRef: Any? , property: KProperty<*>, value: T ) { synchronized(this) { this.value = value this.initializer = null } } }Copy the code

After using initializer, set it to NULL and it will be collected by GC. In particular, this optimization is important when a higher-order function is compiled as an anonymous class or if it is an unknown class (any or generic type). Let’s look at the code for the Kotlin stdlib class SynchronizedLazyImpl as shown below: kotlin-stdlib…… /kotlin/util/LazyJVM.kt

private class SynchronizedLazyImpl<out T>( initializer: () -> T, lock: Any? = null ) : Lazy<T>, Serializable { private var initializer: (() -> T)? = initializer private var _value: Any? = UNINITIALIZED_VALUE private val lock = lock ? : this override val value: T get() { val _v1 = _value if (_v1 ! == UNINITIALIZED_VALUE) { @Suppress("UNCHECKED_CAST") return _v1 as T } return synchronized(lock) { val _v2 = _value if (_v2 ! == UNINITIALIZED_VALUE) { @Suppress("UNCHECKED_CAST") (_v2 as T) } else { val typedValue = initializer!! () _value = typedValue initializer = null typedValue } } } ...... }Copy the code

Note that initializers are set to NULL and will be recycled by GC after use

How can I improve the readability of Kotlin code

As mentioned above, Kotlin is simple and readable, but AndroidStudio provides the convert Our Java Code to Kotlin plugin. Java-style Kotlin code is obviously ugly, so I would like to share a few cool examples of how to Improve the readability of Kotlin code. It uses Elvis expressions, run, with, and so on

Remove!!!!!

myList!! .lengthCopy the code

change to

myList? .lengthCopy the code

Empty check

if (callback ! = null) { callback!! .response() }Copy the code

change to

callback? .response()Copy the code

Using Elvis expressions

if (toolbar ! = null) { if (arguments ! = null) { toolbar!! .title = arguments!! .getString(TITLE) } else { toolbar!! .title = "" } }Copy the code

change to

toolbar? .title = arguments? .getString(TITLE) ? : ""Copy the code

Using the scope function

val intent = intentUtil.createIntent(activity!! .applicationContext) activity!! .startActivity(intent) dismiss()Copy the code

change to

activity? .run { val intent = intentUtil.createIntent(this) startActivity(intent) dismiss() }Copy the code

Ps: scope functions also include run, with, let, also and apply. What are the differences between them and how to use them correctly? The following article will introduce them in detail.

Use the takeIf if function

if (something ! = null && something == preference) { something.doThing()Copy the code

change to

something? .takeIf { it == preference }? .let { something.doThing() }Copy the code

Android TextUtil

if (TextUtils.isEmpty(someString)) {... } val joinedString = TextUtils.join(COMMA, separateList)Copy the code

change to

if (someString.isEmpty()) {... } val joinedString = separateList.joinToString(separator = COMMA)Copy the code

Java Util

val strList = Arrays.asList("someString")
Copy the code

change to

val strList = listOf("someString")
Copy the code

Empty and null

if (myList == null || myList.isEmpty()) {... }Copy the code

change to

if (myList.isNullOrEmpty() {... }Copy the code

Avoid repeated operations on objects

recyclerView.setLayoutManager(layoutManager)
recyclerView.setAdapter(adapter) 
recyclerView.setItemAnimator(animator)
Copy the code

change to

with(recyclerView) {
    setLayoutManager(layoutManager)         
    setAdapter(adapter)         
    setItemAnimator(animator)
}
Copy the code

Avoid list loops

for (str in stringList) {
    println(str)
}
Copy the code

change to

stringList.forEach { println(it) }
Copy the code

Avoid using mutable collections

val stringList: List<String> = mutableListOf()
for (other in otherList) {
    stringList.add(dosSomething(other))
}
Copy the code

change to

val stringList = otherList.map { dosSomething(it) }
Copy the code

Use when instead of if

if (requestCode == REQUEST_1) {            
    doThis()
} else if (requestCode == REQUEST_2) {
    doThat()
} else {
    doSomething()
}
Copy the code

change to

when (requestCode) { 
    REQUEST_1 -> doThis()
    REQUEST_1 -> doThat()
    else -> doSomething()
}
Copy the code

Use the const

companion object {        
    val EXTRA_STRING = "EXTRA_EMAIL"
    val EXTRA_NUMBER = 12345
}
Copy the code

change to

companion object {        
    const val EXTRA_STRING = "EXTRA_EMAIL"
    const val EXTRA_NUMBER = 12345
}
Copy the code

If you have a better example, please leave a comment

Kotlin algorithm: a line of code to achieve Yang Hui triangle

I want to share a cool algorithm to implement Yang Hui triangle with one line of code from The Twitter of Marcin Moskala

fun pascal() = generateSequence(listOf(1)) { prev -> listOf(1) + (1.. prev.lastIndex).map { prev[it - 1] + prev[it] } + listOf(1) } fun main() { pascal().take(10).forEach(::println) }Copy the code

Here’s a tip: Follow the official Twitter accounts of people you’re interested in, and they’re constantly sharing new technologies, new articles, etc.

Amway is a translator’s own navigation site

Based on Python + Material Design development of “for Internet people and Design of domestic and foreign famous station navigation”, collected popular websites at home and abroad, including news, sports, life, entertainment, Design, product, operation, front-end development, Android development and so on navigation website address

reference

  • Item: Consider aggregating elements to a map
  • Effective Java in Kotlin, item 7: Eliminate obsolete object references
  • Improve Java to Kotlin code review

conclusion

Committed to sharing a series of Android system source code, reverse analysis, algorithm, translation related articles, is currently translating a series of European and American selected articles, please continue to pay attention to, in addition to translation and thinking about each European and American article, if it is helpful to you, please help me a like, thank you!! Looking forward to growing up with you.

Plan to establish a most complete and latest AndroidX Jetpack related components of the actual combat project and related components of the principle of analysis articles, currently has included App Startup, Paging3, Hilt and so on, is gradually adding other Jetpack new members, the warehouse continues to update, Check it out: AndroidX-Jetpack-Practice, please give me a thumbs up if this repository is helpful to you, and I will continue to complete more project practices for new members of Jetpack.

algorithm

Since LeetCode has a large question bank, hundreds of questions can be selected for each category. Due to the limited energy of each person, it is impossible to brush all the questions. Therefore, I sorted the questions according to the classic types and the difficulty of the questions

  • Data structures: arrays, stacks, queues, strings, linked lists, trees…
  • Algorithms: Search algorithm, search algorithm, bit operation, sorting, mathematics,…

Each problem will be implemented in Java and Kotlin, and each problem has a solution idea. If you like algorithms and LeetCode like me, you can pay attention to my Solution of LeetCode problem on GitHub: Leetcode-Solutions-with-Java-And-Kotlin, come to learn together And look forward to growing with you

Android 10 source code series

Since Nuggets doesn’t have the ability to sort or sort articles, it’s easy to view them in a GitHub repository called Android10-Source-Analysis, where all articles are synced

  • How is APK generated
  • APK installation process
  • 0xA03 Android 10 source code analysis: APK loading process of resource loading
  • Android 10 source code: APK
  • Dialog loading and drawing process and use in Kotlin, DataBinding
  • WindowManager View binding and architecture
  • More and more

Android Apps

  • How to get video screenshots efficiently
  • How to package Kotlin + Android Databinding in your project
  • [Google engineers] just released a new Fragment feature, “New ways to transfer Data between Fragments” and source code analysis
  • [2.4K Start] Drop Dagger to Koin

Tool series

  • Shortcuts to AndroidStudio that few people know
  • Shortcuts to AndroidStudio that few people know
  • All you need to know about ADB commands
  • 10 minutes introduction to Shell scripting

The reverse series

  • Dynamically debug APP based on Smali file Android Studio
  • The Android Device Monitor tool cannot be found in Android Studio 3.2