0%

一、使用

1.1 定义API方法
1
2
3
4
interface RemoteApi {
@GET("timeline")
suspend fun timeline(): RemoteLaunchesResponse
}
1.2 获取服务
1
2
3
4
5
6
7
8
9
10
11
val client = OkHttpClient.Builder()
.addInterceptor(loggingInterceptor)
.build()

val retrofit = Retrofit.Builder()
.client(client)
.baseUrl("http://10.0.0.2:8080/")
.addConverterFactory(GsonConverterFactory.create())
.build()

val api = retrofit.create(RemoteApi::class.java) //1、create做了什么?
1.3 发起请求
1
api.timeline() //2、调用接口方法怎么发起请求?

二、原理

2.1 create做了什么

Retrofit的网络请求方法都是定义在接口中的,它会在运行时利用Java的动态代理产生代理对象,所以create()就是创建代理对象的方法。

2.2 调用接口方法怎么发起请求

当调用接口方法时,实际上是调用了代理对象的方法。它会去Retrofit中找该方法对应的ServiceMethod,如果找到缓存直接使用,否则解析后再使用。

解析的结果是ServiceMethod的子类CallAdaptedSuspendForResponseSuspendForBody三者之一。

解析结束后调用返回对象的invoke方法初始化OkHttpCall对象发起真正的请求。

三、总结

阅读源码的过程当中,画了详细的代码执行流程图供后续回顾。另外源码中还有两个重要的对外拓展接口CallAdapterConverter没有详细分析。

一、概述

此文是对Github开源项目SpaceX-prepare-for-Clean-Architecture-liftoff 的源码阅读记录。它是一个为了阐述对Clean Architecture的理解而作的Demo项目,是一个值得学习的项目。

二、源码分析

2.1 模块之间的依赖关系

项目包含以下library:

  • app
  • buildSrc
  • core
  • core-android-test
  • data
  • data-api
  • domain
  • navigation
  • presentation

模块之间的依赖关系可用下图简述:

2.2 类和模块之间的关系

三、总结

项目重在阐述架构思想所以比较简单,其中很多东西值得我们在项目中借鉴。数据层的架构模式参看martin fowler 的文章。

简介:

本文是 Roman Elizarov 关于CSP中产生死锁问题的讨论,解释了其中的原因,并逐步给出了一种解决方案。部分翻译不恰当的可参考原文

原文:

众所周知,使用锁保护共享可变状态可能会导致死锁,但很少有人知道,使用无共享可变状态的CSP或actor模型也会导致死锁,尽管它们并不使用锁。它的死锁以另一种方式表现:通信死锁。

要知道,死锁的正式定义并没有直接与锁联系在一起。当每个进程都在循环等待下一个进程时,这组进程(线程/协程/参与者)就处于死锁状态。后面我们会看个例子,这里先道个歉,之前没强调这个问题。

The stage

在2018年的KotlinConf我发表了题为”Kotlin协程实践”的演讲,其中讲到了对于构建可信赖软件来说结构性并发是重要的,且介绍了CSP的一些高级概念。其中一个部分有点问题。如果你按照演讲中一字不差的写完代码会导致一个死锁。不知何故,我掉进了这个陷阱,以为它对我来说是安全的,但不是。让我们来分析一下

首先来讲,如果应用被组织成数据处理管道,消息进入系统,被不同的协程顺序处理,最后被送出系统,那么这种CSP风格的架构,包括actor模式,都是安全的。更广泛地说,只要代码具有协程的层次结构(或有向无环图),上游协程只向下游发送消息,且每个协程在同一个地方接收传过来的消息并向下游传递响应消息,代码就不会出现死锁。

然而在我的演讲中,我草拟了一个数据处理循环的架构,下载器协程向任务池发送locations,并从任务池获取结果:

我演讲中的例子的架构基于3个channel:referenceslocationscontents。下载协程包含以下逻辑:

1
2
3
4
5
6
7
8
9
10
while (true) {
select<Unit> {
references.onReceive { ref -> // (1)
val loc = ref.resolveLocation()
...
locations.send(loc) // (2)
}
contents.onReceive { (loc, content) -> ... } // (3)
}
}

Downloader从references通道(1)接收,解析对位置的引用并将它们发送到locations通道(2)。它还通过从contents通道(3)接收来自workers的结果来更新其状态。另外,works有以下代码:

1
2
3
4
for (loc in locations) {                             // (4)
val content = downloadContent(loc)
contents.send(LocContent(loc, content)) // (5)
}

locations通道接收消息(4),并发送下载后的内容去contents通道(5)

即使在两段通信的代码中也很难遵循逻辑,但在CSP中有一种方便的方法来可视化它。我们可以用通信有限状态机(CFSM)表示我们的系统。这些状态相当于挂起点和向通信的转变过程:

为了简洁起见,上图中通道名简写。receive -> rcv、send -> snd 。下载器主循环中的select语句相当于D0状态,它能接收来自references通道的消息(1)或者来自contents通道的消息(3),当接收到来自references消息,切换到状态D1,等待发送消息去locations通道,如图中:(2)l.snd

Deadlock Demo

我用模拟数据类的方式完善了演讲中的代码,加入了delay(10)downloadContent方法。main函数则持续发送请求给下载器的references通道,它有4个workers且带3秒超时限制。此项目可以完整的运行,正常情况下3s应该处理1000次请求。

当你运行该项目时,你会发现只处理了4次请求(和我们定义的worker数量一样)就挂起了,直到3s超时。此外,它没有任何随机性,因为它是在单线程的runBlocking上下文中运行的。

为了说服你(还有我自己),这是CSP内在的行为而不是Kotlin实现的bug,我用Go语言实现了一遍。Go语言内建的死锁检测器立即给出了提示:all goroutines are asleep — deadlock ,到底发生了什么呢?

开始时所有的worker完成初始化处于W1状态,然后尝试发送回复下载器的消息去contents通道(5),但它是一个对接通道,下载器不能立马收到。下载器处于D1正尝试发送消息去locations通道(2),但由于worker都在尝试发送所以无法接收。死锁发生了,所有的协程都在等待。

Solutions that do not work

问题好像出在select表达式。修复它很简单。相对于由下载器通过select处理来自referencescontents的消息,我们可以使用actor模型作为协程重写下载器,它有独立的mailbox通道来处理发送过来的消息。

1
2
3
4
5
6
for (msg in mailbox) {
when (msg) {
is Reference -> ...
is LocContent -> ...
}
}

然而,actor模型也不能避免死锁,这种方式和原来一样代码很快被挂起。他们的通讯状态机是相同的。

另一个可能被指责的是集合信道——没有缓冲区的信道,因为它们在另一端没有接收器的情况下会暂停发送。即使我们给contentslocations添加buffer也不能解决此问题,只是减少了问题出现的概率或延迟出现。buffer越大出现的概率越低,但无法完全避免死锁的发生,一旦buffer满了发送器还是会挂起并发生死锁。

Unlimited-capacity channels

一种明确的避免死锁的解决方案是对被通讯死锁影响的channel中的至少一个使用不限大小的buffer,这里 的代码对contents通道使用了无限制buffer,似乎能正常工作。

然而,通过取消通道缓冲区的限制,我们丧失了CPS编程风格的利润丰厚的属性-自动背压传播.如果来自通道的消息的接收方比发送方慢,则发送方将挂起在全缓冲区上以自动减慢速度。有了无限容量的通道,就不会发生这种情况,管理背压的任务完全由应用程序开发人员承担。如果不能管理背压,系统最终可能会耗尽内存,在其缓冲区中收集越来越多的消息。

在我们的例子中,把locations通道设置成无限buffer会完全移除对传入引用的背压管理,因为即使所有的worker都处于忙碌状态,下载器也将发送所有的消息去locations通道。
把contents通道设置成无限buffer会更安全,因为它只影响下载内容的最终处理。然而,在无限容量的情况下,我们面临的风险是,下载器会被传入的references淹没,永远无法处理下载的内容。这使我们离最终解决方案更近一步。

Solutions that do work

我们调整一下下载器协程中select表达式的顺序,以便先检查contents通道,也就是说contents通道的消息优先级高于references通道:

1
2
3
4
5
6
7
8
select<Unit> {
contents.onReceive { ... }
references.onReceive {
...
locations.send(loc) // (2)
}
}

它本身并没有解决这个问题(你可以在这里验证代码),但它给了一个有用的属性——
下载器只有在没有worker被挂起且worker准备发送消息去contents通道时,才发送消息去locations通道(2)。现在,提供至少一个buffer给contents通道就足够了,以确保至少有一个worker可以在(5)发送其内容,并在(4)再次开始从locations接收,从而允许下载程序继续进行:

1
val contents = Channel<LocContent>(1)

这里 是能运行的代码。

注意,它是如何在3秒内处理比之前的无限渠道“解决方案”更多的下载的。此外,由于contents通道处理具有最高优先级,现在可以安全地拥有无限容量的contents通道。它在缓冲区中保存的消息永远不会超过工作人员的数量加1(为什么是加1 ?这是留给读者的练习)。

还有一种替代解决方案,它完全不使用缓冲通道,可以完美地与任何容量的通道一起工作。它加倍select,以避免在locations.send(loc)上挂起下载程序,将这个发送操作折叠为一个select。它实际上是CFSM模型中表示和分析的最简单的一个,但是我现在不会详细介绍它,把它留给将来的故事。你可以看一下这里 对应的代码并在playground中运行它。

总结

通信循环(非DAG模式)可能并将导致通道容量有限的通信死锁,除非使用一些死锁预防策略。如果在应用程序中遇到死锁,在了解发生了什么之前,不要尝试使用缓冲通道解决它,否则可能会把问题掩盖起来。

请在本文的评论中分享更多解决这种特殊通信循环死锁的有效解决方案。Kotlin和其他CSP/actor运行时中的代码都是受欢迎的(请提供链接,不要将代码粘贴到评论中)。

Credits

我要感谢Alexey Semin,他通过这个 github-issue报告了这个问题,并感谢Alexander Gorynin在Kotlin Slack里联系了我。还要感谢Simon Wirtz和Sean McQuillan对本文草稿的有用评论。

一、概述:

利用Kotlin的语言特性可以创建可配置的领域语言-DSL(Domain Specific Language)。这种DSL用于表示复杂对象和对象继承结构很有用,它能隐藏模板代码和复杂性,让使用者更好的表达自己的意图。

例如,用Kotlin DSL的方式表示HTML的结构:

1
2
3
4
5
6
7
8
9
body {
div {
a("https://kotlinlang.org") {
target = ATarget.blank
+"Main site"
}
}
+"Some content"
}

其他平台的视图也可以使用DSL来定义。下面是Android上使用Anko库定义的界面:

1
2
3
4
5
6
verticalLayout {
val name = editText()
button("Say Hello") {
onClick { toast("Hello, ${name.text}!") }
}
}

同样的,使用TornadorFX库定义的桌面应用如下:

1
2
3
4
5
6
7
8
9
10
11
class HelloWorld : View() {
override val root = hbox {
label("Hello world") {
addClass(heading)
}

textfield {
promptText = "Enter your name"
}
}
}

DSL通常也被用于定义数据和配置。下面是Ktor定义的API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun Routing.api() {
route("news") {
get {
val newsData = NewsUseCase.getAcceptedNews()
call.respond(newsData)
}
get("propositions") {
requireSecret()
val newsData = NewsUseCase.getPropositions()
call.respond(newsData)
}
}
// ...
}

这是在Kotlin Test中定义的测试用例:

1
2
3
4
5
6
7
8
class MyTests : StringSpec({
"length should return size of string" {
"hello".length shouldBe 5
}
"startsWith should test for a prefix" {
"world" should startWith("wor")
}
})

我们甚至可以使用Gradle DSL定义Gradle配置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
plugins {
`java-library`
}

dependencies {
api("junit:junit:4.12")
implementation("junit:junit:4.12")
testImplementation("junit:junit:4.12")
}

configurations {
implementation {
resolutionStrategy.failOnVersionConflict()
}
}

sourceSets {
main {
java.srcDir("src/core/java")
}
}

java {
sourceCompatibility = JavaVersion.VERSION_11
targetCompatibility = JavaVersion.VERSION_11
}

tasks {
test {
testLogging.showExceptions = true
}
}

使用DSL简化了层次结构和复杂对象的创建。在DSL构建块中,你可以使用Kotlin语法和代码提示。也许你用过Kotlin DSL,但你更应该学会如何定义它。

二、定义自己的DSL

在理解如何定义DSL前,先明白带接收者的函数类型。首先什么是函数类型呢?它是一个能被当成函数使用的对象。例如:filter函数,参数predicate决定集合是否包含此元素。

1
2
3
4
5
6
7
8
9
10
11
inline fun <T> Iterable<T>.filter(
predicate: (T) -> Boolean
): List<T> {
val list = arrayListOf<T>()
for (elem in this) {
if (predicate(elem)) {
list.add(elem)
}
}
return list
}

函数类型的例子:

  • ()->Unit - 无参函数,返回Unit
  • (Int)->Unit - 单参Int函数,返回Unit
  • (Int)->Int - 单参Int函数,返回Int
  • (Int, Int)->Int - 双参Int函数,返回Int。
  • (Int)->()->Unit - 单参Int函数,返回无参函数。
  • (()->Unit)->Unit - 参数为函数的函数,返回Unit

创建函数类型实例的方式有:

  • 使用lambda表达式
  • 使用匿名函数
  • 使用函数引用

例如,下面的函数

1
fun plus(a: Int, b: Int) = a + b

同样可以声明成这样:

1
2
3
val plus1: (Int, Int) -> Int = { a, b -> a + b }
val plus2: (Int, Int) -> Int = fun(a, b) = a + b
val plus3: (Int, Int) -> Int = ::plus

上面的例子中,由于指明了属性的类型,所以lambda和匿名函数中的参数能被推导出来。换一种方式说:如果指定参数类型,函数类型可以被推导。

1
2
val plus4 = { a: Int, b: Int -> a + b }
val plus5 = fun(a: Int, b: Int) = a + b

函数类型以对象来表达函数,匿名函数也是一个普通函数只是没名字而已。lambda则是匿名函数的简短书写方式。

我们可以使用函数类型去表示函数,那拓展函数呢?

1
fun Int.myPlus(other: Int) = this + other

之前提到匿名函数只是没名字而已,匿名拓展函数也一样:

1
fun Int.myPlus(other: Int) = this + other

那此函数的类型是什么呢?一种表示拓展函数的特殊类型,叫:带接收者的函数类型。它看起来和普通函数很像,只是在参数之前额外的指定了接收者的类型,他们之间用一个点分割开来。

1
2
val myPlus: Int.(Int) -> Int =
fun Int.(other: Int) = this + other

这种函数能通过lambda表达式定义,尤其是一个带接收者的lambda表达式,因为作用域内部的this关键字引用了拓展接收者。(此例中是一个Int类型的实例):

1
val myPlus: Int.(Int)->Int = { this + it }

用匿名拓展函数或带接收者的lambda表达式创建的对象能被三种方式调用:

  • 像对象一样使用invoke方法调用
  • 像非拓展函数一样
  • 和普通的拓展函数一样
1
2
3
myPlus.invoke(1, 2)
myPlus(1, 2)
1.myPlus(2)

带接收者的函数类型最大的特点是,它改变了this的指向。这种特点如何使用呢?假设一个类需要依次设置属性:

1
2
3
4
5
6
7
8
9
10
11
12
class Dialog {
var title: String = ""
var text: String = ""
fun show() { /*...*/ }
}

fun main() {
val dialog = Dialog()
dialog.title = "My dialog"
dialog.text = "Some text"
dialog.show()
}

重复引用此dialog很不方便,如果我们使用带接收者的lambda,this就指向dialog,我们可以省略this,因为接收者能够隐式调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Dialog {
var title: String = ""
var text: String = ""
fun show() { /*...*/ }
}

fun main() {
val dialog = Dialog()
val init: Dialog.() -> Unit = {
title = "My dialog"
text = "Some text"
}
init.invoke(dialog)
dialog.show()
}

按照这个思路,你可以定义一个包含创建此dialog对象所需的所有公共部分的逻辑,只把需要变化的属性的设置给调用者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Dialog {
var title: String = ""
var text: String = ""
fun show() { /*...*/ }
}

fun showDialog(init: Dialog.() -> Unit) {
val dialog = Dialog()
init.invoke(dialog)
dialog.show()
}

fun main() {
showDialog {
title = "My dialog"
text = "Some text"
}
}

这就是最简单的DSL例子。因为大部分这些构建函数都是重复的,已经被抽取到一个apply函数内,能被直接使用,不用再定义DSL构建器去设置属性了。

1
2
3
4
5
6
7
8
9
inline fun <T> T.apply(block: T.() -> Unit): T {
this.block()
return this
}

Dialog().apply {
title = "My dialog"
text = "Some text"
}.show()

对于DSL来说,带接收者的函数类型是最基本的构建块。我们一起来写一个简单的DSL用于创建下面的HTML表格:

1
2
3
4
5
6
7
8
9
fun createTable(): TableBuilder = table {
tr {
for (i in 1..2) {
td {
+"This is column $i"
}
}
}
}

在DSL开头我们定义了table函数。由于是最外层定义,所以它没用接收者。在table的内部可以使用tr,所以tr函数只能用于table内部。同理,td只能用于tr内部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fun table(init: TableBuilder.()->Unit): TableBuilder {
//...
}

class TableBuilder {
fun tr(init: TrBuilder.() -> Unit) { /*...*/ }
}

class TrBuilder {
fun td(init: TdBuilder.()->Unit) { /*...*/ }
}

class TdBuilder {
var text = ""

operator fun String.unaryPlus() {
text += this
}
}

现在,我们定义好了DSL。为了让它运行,每一步我们都需要创建一个builder并用参数里面的函数初始化它(下面例子中的init)。builder将包含所有init函数指定的数据。这些数据是我们需要的。我们可以直接返回这个构建器也可以返回另一个包含这些数据的新对象。此例中我们直接返回构建器。下面是table函数的定义:

1
2
3
4
5
fun table(init: TableBuilder.()->Unit): TableBuilder {
val tableBuilder = TableBuilder()
init.invoke(tableBuilder)
return tableBuilder
}

我们可以使用apply函数简化函数:

1
2
fun table(init: TableBuilder.()->Unit) =
TableBuilder().apply(init)

其他函数也使用apply简化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TableBuilder {
var trs = listOf<TrBuilder>()

fun tr(init: TrBuilder.()->Unit) {
trs = trs + TrBuilder().apply(init)
}
}

class TrBuilder {
var tds = listOf<TdBuilder>()

fun td(init: TdBuilder.()->Unit) {
tds = tds + TdBuilder().apply(init)
}
}

三、何时使用?

DSL给了我们一种定义信息的方式。它能用于表达你所想表达的东西。但是对于用户而言这些信息之后如何使用不是很清晰。在Anko、TornadoFX或HTML DSL中,我们相信视图会根据我们的定义形式被构建,但很难跟踪准确跟踪如何构建。一些复杂的使用方式很难发现。用法也会让那些不习惯的人感到困惑。更不用说维护了。它们的定义方式可能是一种成本——在开发人员困惑和性能方面都是如此。当我们可以使用其他更简单的特性时,dsl就太过了。虽然当我们需要表达下面的内容时,它们真的很有用:

  • 复杂的数据结构
  • 继承结构
  • 大量数据

描述事物不止DSL方式,还可以用builder、或只用构造器代替。dsl是关于此类结构的模板代码消除。当您看到可重复的样板代码,并且没有更简单的Kotlin特性可以提供帮助时,您应该考虑使用DSL。

四、总结:

DSL是语言中的一种特殊形式。它可以非常简单地创建复杂的对象,甚至整个对象层次结构,如HTML代码或复杂的配置文件。另一方面,DSL实现可能会让新开发人员感到困惑或困难。它们也很难定义。这就是为什么只有当它们提供真正的价值时才应该使用它们的原因。例如,用于创建一个真正复杂的对象,或者可能用于复杂的对象层次结构。这就是为什么最好在库中而不是在项目中定义它们的原因。制作一个好的DSL并不容易,但是一个定义良好的DSL可以让我们的项目做得更好。

参考:
Effective Kotlin Item 35: Consider defining a DSL for complex object creation

与不可变集合相比,使用可变集合最大的优点是性能更快。向不可变集合添加元素需要新建集合再拷贝所有元素,下面是kotlin标准库现在的实现:

1
2
3
4
5
6
7
operator fun <T> Iterable<T>.plus(element: T): List<T> {
if (this is Collection) return this.plus(element)
val result = ArrayList<T>()
result.addAll(this)
result.add(element)
return result
}

当集合很大时,拷贝操作就比较耗性能了。所以对于需要添加元素的集合使用可变集合性能更好。我们知道,不可变集合是线程安全的。但是对于不需要同步的局部变量来说则不适用。这也是为什么对于局部处理,使用可变集合通常更有意义。这个事实可以在标准库中反映出来,在标准库中,所有的集合处理函数都是使用可变集合内部实现的:

1
2
3
4
5
6
7
8
9
10
inline fun <T, R> Iterable<T>.map(
transform: (T) -> R
): List<R> {
val size =
if (this is Collection<*>) this.size else 10
val destination = ArrayList<R>(size)
for (item in this)
destination.add(transform(item))
return destination
}

而不是不可变集合:

1
2
3
4
5
6
7
8
9
// This is not how map is implemented
inline fun <T, R> Iterable<T>.map(
transform: (T) -> R
): List<R> {
var destination = listOf<R>()
for (item in this)
destination += transform(item)
return destination
}

总结:
如果是增加元素,可变集合是很快的,而不可变集合则给我们给多的控制,知道集合是如何变化的。但对于本地作用域来讲,我们不需要这种控制,所以使用可变集合更好。尤其在一些工具类,插入操作可能很频繁。

一、概述

你可能注意到了几乎所有的Kotlin标准库里面的高阶函数都是inline类型的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public inline fun repeat(times: Int, action: (Int) -> Unit) {
for (index in 0 until times) {
action(index)
}
}

public inline fun <T, R> Iterable<T>.map(
transform: (T) -> R
): List<R> {
return mapTo(
ArrayList<R>(collectionSizeOrDefault(10)),
transform
)
}

public inline fun <T> Iterable<T>.filter(
predicate: (T) -> Boolean
): List<T> {
return filterTo(ArrayList<T>(), predicate)
}

这些函数的调用在编译时会被展开到调用处。如下所示:repeat函数会被它本身的函数体替换掉。

1
2
3
4
5
6
7
repeat(10) {
print(it)
}
//↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
for (index in 0 until 10) {
print(index)
}

一般的函数调用通常是:跳进函数体,执行代码,然后跳出函数体,回到调用点。而用函数体替换函数调用是一种完全不同的方式,这种方式有以下一些优点:

  • 类型参数具体化
  • 参数包含函数的方法内联后执行更快
  • 不允许非本地的return语句

使用inline标识符也会有一些缺点,下面👇🏻我们一起来看一下它的优缺点:

一、类型参数具体化:

早期的Java版本不支持泛型,在2004年的J2SE-5.0才支持。由于泛型会在编译期间被擦除,所以在字节码层面是不存在的。例如:List<Int> 编译后成为 List ,所以我们只需要检查一个对象是否是List实例,而不用检查它是否是一个List<Int>

1
2
any is List<Int> // Error
any is List<*> // OK

由于这个原因,我们不能操作类型参数:

1
2
3
fun <T> printTypeName() {
print(T::class.simpleName) // ERROR
}

通过内联函数我们可以突破这种限制。由于函数调用被函数体替换,通过使用reified修饰符,泛型被真实的类型参数替换。

1
2
3
4
5
6
7
8
inline fun <reified T> printTypeName() {
print(T::class.simpleName)
}

// Usage
printTypeName<Int>() //→print(Int::class.simpleName) // Int
printTypeName<Char>() //→print(Char::class.simpleName)// Char
printTypeName<String>() //→print(String::class.simpleName)// String

reified是一个非常有用的修饰符,例如标准库里面的filterIsInstance用来过滤某一种类型的元素。

1
2
3
4
5
6
7
8
class Worker
class Manager

val employees: List<Any> =
listOf(Worker(), Manager(), Worker())

val workers: List<Worker> =
employees.filterIsInstance<Worker>()

它经常被用在我们自己写的代码库或工具类中。下面的例子是使用Gson库实现的通用函数,它能帮助我们简化依赖注入和模块申明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline fun <reified T : Any> String.fromJsonOrNull(): T? =
try {
gson.fromJson(json, T::class.java)
} catch (e: JsonSyntaxException) {
null
}

// usage
val user: User? = userAsText.fromJsonOrNull()

// Koin module declaration
val myModule = module {
single { Controller(get()) } // get is reified
single { BusinessService() } // get is reified
}

// Koin injection
val service: BusinessService by inject()
// inject is reified
二、函数类型的参数内联后执行更快

更确切的讲,短小的函数内联会更快,它无需跳转执行和跟踪调用栈。这也是为什么标准库里面很多小函数都是inline类型的原因。

1
2
3
inline fun print(message: Any?) {
System.out.print(message)
}

当方法没有函数类型的参数时,没必要内联且IntelliJ会给出以下提示⚠️:

要理解其中的原因,我们首先需要理解将函数作为对象进行操作的问题是什么。这些类型的对象(使用函数字面量创建)需要以某种方式保存。在Kotlin/JVM上,需要使用JVM匿名类或普通类创建一些对象。因此,下面的lambda表达式:

1
2
3
val lambda: () -> Unit = {
// code
}

将会被编译为一个类。或JVM匿名类。

1
2
3
4
5
6
// Java
Function0<Unit> lambda = new Function0<Unit>() {
public Unit invoke() {
// code
}
};

或者被编译成一个普通的类,被定义在一个单独的文件中。

1
2
3
4
5
6
7
8
9
10
// Java
// Additional class in separate file
public class Test$lambda implements Function0 < Unit > {
public Unit invoke() {
// code
}
};

// Usage
Function0 lambda = new Test$lambda();

这两种方式没有特别大的区别。

我们注意到,这个函数类型被转换成Function0类型。在Kotlin中,无参类型会被编译器转换成Function0,同理单参数,两参数转换成Function1, Function2,Function3等

  • ()->Unit 编译成 Function0
  • ()->Int 编译成 Function0
  • (Int)->Int 编译成 Function1<Int, Int>
  • (Int, Int)->Int 编译成 Function2<Int, Int, Int>

这些所有的接口都是Kotlin编译器生成的。你不能在Kotlin里显示的使用他们,因为它们是按需生成的,而应该使用函数类型。知道函数类型只是接口为你开启了很多的可能性。比如:

1
2
3
4
5
class OnClickListener : () -> Unit {
override fun invoke() {
// ...
}
}

正如在高效Kotlin-47中所述:避免不必要的对象创建,把函数体包装成对象拖慢代码。这就是为什么下面的代码中,第一个更快。

1
2
3
4
5
6
7
8
9
10
11
inline fun repeat(times: Int, action: (Int) -> Unit) {
for (index in 0 until times) {
action(index)
}
}

fun repeatNoinline(times: Int, action: (Int) -> Unit) {
for (index in 0 until times) {
action(index)
}
}

这种差异是显而易见的,但在现实生活中的例子中很少有显著差异。我们把测试用例设计一下,放大这种差异:

1
2
3
4
5
6
7
8
9
10
11
12
13
@Benchmark
fun nothingInline(blackhole: Blackhole) {
repeat(100_000_000) {
blackhole.consume(it)
}
}

@Benchmark
fun nothingNoninline(blackhole: Blackhole) {
noinlineRepeat(100_000_000) {
blackhole.consume(it)
}
}

第一个在我们电脑平均运行189ms。第二个平均447ms。这种差距体现在:第一个例子迭代调用空函数。第二个例子迭代调用对象,这个对象调用一个空函数。这里使用了额外的对象。

看一个更典型的例子。我们有5000个产品,计算我们购买物品的价格:

1
users.filter { it.bought }.sumByDouble { it.price }

在我的机器上平均耗时38ms。如果filter和sumByDouble不内联耗时多少呢?平均42ms!看起来不多,但每次调用也有10%的差异。

内联和非内联函数最大的区别在于,当我们在函数字面量里捕获变量时。变量被使用时需要被包装成对象。例如:

1
2
3
4
var l = 1L
noinlineRepeat(100_000_000) {
l += it
}

一个本地变量不能直接在非内联lambda中使用。这就是为什么要被包装成引用对象:

1
2
3
4
5
val a = Ref.LongRef()
a.element = 1L
noinlineRepeat(100_000_000) {
a.element = a.element + it
}

区别很大是因为,通常这个对象会被使用很多次,上面代码中的a变量使用了两次。因此,额外的对象调用2*100_000_000。再看一下这个例子👇🏻:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Benchmark
// On average 30 ms
fun nothingInline(blackhole: Blackhole) {
var l = 0L
repeat(100_000_000) {
l += it
}
blackhole.consume(l)
}

@Benchmark
// On average 274 ms
fun nothingNoninline(blackhole: Blackhole) {
var l = 0L
noinlineRepeat(100_000_000) {
l += it
}
blackhole.consume(l)
}

第一个在我电脑运行30ms,第二个274ms。差距的原因是,函数是一个对象,本地变量需要被包装。小的影响累计放大了。大多数情况下,我们不知道有函数类型参数的方法被如何使用,当我们定义这种函数时,最好内联一下。这也是标准库经常这么写的原因。

三、不允许非本地返回

前面定义的repeatNoninline像是一个控制结构,拿它和if语句或for循环对比一下。

1
2
3
4
5
6
7
8
9
10
11
if (value != null) {
print(value)
}

for (i in 1..10) {
print(i)
}

repeatNoninline(10) {
print(it)
}

明显的区别是,内部不能返回

1
2
3
4
5
6
fun main() {
repeatNoinline(10) {
print(it)
return // ERROR: Not allowed
}
}

这是函数字面量编译的结果。当我们的代码处于另外一个类时,不能从main函数返回。但是,当使用内联时,就没限制。

1
2
3
4
5
6
fun main() {
repeat(10) {
print(it)
return // OK
}
}

得益于此,函数可以看起来更像控制结构:

1
2
3
4
5
6
7
fun getSomeMoney(): Money? {
repeat(100) {
val money = searchForMoney()
if (money != null) return money
}
return null
}
四、内联修饰符的缺陷

inline很有用,但不应该随处使用。有些情况下不建议使用。再来看看最重要的限制。

  • 内联函数不能递归,否则调用展开将无限循环。周期性循环尤其危险,因为Intellij不报错:
1
2
3
4
5
6
7
8
9
inline fun a() {
b()
}
inline fun b() {
c()
}
inline fun c() {
a()
}
  • 内联函数不能使用可见性约束的元素

public inline fun中不能使用private 、internal修饰的函数或属性

1
2
3
4
5
6
7
8
internal inline fun read() {
val reader = Reader() // Error
// ...
}

private class Reader {
// ...
}

这也是为什么它不能用于隐藏实现,并且很少在类中使用。

  • 内联函数使代码膨胀

定义一个打印3的函数:

1
2
3
inline fun printThree() {
print(3)
}

调用三次:

1
2
3
4
5
inline fun threePrintThree() {
printThree()
printThree()
printThree()
}

又定义下面函数:

1
2
3
4
5
6
7
8
9
10
11
inline fun threeThreePrintThree() {
threePrintThree()
threePrintThree()
threePrintThree()
}

inline fun threeThreeThreePrintThree() {
threeThreePrintThree()
threeThreePrintThree()
threeThreePrintThree()
}

看一下它们的编译结果,前两个还能看:

1
2
3
4
5
6
7
8
9
inline fun printThree() {
print(3)
}

inline fun threePrintThree() {
print(3)
print(3)
print(3)
}

后两个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline fun threeThreePrintThree() {
print(3)
print(3)
print(3)
print(3)
print(3)
print(3)
print(3)
print(3)
print(3)
}

inline fun threeThreeThreePrintThree() {
print(3)
print(3)
print(3)
...
print(3)
print(3)
print(3)
print(3)
}

这个例子展示了内联函数的弊端:过度使用时代码膨胀严重。

五、crossinline 和noinline

有时候我们想内联一个函数,由于某些原因,不能内联全部的函数类型参数。这种情况下我们使用下面的修饰符:

crossinline:用于内联函数的参数,表示此参数内联范围扩大。对内联函数内部的lambda生效:

1
2
3
4
5
6
inline fun hello(postAction:()->Unit){
println("Hello")
runOnUiThread {
postAction()
}
}

noinline:用于内联函数的参数,表示此参数不能被内联。可以局部性关闭内联。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline fun requestNewToken(
hasToken: Boolean,
crossinline onRefresh: () -> Unit,
noinline onGenerate: () -> Unit
) {
if (hasToken) {
httpCall("get-token", onGenerate) // We must use
// noinline to pass function as an argument to a
// function that is not inlined
} else {
httpCall("refresh-token") {
onRefresh() // We must use crossinline to
// inline function in a context where
// non-local return is not allowed
onGenerate()
}
}
}

fun httpCall(url: String, callback: () -> Unit) {
/*...*/
}

能记住这两个修饰符最好,记不住也没事,IntelliJ会有提示:

六、总结:

使用inline的主要场景是:

  • 经常被使用的函数
  • 具体化的类型参数,像:filterIsInstance
  • 定义带有函数类型的参数的顶层函数。尤其是辅助函数,如集合处理(map、filter)、作用域函数(also、apply、let)、顶层工具函数(repeat、run、with)

我们很少用inline定义API,注意内联函数调用内联函数的情景。记住代码膨胀。

参考:
Effective Kotlin Item 48: Use inline modifier for functions with parameters of functional types

一、概述

你可能对 IterableSequence 傻傻分不清。看一下他们的代码:

1
2
3
4
5
6
7
interface Iterable<out T> {
operator fun iterator(): Iterator<T>
}

interface Sequence<out T> {
operator fun iterator(): Iterator<T>
}

好像只有名字不一样-_-||,但他们却有着本质的区别。Sequence属于懒加载,中间操作符不会触发计算,仅仅是对前一个Sequence的装饰,只有在遇到toList()或count()这些终止操作符时才会执行真正的计算工作。而Iterable每一步都返回一个新的集合。

1
2
3
4
5
6
7
8
9
10
11
public inline fun <T> Iterable<T>.filter(
predicate: (T) -> Boolean
): List<T> {
return filterTo(ArrayList<T>(), predicate)
}

public fun <T> Sequence<T>.filter(
predicate: (T) -> Boolean
): Sequence<T> {
return FilteringSequence(this, true, predicate)
}

下图中filter操作符不做任何计算操作,只是返回一个装饰器对象,在遇到toList()操作符才执行计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
val seq = sequenceOf(1, 2, 3)
val filtered = seq.filter { print("f$it "); it % 2 == 1 }
println(filtered) // FilteringSequence@...

val asList = filtered.toList()
// f1 f2 f3
println(asList) // [1, 3]

val list = listOf(1, 2, 3)
val listFiltered = list
.filter { print("f$it "); it % 2 == 1 }
// f1 f2 f3
println(listFiltered) // [1, 3]

二、优势

Sequence的惰性执行有以下几个优点:

  • 保证操作的顺序性
  • 保证操作执行次数最少化
  • 他们可以是无限的
  • 无需每一步创建新的集合

下面依次讨论一下这些优点

一、顺序性很重要
使用Sequence处理数据时,每个元素依次执行所有操作符。这是一种元素接元素的处理方式。 使用Iterable处理数据时,每个操作符依次执行所有数据。这是一种步骤接步骤的处理方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
sequenceOf(1, 2, 3)
.filter {
print("F$it, ");
it % 2 == 1
}
.map {
print("M$it, ");
it * 2
}
.forEach {
print("E$it, ")
}
// Prints: F1, M1, E2, F2, F3, M3, E6,
1
2
3
4
5
6
7
8
9
10
11
12
13
listOf(1, 2, 3)
.filter {
print("F$it, ");
it % 2 == 1
}
.map {
print("M$it, ");
it * 2
}
.forEach {
print("E$it, ")
}
// Prints: F1, F2, F3, M1, M3, E2, E6,

如果我们不用集合处理函数,而是用循环和条件语句,这和sequence一样,也是一种元素接元素的处理方式。这也为我们提供了一种编译器底层优化的思路:sequence操作可以被优化成循环和条件。

1
2
3
4
5
6
7
8
9
for (e in listOf(1, 2, 3)) {
print("F$e, ")
if (e % 2 == 1) {
print("M$e, ")
val mapped = e * 2
print("E$mapped, ")
}
}
// Prints: F1, M1, E2, F2, F3, M3, E6,
二、Sequence执行最少的操作

我们没必要每一步都处理整个集合。假如我们有一百万个数据,我们只需要前十个,没必要处理十个之后的数据。所以sequence可以执行最少的操作。

看下面的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
(1..10).asSequence()
.filter {
print("F$it, ");
it % 2 == 1
}
.map {
print("M$it, ");
it * 2
}
.find {
it > 5
}
// Prints: F1, M1, F2, F3, M3,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(1..10)
.filter {
print("F$it, ");
it % 2 == 1
}
.map {
print("M$it, ");
it * 2
}
.find {
it > 5
}
// Prints:
//F1, F2, F3, F4, F5, F6, F7, F8, F9, F10,
// M1, M3, M5, M7, M9,

这个例子中,有很多个操作符,最后的终止操作符不需要处理所有的数据,因此sequence性能更好。类似的操作符还有:first, find, take, any, all, noneindexOf

三、Sequence是无限的

由于Sequence按需处理,我们可以定义无限序列。一种常用的方式是使用sequence生成器 generateSequencesequence

generateSequence需要传如第一个值,以及如何产生下一个值:

1
2
3
4
5
generateSequence(1) { it + 1 }
.map { it * 2 }
.take(10)
.forEach { print("$it, ") }
// Prints: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,

sequence 则使用挂起函数按需生成数据。只要我们需要数据他就执行,一直到调用yield方法。然后挂起直到下次再向他请求数据。下面是一个无限生成斐波那契数列的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.math.BigDecimal

val fibonacci: Sequence<BigDecimal> = sequence {
var current = 1.toBigDecimal()
var prev = 1.toBigDecimal()
yield(prev)
while (true) {
yield(current)
val temp = prev
prev = current
current += temp
}
}

fun main() {
print(fibonacci.take(10).toList())
// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
}

需要注意的是,使用无限序列需要限制元素的数量,否则将无限的运行下去。

1
print(fibonacci.toList()) // Runs forever

为了不让它无限循环的运行,我们可以使用take限制元素数量,或者使用first、find、indexOf等。在不限制数量的情况下,不要使用any、all、none。

四、sequence每一步不产生新集合

标准的集合处理函数每一步都返回新的集合,当我们处理大量数据时会分配很多临时内存。

1
2
3
4
5
6
7
8
9
10
num
.filter {// 1
it % 10 == 0
}
.map {// 2
it * 2
}
.sum()
// In total, 2 collections
// created under the hood
1
2
3
4
5
6
7
8
9
num.asSequence()
.filter {//0
it % 10 == 0
}
.map {//0
it * 2
}
.sum()
// No collections created

一个极端又常见的例子:文件读取。文件可能是几个G,每执行一个操作符都分配这么多内存是一种极大的浪费。下面例子是读取大小1.53G的芝加哥犯罪记录中包含毒品交易信息的记录数量,其中readLines 返回 List

1
2
3
4
5
6
7
8
9
10
// BAD SOLUTION, DO NOT USE COLLECTIONS FOR 
// POSSIBLY BIG FILES
File("ChicagoCrimes.csv")
.readLines()
.drop(1) // Drop descriptions of the columns
.mapNotNull { it.split(",").getOrNull(6) }
// Find description
.filter { "CANNABIS" in it }
.count()
.let(::println)

这段程序在我电脑上的运行结果是:

script
1
OutOfMemoryError.n> Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

我们创建了一个集合,中间三个操作符产生集合,一个四个集合。其中三个包含文件的主要主要数据记录,一共消耗4.59G。正确的实现应该使用sequence,我们使用useLines函数,每次只操作一行记录。

1
2
3
4
5
6
7
8
9
File("ChicagoCrimes.csv").useLines { lines ->
// The type of `lines` is Sequence<String>
lines.drop(1) // Drop descriptions of the columns
.mapNotNull { it.split(",").getOrNull(6) }
// Find description
.filter { "CANNABIS" in it }
.count()
.let { println(it) } // 318185
}

同样运行这段代码,只耗时8.3s。为了比较一下这两种方法的效率,我做了另外一个实验:删除数据中不必要的列以减少文件大小,得到CrimeData.csv只有728MB,然后做相同的操作。使用Collection处理函数,耗时13s,使用sequence函数,耗时4.5s。正如实验数据,使用sequence处理大文件不仅节约内存,而且提升性能。

事实上,在每个步骤中,我们创建一个新的集合本身也是一种成本,当我们处理包含大量元素的集合时,这种成本就会显现出来。差别并不大——主要是因为在许多步骤中创建的集合都是用预期的大小初始化的,所以当我们添加元素时,我们只需要将它们放在下一个位置。尽管即使是廉价的集合复制也比完全不复制要昂贵,这也是为什么我们应该更喜欢对具有多个处理步骤大集合使用Sequence的主要原因。

大集合:元素多(含数万个元素的整数列表)、元素大(超长字符串)

多个处理步骤:处理集合时使用很多操作符。

如果对比下面两个函数:

1
2
3
4
5
6
7
8
9
fun singleStepListProcessing(): List<Product> {
return productsList.filter { it.bought }
}

fun singleStepSequenceProcessing(): List<Product> {
return productsList.asSequence()
.filter { it.bought }
.toList()
}

你会发现,在性能上区别不大(实际上,简单的list处理更快,因为它的filter函数是内联的)。但是,当你使用多个操作符,先filter再map,在大集合上性能问题就行显现出来。为了看到区别,我们比较一下2个操作符和3个操作符处理5000个数据的情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
fun twoStepListProcessing(): List<Double> {
return productsList
.filter { it.bought }
.map { it.price }
}

fun twoStepSequenceProcessing(): List<Double> {
return productsList.asSequence()
.filter { it.bought }
.map { it.price }
.toList()
}

fun threeStepListProcessing(): Double {
return productsList
.filter { it.bought }
.map { it.price }
.average()
}

fun threeStepSequenceProcessing(): Double {
return productsList.asSequence()
.filter { it.bought }
.map { it.price }
.average()
}

下面是在MacBook Pro(Retina, 15-inch, Late 2013)处理5000个元素的平均结果:

1
2
3
4
twoStepListProcessing                        81 095 ns
twoStepSequenceProcessing 55 685 ns
twoStepListProcessingAndAcumulate 83 307 ns
twoStepSequenceProcessingAndAcumulate 6 928 ns

很难预测我们能提升但是性能,根据我的观察,在一个包含多个步骤的典型集合处理中,对于至少几千个元素,我们可以预期大约20-40%的性能提升。

五、sequence什么时候没那么快?

有些情况我们要处理整个集合,sequence并不能给我们带来什么收益。如sorted(当前来讲它是唯一一个例子)。sorted的最优实现:积攒Sequence并放入List,然后使用Java的sort函数。缺点是,与Collection.sort相比,积攒过程会消耗额外的时间。

Sequence是否应该支持sorted函数是有争议的,因为当一个序列的方法需要所有元素才能完成计算时,后续操作只是部分延迟,并且它不支持无限序列。之所以添加sorted操作只是因为它很常用,好用。Kotlin开发者需要了解它的缺陷,尤其是它不能用于无限序列。

1
2
3
4
generateSequence(0) { it + 1 }.take(10).sorted().toList()
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
generateSequence(0) { it + 1 }.sorted().take(10).toList()
// Infinite time. Does not return.

在Collection上使用sorted比在Sequence上更快只是少数特例。当我们只使用很少操作符函数和单个sorted函数时,还是建议使用sequence来处理。

1
2
3
4
5
6
productsList.asSequence()
.filter { it.bought }
.map { it.price }
.sorted()
.take(10)
.sum()
六、看看Java的Stream操作

Java 8新增了集合处理流的特性,看起来和Kotlin的序列很像。

1
2
3
4
productsList.asSequence()
.filter { it.bought }
.map { it.price }
.average()
1
2
3
4
5
productsList.stream()
.filter { it.bought }
.mapToDouble { it.price }
.average()
.orElse(0.0)

Java 8的Stream也是惰性的在最后一个操作符触发计算。与Kotlin sequence的区别主要是:

  • Kotlin sequence包含更多的处理函数(被定义为拓展函数),使用简单: toList() vs collect(Collectors.toList())
  • Java stream可以开启并行模式,在多核处理器上会有很大的性能提升。
  • Kotlin sequence可以用于Kotlin/JVM、Kotlin/JS、Kotlin/Native模块中。Java stream只能用于Kotlin/JVM,且JVM版本至少是8

总之,我们不用Java stream并行模式时很难将谁的性能更好,我建议少用Java stream,只有在处理重量级计算问题中使用并行模式可以显著带来收益的情况下使用,其他情况用Kotlin标准函数能带来清晰的代码结构和多平台支持。

七、调试Sequence

Kotlin Sequence和Java Stream都支持debug每一步操作。Java需要使用”Java Stream Debugger”插件,Kotlin则需要”Kotlin Sequence Debugger”插件,现在已经被集成在了Kotlin插件中了。

三、总结

集合和序列非常相似,都支持相同的处理函数。但他们也有很大的区别。Sequence处理是困难的,因为我们要保持原集合不变,执行相应转换后再放回原集合。Sequence是惰性的,带来很多优点:

  • 保证操作的顺序性
  • 保证操作执行次数最少化
  • 他们可以是无限的
  • 无需每一步创建新的集合

基于这些优点,对于包含多个处理步骤的包含大对象或元素很多的集合来说使用Sequence更好。Sequence也包含调试器,能帮助我们可视化的分析元素处理过程。Sequence不是为了取代传统的集合处理方式,使用前应该分析清楚自己的目的和原因才能带来性能的提升以及更少的内存问题。

四、参考

Effective Kotlin Item 51: Prefer Sequence for big collections with more than one processing step

    协程一般用于异步编程。在解决异步编程问题方面,Kotlin编译器在对协程的设计和实现是通用的。我们可以借助协程优雅的解决深度递归问题。

一、问题描述

定义以下二叉树的结点,并构造一棵只含十万个左结点的树,进行深度遍历,求树的深度:

1
2
3
4
5
6
7
8
9
//结点定义
class Tree(val left: Tree?, val right: Tree?)

//构造二叉树:以叶子结点开始,重复构造父结点,并把当前结点作为父结点的左子树
val n = 100_000
val deepTree = generateSequence(Tree(null, null)) { prev ->
Tree(prev, null)
}.take(n).last()

二、解决方案

2.1 解决方案一:
1
2
3
4
5
fun depth(t: Tree?): Int =
if (t == null) 0 else maxOf(
depth(t.left), // recursive call one
depth(t.right) // recursive call two
) + 1

分析:
对树进行递归是最简洁直接的解决方案。而递归将保存函数的调用栈用于后续状态恢复,线程的调用栈是有大小限制的,此处将抛出Exception in thread "main" java.lang.StackOverflowError错误。

2.2 解决方案二:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun depth(t: Tree?): Int {
if (t == null) return 0
class Frame(val node: Tree, var state: Int = 0, var depth: Int = 1)
val stack = ArrayList<Frame>()
val root = Frame(t)
stack.add(root)
while (stack.isNotEmpty()) {
val frame = stack.last()
when (frame.state++) {
0 -> frame.node.left?.let { l -> stack.add(Frame(l)) }
1 -> frame.node.right?.let { r -> stack.add(Frame(r)) }
2 -> {
stack.removeLast()
stack.lastOrNull()?.let { p ->
p.depth = maxOf(p.depth, frame.depth + 1)
}
}
}
}
return root.depth
}

分析:
基于解决方案一,我们考虑将调用栈状态的保存转移到内存空间更大的堆区,并加入了状态机和while循环。在此例中,程序开始时将全部走状态0,将所有的左节点加入stack。然后全部走状态2(因为没有右结点),由下到上计算每一个结点的深度。最后返回根节点的深度。

2.3 解决方案三:
1
2
3
4
5
6
val depth = DeepRecursiveFunction<Tree?, Int> { t ->
if (t == null) 0 else maxOf(
callRecursive(t.left),
callRecursive(t.right)
) + 1
}

分析:
方案二中的状态机就是Kotlin挂起函数的实现原理。所以我们也可以利用Kotlin的挂起函数实现深度遍历。那么方案三是如何实现的呢?我们分析三个方面:

  • 如何调用
  • 如何进入循环
  • 如何保存状态

2.3.1 调用
DeepRecursiveFunction类声明了invoke操作符,调用depth函数就是调用下面👇🏻的操作符。

1
2
3
4
@SinceKotlin("1.4")
@ExperimentalStdlibApi
public operator fun <T, R> DeepRecursiveFunction<T, R>.invoke(value: T): R =
DeepRecursiveScopeImpl<T, R>(block, value).runCallLoop()

2.3.2 循环
调用DeepRecursiveFunction后直接进入runCallLoop()循环,result的默认值为UNDEFINED_RESULT,所以会启动我们的递归业务逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
@Suppress("UNCHECKED_CAST")
fun runCallLoop(): R {
while (true) {
// Note: cont is set to null in DeepRecursiveScopeImpl.resumeWith when the whole computation completes
val result = this.result
val cont = this.cont
?: return (result as Result<R>).getOrThrow() // done -- final result
// The order of comparison is important here for that case of rogue class with broken equals
if (UNDEFINED_RESULT == result) {
// call "function" with "value" using "cont" as completion
val r = try {
// This is block.startCoroutine(this, value, cont)
function.startCoroutineUninterceptedOrReturn(this, value, cont)
} catch (e: Throwable) {
cont.resumeWithException(e)
continue
}
// If the function returns without suspension -- calls its continuation immediately
if (r !== COROUTINE_SUSPENDED)
cont.resume(r as R)
} else {
// we returned from a crossFunctionCompletion trampoline -- call resume here
this.result = UNDEFINED_RESULT // reset result back
cont.resumeWith(result)
}
}
}

2.3.3 状态保存
每次调用callRecursive时将保存当前的值和cont(continuation),注意这里cont对象每次都不是同一个对象。当进行挂起恢复时,拿到旧的continuation进行回调。

1
2
3
4
5
6
suspend fun callRecursive(value: T): R = 
suspendCoroutineUninterceptedOrReturn { cont ->
this.cont = cont
this.value = value
COROUTINE_SUSPENDED
}

参考:

Deep recursion with coroutines

一、概述

    Android中的视图是以树的形式组织起来的,它是一种层次结构。在代码中体现为组合模式,一个ViewGroup可以包含一个或多个View,同时ViewGroup又是一个View。在布局文件中体现为xml的结点和缩进。
    同时视图的渲染少不了对其进行遍历,这就涉及数据结构中树的深度优先遍历和广度优先遍历。有时候一些复杂的布局一次遍历还无法完全确定View的信息。如何通过算法方式降低树的层次呢?也许这就是约束布局存在的意义吧。
    在Android中,灵活运用ConstraintLayout包括以下几个点:

  • 主属性
    • 通过相对位置约束View
    • 控制约束之间的距离
    • 居中和偏移百分比
    • 通过圆定位📌View
    • 通过可见性控制View
    • 通过分辨率约束View
    • 通过链⛓约束View
  • 辅助工具
    • Barrier屏障约束
    • Group分组约束
    • Placeholder占位约束
    • Guideline引导线约束

二、使用

2.1 通过相对位置约束View
约束属性 描述 约束属性 描述
layout_constraintLeft_toLeftOf layout_constraintLeft_toRightOf
layout_constraintRight_toLeftOf layout_constraintRight_toRightOf
layout_constraintTop_toTopOf layout_constraintTop_toBottomOf
layout_constraintBottom_toTopOf layout_constraintBottom_toBottomOf
layout_constraintStart_toEndOf layout_constraintStart_toStartOf
layout_constraintEnd_toStartOf layout_constraintEnd_toEndOf
layout_constraintBaseline_toBaselineOf
2.2 控制约束之间的距离
约束属性 描述 约束属性 描述
android:layout_marginStart layout_goneMarginStart
android:layout_marginEnd layout_goneMarginEnd
android:layout_marginLeft layout_goneMarginLeft
android:layout_marginTop layout_goneMarginTop
android:layout_marginRight layout_goneMarginRight
android:layout_marginBottom layout_goneMarginBottom
android:layout_marginBaseline layout_goneMarginBaseline
2.3 居中和偏移百分比
约束属性 描述 约束属性 描述
layout_constraintHorizontal_bias layout_constraintVertical_bias
2.4 通过圆定位📌View
约束属性 描述
layout_constraintCircle 另一个widget的id
layout_constraintCircleRadius 圆的半径
layout_constraintCircleAngle 角度
1
2
3
4
<Button android:id="@+id/buttonB" 
app:layout_constraintCircle="@+id/buttonA"
app:layout_constraintCircleRadius="100dp"
app:layout_constraintCircleAngle="45" />
2.5 通过可见性控制View
2.6 通过分辨率约束View
约束属性 描述 约束属性 描述
android:minWidth android:minHeight
android:maxWidth android:maxHeight

2.6.1 百分比

1
2
3
4
5
<Button android:id="@+id/buttonA" 
android:layout_width="0dp"
app:layout_constraintWidth_default="percent"
app:layout_constraintWidth_percent="0.5"
/>

app:layout_constraintWidth_default可以取的值包括:

  • spread
  • percent
  • wrap

在ConstraintLayout-1.1之后,使用app:layout_constrainedWidth="true"替代app:layout_constraintWidth_default="wrap"

2.6.2 比率
宽高一比一:

1
2
3
4
<Button android:id="@+id/buttonA" 
android:layout_height="0dp"
app:layout_constraintDimensionRatio="1:1"
/>

指定一条边符合约束比率:

1
2
3
4
5
<Button android:layout_width="0dp"
android:layout_height="0dp"
app:layout_constraintDimensionRatio="H,16:9"
app:layout_constraintBottom_toBottomOf="parent"
app:layout_constraintTop_toTopOf="parent"/>
2.7 通过链⛓约束View
图示 Style
_chainStyle="spread"
_chainStyle="spread_inside"
_chainStyle="spread"
_weight="1"
_chainStyle="packed"
_chainStyle="packed"
_bias="0.3"
2.8 Barrier

将多个View的某一边的极端值作为约束:

1
2
3
4
5
6
<androidx.constraintlayout.widget.Barrier
android:id="@+id/barrier"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
app:barrierDirection="start/end"
app:constraint_referenced_ids="button1,button2" />
2.9 Group分组约束

将多个View作为一个组一起控制:

1
2
3
4
5
6
<androidx.constraintlayout.widget.Group
android:id="@+id/group"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:visibility="visible"
app:constraint_referenced_ids="button4,button9" />
  • 无法通过group设置点击事件
    1
    2
    3
    4
    5
    group.referencedIds.forEach { id ->
    view.findViewById(id).setOnClickListener {
    //do something
    }
    }
2.10 Placeholder占位约束

    Placeholder是一个虚拟的占位符View,界面上其他存在的View可以通过placeholder.setContentId(R.id.xxx)将自己的位置设置到placeholder的位置,原位置视图将不可见。
    我们可以使用Placeholder搭建一个布局模板,include到其他布局当中,来填充模板中的视图,这将使所有的界面有一个通用的模板。

2.11 Guideline引导线约束

Guideline只能在ConstraintLayout中使用,在水平或垂直方向设置辅助布局的不可见线条。

约束属性 描述
layout_constraintGuide_begin 距布局的左边或者上边x处设置引导线
layout_constraintGuide_end 距布局右边或下面x处设置引导线
layout_constraintGuide_percent 宽或高的百分之x处设置引导线
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<androidx.constraintlayout.widget.ConstraintLayout
xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:layout_width="match_parent"
android:layout_height="match_parent">

<androidx.constraintlayout.widget.Guideline
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:id="@+id/guideline"
app:layout_constraintGuide_begin="100dp"
android:orientation="vertical"/>

<Button
android:text="Button"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:id="@+id/button"
app:layout_constraintLeft_toLeftOf="@+id/guideline"
android:layout_marginTop="16dp"
app:layout_constraintTop_toTopOf="parent" />

</androidx.constraintlayout.widget.ConstraintLayout>

三、原理

3.1 解决约束问题

3.1.1 定义变量

1
x[1], x[2], ... x[n]

3.1.2 定义约束问题:

1
2
3
a[1]x[1] + ... + a[n]x[n] = b
a[1]x[1] + ... + a[n]x[n] <= b
a[1]x[1] + ... + a[n]x[n] >= b

3.2.3 计算约束方程
食火鸡算法:食火鸡是一种生活在新几内亚热带雨林中的鸟类,以水果为食。同时它也是一种解决线性方程和线性不等式的算法。1990年在华盛顿大学被证明和发现。线性方程非常适合用于表示用户界面中视图的位置、大小、与其他视图的关系。

3.2 个人理解:

定义变量 -> 声明View对象
定义约束问题 -> 建立View之间的约束关系
计算约束方程 -> 计算视图的大小、坐标

四、参考文档

1.官方文档
2.基本使用
3.基本使用-译文
4.ConstraintLayout, Inside and Out: Part 1
5.ConstraintLayout, Inside and Out: Part 2
6.线性约束解决算法
7.解决约束