开发者博客 – IT技术 尽在开发者博客

开发者博客 – 科技是第一生产力


  • 首页

  • 归档

  • 搜索

Google 推荐在项目中使用 sealed 和 Remot

发表于 2020-07-27

之前分享过一篇 Jetpack + MVVM 综合实战应用 神奇宝贝(PokemonGo) 眼前一亮的 Jetpack + MVVM 极简实战 主要包了以下功能:

  1. 自定义 RemoteMediator 实现 network + db 的混合使用 ( RemoteMediator 是 Paging3 当中重要成员 )
  2. 使用 Data Mapper 分离数据源 和 UI
  3. Kotlin Flow 结合 Retrofit2 + Room 的混合使用
  4. Kotlin Flow 与 LiveData 的使用
  5. 使用 Coil 加载图片
  6. 使用 ViewModel、LiveData、DataBinding 协同工作
  7. 使用 Motionlayout 做动画
  8. App Startup 与 Hilt 的使用
  9. 在 Flow 基础上封装成功或者失败处理

这篇文章是对 神奇宝贝(PokemonGo) 的部分功能做全面的分析,主要包含以下内容:

  • 如何在 Flow 基础上封装成功或者失败处理?
  • 如何自定义 RemoteMediator 实现 数据库 和 网络 加载数据?
  • Paging3 当中的 RemoteMediator 和 PagingSource 的区别?
  • Paging3 中的 cachedIn 是什么?它为我们解决了什么问题?

在开始阅读本文之前,建议更新 PokemonGo 最新的代码,对照着代码一起看,为了节省篇幅,文中只会列出核心代码。

如何在 Flow 基础上封装成功或者失败处理

之前有小伙们问过我,如何在 Flow 基础上封装成功或者失败处理逻辑,关于这个问题,其实 Google Android 团队的工程师在 medium 上发表过一篇文章 Sealed with a class 建议我们使用 sealed,在 Paging3 源码里面也大量用到了 sealed。

在分析封装逻辑之前,我们先来看一下 Paging3 源码是如何处理的,在 Paging3 中有个很重要的类 RemoteMediator,在 RemoteMediator 中有个重要的方法 load()

1
kotlin复制代码abstract suspend fun load(loadType: LoadType, state: PagingState<Key, Value>): MediatorResult

load() 方法返回值是 MediatorResult,我们来看一下 MediatorResult 源码的实现。

1
2
3
4
5
6
7
less复制代码sealed class MediatorResult {
class Error(val throwable: Throwable) : MediatorResult()

class Success(
@get:JvmName("endOfPaginationReached") val endOfPaginationReached: Boolean
) : MediatorResult()
}

其实 MediatorResult 是一个密封类,密封类有两个子类分别为 Error 和 Success 封装了成功和失败处理逻辑。

我们在来看一下另外一个类 LoadState,在 Jetpack 新成员 Paging3 网络实践及原理分析(二)- 监听网路请求状态 文章中也提到 refresh、prepend 和 append 都是 LoadState 的对象,我们来看一下 LoadState 源码实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
kotlin复制代码sealed class LoadState( val endOfPaginationReached: Boolean) {
class NotLoading( endOfPaginationReached: Boolean) :LoadState(endOfPaginationReached) {
......
}

object Loading : LoadState(false) {
......
}

class Error(val error: Throwable) : LoadState(false) {
......
}
}

LoadState 是一个密封类,它有三个子类 NotLoading 、 Loading 、 Error 代表网络请求状态。

变量 作用
Error 表示加载失败
Loading 表示正在加载
NotLoading 表示当前未加载

正如你所见在 Paging3 源码中对于成功和失败处理都用到了 sealed,我们可以仿照 Paging3 源码,使用 sealed 在 Flow 基础上封装成功或者失败处理。

PokemonGo/app/src/main/java/com/hi/dhl/pokemon/data/remote/PokemonResult.kt

1
2
3
4
5
csharp复制代码sealed class PokemonResult<out T> {
data class Success<out T>(val value: T) : PokemonResult<T>()

data class Failure(val throwable: Throwable?) : PokemonResult<Nothing>()
}

PokemonResult 是一个密封类,同样它也有两个子类 Success 和 Failure 分别表示成功和失败,我们来看一下如何使用。

PokemonGo/app/src/main/java/com/hi/dhl/pokemon/data/repository/PokemonRepositoryImpl.kt

1
2
3
4
5
6
7
8
9
10
kotlin复制代码override suspend fun featchPokemonInfo(name: String): Flow<PokemonResult<PokemonInfoModel>> {
return flow {
try {

emit(PokemonResult.Success(model)) // 成功
} catch (e: Exception) {
emit(PokemonResult.Failure(e.cause)) // 失败
}
}.flowOn(Dispatchers.IO) // 通过 flowOn 切换到 io 线程
}
  • 如果请求成功返回 PokemonResult.Success(model)
  • 如果出现错误返回 PokemonResult.Failure(e.cause)

这只是一个简单的封装,可以在这个基础上,针对于不同的场景进行二次封装,接下来看一下在 ViewModel 中如何处理。

PokemonGo/app/src/main/java/com/hi/dhl/pokemon/ui/detail/DetailViewModel.kt

1
2
3
4
5
6
7
8
csharp复制代码when (result) {
is PokemonResult.Failure -> {
_failure.value = result.throwable?.message ?: "failure"
}
is PokemonResult.Success -> {
_pokemon.postValue(result.value)
}
}

使用强大的 when 表达式,针对于成功或者失败进行不同的处理,在 Pokemon 项目中,如果没有网,进入详情页,会弹出一个失败的 toast。

when 表达式虽然强大,但是有一个问题,在一个项目中进行网络请求的地方会有很多,如果每次都要写 when 表达式,就会出现很多重复的代码,那么如何减少这样的模板代码呢,可以利用 Kotlin 提供的强大的扩展函数,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
kotlin复制代码inline fun <reified T> PokemonResult<T>.doSuccess(success: (T) -> Unit) {
if (this is PokemonResult.Success) {
success(value)
}
}

inline fun <reified T> PokemonResult<T>.doFailure(failure: (Throwable?) -> Unit) {
if (this is PokemonResult.Failure) {
failure(throwable)
}
}

使用扩展函数进一步封装的目的是减少模板代码,我们重新修改一下之前使用 when 表达式的地方。

1
2
3
4
5
6
7
scss复制代码result.doFailure { throwable ->
_failure.value = throwable?.message ?: "failure"
}
result.doSuccess { value ->
_pokemon.postValue(value)
emit(value)
}

如果在其他地方也需要进行成功 或者 失败处理,只需要调用对应的扩展函数即可,到这里关于如何在 Flow 基础上封装成功或者失败处理就分析完了。

接下来我们一起来分析一下今天的主角 如何自定义 RemoteMediator 实现 数据库 和 网络 加载数据,建议在了解这部分内容之前,先看一下之前的两篇文章,因为它们都是关联在一起的。

  • Jetpack 成员 Paging3 数据库的实践以及源码分析(一)
  • Jetpack 新成员 Paging3 网络实践及原理分析(二)

RemoteMediator 主要用来实现加载网络分页数据并更新到数据库中,在开始分析之前,我们先来了解一下基本概念。

Paging3 类的职能

  • PagingData :用于分页数据的容器,每次数据刷新都有一个单独的对应 PagingData
  • Pager :是 Paging3 的主要的入口,在其构造方法中接受 PagingConfig 、initialKey 、remoteMediator 、pagingSourceFactory
  • Pager.flow :将会构建一个 Flow<PagingData>,在 PagingConfig 构造方法中定义了 pageSize、prefetchDistance、initialLoadSize 等等
  • PagingDataAdapter :是一个处理分页数据的可回收视图适配器,可以使用 AsyncPagingDataDiffer 组件来构建自己的自定义适配器
  • PagingSource :每个 PagingSource 对象定义一个数据源以及如何从该数据源查找数据
  • RemoteMediator :RemoteMediator 实现加载网络分页数据并更新到数据库中

到这里小伙伴们应该会有一个疑惑 RemoteMediator 和 PagingSource 都是用来加载数据源的数据,那么它们有什么区别?

RemoteMediator 和 PagingSource 的区别

  • RemoteMediator:实现加载网络分页数据并更新到数据库中,但是数据源的变动不能直接映射到 UI 上
  • PagingSource:实现单一数据源以及如何从该数据源中查找数据,例如 Room,数据源的变动会直接映射到 UI 上

使用分层数据源的分页实现

上图来自 Google 官网,正如你所见,使用 RemoteMediator 实现从网络加载分页数据更新到数据库中,使用 PagingSource 从数据库中查找数据并显示在 UI 上。

在项目中如何进行选择?

  • PagingSource:用于加载有限的数据集(本地数据库)例如手机通讯录等等 ,可以参考 Jetpack 成员 Paging3 数据库的实践以及源码分析(一) 这篇文章的实现
  • RemoteMediator:主要用来加载网络分页数据并更新到数据库中,当我们没有更多的数据时,我们向网络请求更多的数据,结合 PagingSource 当保存更多数据时会直接映射到 UI 上

注意:

  1. RemoteMediator 目前是实验性的 API ,所有实现 RemoteMediator 的类都需要添加 @OptIn(ExperimentalPagingApi::class) 注解。
  2. 当我们使用 OptIn 注解,需要在 App 模块下的 build.gradle 文件内添加以下代码
1
2
3
4
5
css复制代码android {
kotlinOptions {
freeCompilerArgs += ["-Xopt-in=kotlin.RequiresOptIn"]
}
}

当我们了解完基本概念之后,接下来一起来分析一下如何实现 RemoteMediator,在这里建议更新 PokemonGo 最新代码,对照着项目中的代码一起看,为了节省篇幅文章中只会列出核心代码。

三步实现 RemoteMediator

使用分层数据源的分页实现

如上面图片所示在 Repository 中通过 RemoteMediator 获取网络分页数据并更新到数据库中,PagingSource 当保存更多数据时会直接映射到 UI 上。

其实实现一个 RemoteMediator 贯穿了数据源、Repository、ViewModel,接下来我们来分析一下如何在每层中,分三步实现一个 RemoteMediator。

1. 定义数据源

使用 Room 作为本地的数据源,将网络分页数据存储在本地数据库中。

PokemonGo/app/src/main/java/com/hi/dhl/pokemon/data/local/PokemonDao.kt

1
2
3
4
5
6
7
8
9
10
kotlin复制代码@Dao
interface PokemonDao {

@Insert(onConflict = OnConflictStrategy.REPLACE)
suspend fun insertPokemon(pokemonList: List<PokemonEntity>)

@Query("SELECT * FROM PokemonEntity")
fun getPokemon(): PagingSource<Int, PokemonEntity>

}
  • 在 Paging3 中使用的是 Flow,所以 insertPokemon 方法前需要添加 suspend 修饰符。
  • 需要注意的是 getPokemon() 方法返回了一个 PagingSource<Key, Value>,意味着数据源更新时会映射到 UI 上,其中 Key 和 Value 和实现 RemoteMediator 有很大关系,后面会提到。

2. 在 Repository 中实现 RemoteMediator

RemoteMediator 和 PagingSource 相似,都需要覆盖 load() 方法,但是不同的是 RemoteMediator 不是加载分页数据到 RecyclerView 列表上,而是获取网络分页数据并更新到数据库中。

PokemonGo/app/src/main/java/com/hi/dhl/pokemon/data/repository/PokemonRemoteMediator.kt

注意:

刚才我们在数据源中定义 getPokemon() 方法,其返回值是 PagingSource<Int, PokemonEntity>,那我们在实现 RemoteMediator<Key, Value> 的时候,其中 Key 和 Value,应该和 PagingSource<Int, PokemonEntity> Key 和 Value 相同,代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
kotlin复制代码@OptIn(ExperimentalPagingApi::class)
class PokemonRemoteMediator(
val api: PokemonService,
val db: AppDataBase
) : RemoteMediator<Int, PokemonEntity>() {

override suspend fun load(
loadType: LoadType,
state: PagingState<Int, PokemonEntity>
): MediatorResult {
/**
* 在这个方法内将会做三件事
*
* 1. 参数 LoadType 有个三个值,关于这三个值如何进行判断
* LoadType.REFRESH
* LoadType.PREPEND
* LoadType.APPEND
*
* 2. 请问网络数据
*
* 3. 将网络数据插入到本地数据库中
*/
}
}

load() 方法有两个重要的参数,它们的意思如下所示:

  • PagingState:这个类当中有两个重要的变量
+ `pages: List<Page<Key, Value>>` 返回的上一页的数据,主要用来获取上一页最后一条数据作为下一页的开始位置
+ `config: PagingConfig` 返回的初始化设置的 PagingConfig 包含了 pageSize、prefetchDistance、initialLoadSize 等等
  • LoadType 是一个枚举类,里面定义了三个值,如下所示
类名 作用
LoadType.Refresh 在初始化刷新的使用
LoadType.Append 在加载更多的时候使用
LoadType.Prepend 在当前列表头部添加数据的时候使用

load() 的返回值 MediatorResult,MediatorResult 是一个密封类,根据不同的结果返回不同的值

  • 请求出现错误,返回 MediatorResult.Error(e)
  • 请求成功且有数据,返回 MediatorResult.Success(endOfPaginationReached = true)
  • 请求成功但是没有数据,返回 MediatorResult.Success(endOfPaginationReached = false)
  • 参数 endOfPaginationReached 表示是否还有更多数据

在 load() 方法里面将会做三件事 1. 如何判断参数 LoadType 、2. 请问网络数据 、3. 将网络数据插入到本地数据库中

1. 如何判断参数 LoadType

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
kotlin复制代码val pageKey = when (loadType) {
// 首次访问 或者调用 PagingDataAdapter.refresh()
LoadType.REFRESH -> null
// 在当前加载的数据集的开头加载数据时
LoadType.PREPEND -> return MediatorResult.Success(endOfPaginationReached = true)
LoadType.APPEND -> { // 下来加载更多时触发
/**
* 方式一:这种方式比较简单,当前页面最后一条数据是下一页的开始位置
* 通过 load 方法的参数 state 获取当页面最后一条数据
*/
// val lastItem = state.lastItemOrNull()
// if (lastItem == null) {
// return MediatorResult.Success(
// endOfPaginationReached = true
// )
// }
// lastItem.page

/**
* 方式二:比较麻烦,当前分页数据没有对应的远程 key,这个时候需要我们自己建表
*/
val remoteKey = db.withTransaction {
db.remoteKeysDao().getRemoteKeys(remotePokemon)
}
if (remoteKey == null || remoteKey.nextKey == null) {
return MediatorResult.Success(endOfPaginationReached = true)
}
remoteKey.nextKey
}
}
  • LoadType.REFRESH:首次访问 或者调用 PagingDataAdapter.refresh() 触发,加载第一页数据,这里不需要做任何操作,返回 null 就可以。
  • LoadType.PREPEND:在当前列表头部添加数据的时候时触发,需要注意的是当 LoadType.REFRESH 触发了,LoadType.PREPEND 也会触发,所以为了避免重复请求,直接返回 MediatorResult.Success(endOfPaginationReached = true) 即可
  • LoadType.APPEND:下拉加载更多时触发,这里获取下一页的 key,如果 key 不存在,直接返回 MediatorResult.Success(endOfPaginationReached = true) 不会在进行请求

2. 请问网络数据

1
2
3
4
5
ini复制代码val page = pageKey ?: 0
val result = api.fetchPokemonList(
state.config.pageSize,
page * state.config.pageSize
).results

这里不需要调用 withContext(Dispatcher.IO) { ... } 因为 Retrofit 的协程是发生在 worker thread 中的

3. 将网络分页数据并更新到数据库中

1
2
scss复制代码remoteKeysDao.insertAll(entity)
pokemonDao.insertPokemon(item)

所有实现 RemoteMediator 的类都需要重写 load() 方法,在 load() 方法内按照如上三步实现即可,具体逻辑需要根据需求而定。

PokemonRemoteMediator 完整代码太长了,这里就不贴了,可以点击 PokemonRemoteMediator 前去查看。

3. 在 Repository 中构建 Pager

Pager 是 Paging3 的主要的入口,是从数据源获取数据的入口,其构造方法接受 pagingConfig 、initialKey 、remoteMediator 、pagingSourceFactory,其中 initialKey、remoteMediator 是可选的,pageConfig 和 pagingSourceFactory 必填的,代码如下所示。

PokemonGo/app/src/main/java/com/hi/dhl/pokemon/data/repository/PokemonRepositoryImpl.kt

1
2
3
4
5
6
7
8
scss复制代码Pager(
config = pageConfig,
remoteMediator = PokemonRemoteMediator(api, db)
) {
db.pokemonDao().getPokemon()
}.flow.map { pagingData ->
pagingData.map { mapper2ItemMolde.map(it) }
}
  • config :初始化 Pager 参数 pageSize、prefetchDistance、initialLoadSize 等等
  • remoteMediator :提供 RemoteMediator 的实现类,这里是 PokemonRemoteMediator
  • pagingSourceFactory :是一个 lambda 表达式,在 Kotlin 中可以直接用花括号表示,在花括号内执行加载分页数据,这里直接调用 db.pokemonDao().getPokemon()。
  • 调用 getPokemon() 方法返回的是一个 PagingSource,在 PokemonRemoteMediator 中获取网络分页数据,更新数据库的时候,这里返回的是你请求的网络分页数据

到这里关于 如何自定义 RemoteMediator 实现 数据库 和 网络 加载数据 就分析完了,接下来就是在 ViewModel 中调用 Repository 获取数据。

4. 在 ViewModel 获取数据

在 ViewModel 中调用 Repository 请求数据,通过构建 Pager 加载网络分页数据并更新到数据库中,当数据库更新时,会映射到 UI 上。

PokemonGo/app/src/main/java/com/hi/dhl/pokemon/ui/main/MainViewModel.kt

1
2
kotlin复制代码fun postOfData(): LiveData<PagingData<PokemonItemModel>> =
polemonRepository.featchPokemonList().cachedIn(viewModelScope).asLiveData()

正如你所见在 ViewModel 中就两行代码,结合着 DataBinding 一起使用,在 Activity 或者 Fragment 只需要不到 20 行代码甚至更少。

注意: 在 ViewModel 中的 postOfData 方法中调用了 cachedIn() 方法

Paging3 中的 cachedIn 是什么?它为我们解决了什么问题?

cachedIn() 是 Flow<PagingData> 的扩展方法,主要用来缓存 Flow<PagingData> 返回的内容,当我们在使用 Flow 进行 map 或者 filter 操作后调用 cachedIn() 是为了确保不需要再次触发它们,我们来看一下 cachedIn() 方法的源码。

1
2
3
kotlin复制代码fun <T : Any> Flow<PagingData<T>>.cachedIn(
scope: CoroutineScope
)

正如你所见 cachedIn() 是 Flow<PagingData> 的扩展方法,cachedIn() 方法接受一个 CoroutineScope,CoroutineScope 表示协程的作用域,在 ViewModel 中对应的是 androidx.lifecycle.viewModelScope.,也就意味在作用域内防止不需要再次触发它们,在屏幕旋转的时候也可以复用。

全文到这里就结束了,在这里强烈建议至少体验一次,结合 Kotlin Flow + DataBinding + Jetpack + MVVM

神奇宝贝 (PokemonGo) 基于 Jetpack + MVVM + Repository + Data Mapper + Kotlin Flow 的实战项目,我也正在为 PokemonGo 项目设计更多的场景,也会加入更多的 Jetpack 成员,在 PokemonGo 项目首页增加了更新记录,可以点击下方链接前往查看 PokemonGo 项目的更新记录。

PokemonGo GitHub 地址:https://github.com/hi-dhl/PokemonGo

PokemonGo

结语

公众号开通了:ByteCode , 欢迎小伙伴们前去查看 Android 10 系列源码,Jetpack ,Kotlin ,译文,LeetCode / 剑指 Offer / 国内外大厂算法题 等等一系列文章,如果对你有帮助,请帮我点个 star,感谢!!!,欢迎一起来学习,在技术的道路上一起前进。

正在建立一个最全、最新的 AndroidX Jetpack 相关组件的实战项目 以及 相关组件原理分析文章,目前已经包含了 App Startup、Paging3、Hilt 等等,正在逐渐增加其他 Jetpack 新成员,仓库持续更新,可以前去查看:AndroidX-Jetpack-Practice, 如果这个仓库对你有帮助,请仓库右上角帮我点个赞。

算法

由于 LeetCode 的题库庞大,每个分类都能筛选出数百道题,由于每个人的精力有限,不可能刷完所有题目,因此我按照经典类型题目去分类、和题目的难易程度去排序。

  • 数据结构: 数组、栈、队列、字符串、链表、树……
  • 算法: 查找算法、搜索算法、位运算、排序、数学、……

每道题目都会用 Java 和 kotlin 去实现,并且每道题目都有解题思路、时间复杂度和空间复杂度,如果你同我一样喜欢算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:Leetcode-Solutions-with-Java-And-Kotlin,一起来学习,期待与你一起成长。

Android 10 源码系列

正在写一系列的 Android 10 源码分析的文章,了解系统源码,不仅有助于分析问题,在面试过程中,对我们也是非常有帮助的,如果你同我一样喜欢研究 Android 源码,可以关注我 GitHub 上的 Android10-Source-Analysis,文章都会同步到这个仓库。

  • 0xA01 Android 10 源码分析:APK 是如何生成的
  • 0xA02 Android 10 源码分析:APK 的安装流程
  • 0xA03 Android 10 源码分析:APK 加载流程之资源加载
  • 0xA04 Android 10 源码分析:APK 加载流程之资源加载(二)
  • 0xA05 Android 10 源码分析:Dialog 加载绘制流程以及在 Kotlin、DataBinding 中的使用
  • 0xA06 Android 10 源码分析:WindowManager 视图绑定以及体系结构
  • 0xA07 Android 10 源码分析:Window 的类型 以及 三维视图层级分析
  • 更多……

Android 应用系列

  • 为数不多的人知道的 Kotlin 技巧以及 原理解析
  • Jetpack 最新成员 AndroidX App Startup 实践以及原理分析
  • Jetpack 成员 Paging3 实践以及源码分析(一)
  • Jetpack 新成员 Paging3 网络实践及原理分析(二)
  • Jetpack 新成员 Hilt 实践(一)启程过坑记
  • Jetpack 新成员 Hilt 实践之 App Startup(二)进阶篇
  • Jetpack 新成员 Hilt 与 Dagger 大不同(三)落地篇
  • 全方面分析 Hilt 和 Koin 性能
  • 神奇宝贝(PokemonGo) 眼前一亮的 Jetpack + MVVM 极简实战
  • Google 推荐在 MVVM 架构中使用 Kotlin Flow

精选译文

目前正在整理和翻译一系列精选国外的技术文章,不仅仅是翻译,很多优秀的英文技术文章提供了很好思路和方法,每篇文章都会有译者思考部分,对原文的更加深入的解读,可以关注我 GitHub 上的 Technical-Article-Translation,文章都会同步到这个仓库。

  • [译][Google工程师] 刚刚发布了 Fragment 的新特性 “Fragment 间传递数据的新方式” 以及源码分析
  • [译][Google工程师] 详解 FragmentFactory 如何优雅使用 Koin 以及部分源码分析
  • [译][2.4K Start] 放弃 Dagger 拥抱 Koin
  • [译][5k+] Kotlin 的性能优化那些事
  • [译] 解密 RxJava 的异常处理机制
  • [译][1.4K+ Star] Kotlin 新秀 Coil VS Glide and Picasso
  • 更多……

工具系列

  • 为数不多的人知道的 AndroidStudio 快捷键(一)
  • 为数不多的人知道的 AndroidStudio 快捷键(二)
  • 关于 adb 命令你所需要知道的
  • 10分钟入门 Shell 脚本编程
  • 基于 Smali 文件 Android Studio 动态调试 APP
  • 解决在 Android Studio 3.2 找不到 Android Device Monitor 工具

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

给我半首歌的时间,给你说明白Immutable List

发表于 2020-07-27

先看再点赞,给自己一点思考的时间,微信搜索【沉默王二】关注这个靠才华苟且的程序员。
本文 GitHub github.com/itwanger 已收录,里面还有一线大厂整理的面试题,以及我的系列文章。

Immutable List,顾名思义,就是,啥,不明白 Immutable 是什么意思?一成不变的意思,所以 Immutable List 就是一个不可变的 List 类,这意味着该 List 声明后,它的内容就是固定的,不可增删改的。

如果对不可变类比较陌生的话,可以先点击下面的链接查看我之前写的另外一篇文章。

这次要说不明白immutable类,我就怎么地

如果尝试对 List 中的元素进行增加、删除或者更新,就会抛出 UnsupportedOperationException 异常。

另外,Immutable List 中的元素是非 null 的,如果使用 null 来创建 Immutable List,则会抛出 NullPointerException;如果尝试在 Immutable List 中添加 null 元素,则会抛出 UnsupportedOperationException。

那 Immutable List 有什么好处呢?

  • 它是线程安全的;
  • 它是高效的;
  • 因为它是不可变的,就可以像 String 一样传递给第三方类库,不会发生任何安全问题。

那接下来,我们来看一下,如何创建 Immutable List。注意,源码是基于 JDK14 的。

01、借助原生 JDK

Collections 类的 unmodifiableList() 方法可以创建一个类似于 Immutable List 的 UnmodifiableList 或者 UnmodifiableRandomAccessList,都是不可修改的。

1
2
3
4
5
java复制代码public static <T> List<T> unmodifiableList(List<? extends T> list) {  
    return (list instanceof RandomAccess ?
            new Collections.UnmodifiableRandomAccessList<>(list) :
            new Collections.UnmodifiableList<>(list));
}

来看一下使用方法:

1
2
java复制代码List<String> list = new ArrayList<>(Arrays.asList("沉默王二", "沉默王三", "沉默王四"));  
List<String> unmodifiableList = Collections.unmodifiableList(list);

我们尝试往 unmodifiableList 中添加元素“沉默王五”:

1
java复制代码unmodifiableList.add("沉默王五");

运行后会抛出 UnsupportedOperationException 异常:

1
2
3
复制代码Exception in thread "main" java.lang.UnsupportedOperationException  
    at java.base/java.util.Collections$UnmodifiableCollection.add(Collections.java:1062)
    at com.cmower.mkyong.immutablelist.ImmutableListDemo.main(ImmutableListDemo.java:16)

02、借助 Java 9

Java 9 的时候,List 类新增了一个 of() 静态工厂方法,可以用来创建不可变的 List。先来看一下源码:

1
2
3
java复制代码static <E> List<E> of(E e1, E e2, E e3) {  
    return new ImmutableCollections.ListN<>(e1, e2, e3);
}

of() 方法有很多变体,比如说:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码static <E> List<E> of(E e1) {  
        return new ImmutableCollections.List12<>(e1);
    }
static <E> List<E> of(E e1, E e2) {
        return new ImmutableCollections.List12<>(e1, e2);
    }
static <E> List<E> of(E e1, E e2, E e3, E e4) {
    return new ImmutableCollections.ListN<>(e1, e2, e3, e4);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) {
    return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
    return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
            e6, e7, e8, e9, e10);
}

该方法的设计者也挺有意思的,of() 方法的参数,从 0 到 10 都有一个相同签名的重载方法。

甚至当参数是可变的时候,使用 switch 语句对参数的个数进行了判断,然后调用不同的重载方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码static <E> List<E> of(E... elements) {  
    switch (elements.length) { // implicit null check of elements
        case 0:
            @SuppressWarnings("unchecked")
            var list = (List<E>) ImmutableCollections.ListN.EMPTY_LIST;
            return list;
        case 1:
            return new ImmutableCollections.List12<>(elements[0]);
        case 2:
            return new ImmutableCollections.List12<>(elements[0], elements[1]);
        default:
            return new ImmutableCollections.ListN<>(elements);
    }
}

不管是 ImmutableCollections.List12 还是 ImmutableCollections.ListN,它们都是 final 的,并且继承了 AbstractImmutableList,里面的元素也是 final 的。

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
java复制代码static final class List12<E> extends ImmutableCollections.AbstractImmutableList<E>  
        implements Serializable {

    @Stable
    private final E e0;

    @Stable
    private final E e1;
}

static final class ListN<E> extends ImmutableCollections.AbstractImmutableList<E>
        implements Serializable {

    // EMPTY_LIST may be initialized from the CDS archive.
    static @Stable List<?> EMPTY_LIST;

    static {
        VM.initializeFromArchive(ImmutableCollections.ListN.class);
        if (EMPTY_LIST == null) {
            EMPTY_LIST = new ImmutableCollections.ListN<>();
        }
    }

    @Stable
    private final E[] elements;
}

好了,来看一下使用方法吧:

1
2
java复制代码final List<String> unmodifiableList = List.of("沉默王二", "沉默王三", "沉默王四");  
unmodifiableList.add("沉默王五");

ImmutableCollections 的内部类 ListN 或者 List12 同样不可修改,使用 add() 方法添加元素同样会在运行时抛出异常:

1
2
3
4
复制代码Exception in thread "main" java.lang.UnsupportedOperationException  
    at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:73)
    at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:77)
    at com.cmower.mkyong.immutablelist.ImmutableListDemo.main(ImmutableListDemo.java:20)

03、借助 Guava

Guava 工程包含了若干被 Google 的 Java 项目广泛依赖的核心库,例如:集合 [collections] 、缓存 [caching] 、原生类型支持 [primitives support] 、并发库 [concurrency libraries] 、通用注解 [common annotations] 、字符串处理 [string processing] 、I/O 等等。 所有这些工具每天都在被 Google 的工程师应用在产品服务中。

在实际的项目实战当中,Guava 类库的使用频率真的蛮高的,因此我们需要在项目中先引入 Guava 的 Maven 依赖。

1
2
3
4
5
复制代码<dependency>  
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.1-jre</version>
</dependency>

Guava 定了一个 ImmutableList 类,它的声明方式如下所示:

1
2
3
4
5
java复制代码@GwtCompatible(serializable = true, emulated = true)  
@SuppressWarnings("serial") // we're overriding default serialization
public abstract class ImmutableList<E> extends ImmutableCollection<E>
    implements List<E>, RandomAccess {
}

它的类结构关系如下所示:

1
2
3
4
java复制代码java.lang.Object  
  ↳ java.util.AbstractCollection
      ↳ com.google.common.collect.ImmutableCollection
          ↳ com.google.common.collect.ImmutableList

ImmutableList 类的 copyOf() 方法可用于创建一个不可变的 List 对象:

1
2
3
java复制代码List<String> list = new ArrayList<>(Arrays.asList("沉默王二", "沉默王三", "沉默王四"));  
List<String> unmodifiableList = ImmutableList.copyOf(list);
unmodifiableList.add("沉默王五");

ImmutableList 同样不允许添加元素,add() 方法在执行的时候会抛出 UnsupportedOperationException 异常:

1
2
3
复制代码Exception in thread "main" java.lang.UnsupportedOperationException  
    at com.google.common.collect.ImmutableCollection.add(ImmutableCollection.java:244)
    at com.cmower.mkyong.immutablelist.ImmutableListDemo.main(ImmutableListDemo.java:25)

ImmutableList 类的 of() 方法和 Java 9 的 of() 方法类似,同样有很多相同签名的重载方法,使用方法也完全类似:

1
java复制代码List<String> unmodifiableList = ImmutableList.of("沉默王二", "沉默王三", "沉默王四");

ImmutableList 类还提供了 builder 模式,既可以在创建的时候添加元素,也可以基于已有的 List 创建,还可以将两者混合在一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码ImmutableList<String> iList = ImmutableList.<String>builder()  
        .add("沉默王二", "沉默王三", "沉默王四")
        .build();

List<String> list = List.of("沉默王二", "沉默王三", "沉默王四");
ImmutableList<String> iList = ImmutableList.<String>builder()
        .addAll(list)
        .build();

List<String> list = List.of("沉默王二", "沉默王三", "沉默王四");
ImmutableList<String> iList = ImmutableList.<String>builder()
        .addAll(list)
        .add("沉默王五")
        .build();

04、Collections.unmodifiableList() 和 ImmutableList 有什么区别?

Collections.unmodifiableList() 基于原有的 List 创建了一个不可变的包装器,该包装器是不可修改的,但是,我们可以通过对原有的 List 进行修改,从而影响到包装器,来看下面的示例:

1
2
3
4
5
6
7
8
9
java复制代码List<String> list = new ArrayList<>();  
list.add("沉默王二");

List<String> iList = Collections.unmodifiableList(list);

list.add("沉默王三");
list.add("沉默王四");

System.out.println(iList);

程序输出的结果如下所示:

1
复制代码[沉默王二, 沉默王三, 沉默王四]

但如果我们通过 ImmutableList 类创建一个不可变 List,原有 List 的改变并不会影响到 ImmutableList。

1
2
3
4
5
6
7
8
9
java复制代码List<String> list = new ArrayList<>();  
list.add("沉默王二");

ImmutableList<String> iList = ImmutableList.copyOf(list);

list.add("沉默王三");
list.add("沉默王四");

System.out.println(iList);

程序输出的结果如下所示:

1
复制代码[沉默王二]

这是因为 ImmutableList 是在原有的 List 上进行了拷贝。


我是沉默王二,一枚有颜值却靠才华苟且的程序员。关注即可提升学习效率,别忘了三连啊,点赞、收藏、留言,我不挑,奥利给。

注:如果文章有任何问题,欢迎毫不留情地指正。

如果你觉得文章对你有些帮助欢迎微信搜索「沉默王二」第一时间阅读,回复「小白」更有我肝了 4 万+字的 Java 小白手册 2.0 版,本文 GitHub github.com/itwanger 已收录,欢迎 star。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

HashMap 容量大小的问题-为什么长度都是2的幂? 前言

发表于 2020-07-27

前言

在之前的文章 我分析过HashMap 初始化容量的问题 不清楚的可以看这个。

经过这篇文章 我们知道了 HashMap是什么时候 设置容量大小的,容量大小和容量的阀值 是怎么计算的,但是有的小伙伴 包括我 可能对一点比较好奇 为什么默认的容量是16 而且计算是自己容量的时候,最终计算出来的容量也是2的幂次方?可能 有的小伙伴知道 这个是为了 降低哈希碰撞率,那是为什么呢?那我们今天就来聊一聊

分析

容量计算

1
2
3
4
5
6
7
8
9
10
11
12
复制代码    /**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

照顾下 没看之前的文章的小伙伴 还是回顾下

这个方法是Hashmap里面去计算初始容量需要用的 其目的就是获取一个大于当前传入的cap值的2的最小幂次方的数值。

看完这句话 感觉好拗口的 ,又是大于 又是小于的 比较懵逼,没事 那我们给出2个栗子:

  • cap:10 这个方法的到值是16 也就是2的4次方
  • cap:17 这个方法的到值是32 也就是2的5次方
  • cap:1000 这个方法的到值是1024 也就是2的10次方

我相信 看到了这个我相信 小伙伴们 一定知道了吧~

hash位置计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
复制代码    public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
...
}

上面是我截取的 计算HashMap 位置的代码

我们知道 HashMap 里面计算卡槽的位置 是经过了这么几步:

hash

首先 我们调用hash这个方法,这个方法 就是回去key的hascode值 然后和hashcode值的右移16位后 的值 做异或处理

为什么要这么处理呢?

首先我们知道异或【^】的逻辑运算的规则是 ==相同为0 不同为1== 即:0 ^ 0=0,1 ^ 1=0,1 ^ 0=1,0 ^ 1=1

与【&】运算的规则 ==2者都为1 时候结果为1 否则为0== 即:0&0=0, 1&1=1 ,1&0=0 ,0^1=0

顺便也会回顾下 或运算符【|】 规则是 ==只有有1 那结果就是1== 即:0&0=0,1&1=1 ,1&0=1 ,0^1=1

记住下 上2个逻辑运算符 方法里面会涉及到

那我们再来回顾下 (h = key.hashCode()) ^ (h >>> 16) ,h >>> 16 这个操作就是 将二进制位往右移16位 空位的用0补足,知道了这个 我们来举个小demo 来看下 这个是要做什么,16为的花 我要写很长一段数组 那我就右移4位吧,举例说明下:

如果key的hashCode 的二进制值是:1011 0011 那么>>> 4的结果就是0000 1011 那么2者相【^】异或的结果是:

1011 0011

0000 1011

结果: 1011 1000

看到这样的结果是 高4位的数值 其实没有变化 低4位的数值 是有变化的,这样做的目的是把高4位的影响 降低到低4位中,保证hash后面hash值 在计算位置的时候 减少hash的冲突,具体 可以看下 英文的注释,翻译过来大概就是这个意思!

(n - 1) & hash

这个是计算位置的方法 hash 值就是上个方法中 传入过来的

如果这个是的hash值是 1011 1000 我们的n值就是16,那么就算结果将是这样的
hash: 1011 1000

n-1 : 0000 1111

结果: 0000 1000 10进制数值是:8

如果这个时候改变hash值是 1011 1100 那么就算结果将是这样的
hash: 1011 1100

n-1 : 0000 1111

结果: 0000 1100 10进制数值是:12

这个时候 我们看到 随着我们的hash值的不同 的到的index 也是不同的 ,这样能保证hash值 能均分的分配

但是如果这个是 我们的n长度不是2的幂次方,比如是10 ,那么计算结果是这样的
hash: 1011 1000

n-1 : 0000 1001

结果: 0000 1000 10进制数值是:8

这个时候 我们还是修改 hash值是 1011 1100 那么就算结果将是这样的
hash: 1011 1100

n-1 : 0000 1001

结果: 0000 1000 10进制数值是:8

这个时候 我们发现 虽然hash值修改了 但是 我们计算得到的index 还是相同的,就那上面这个例子 如果hash值是 1011 1000, 1011 1100, 1011 1110 计算得到的结果 都是 0000 1000 index 都是8 这样会提高Hash的冲突率,这显然不是我们想要的。

看到这里 你是否 知道了 为什么都是2的幂次方了么, 因为2的幂次方减掉1后, 二进制的值的 低位都是1,这样就保证了和Hash值 相与【&】后结果 低位都是被保留下来的 这样就可以避免不同的Hash值传入进来 被分配到 同一个卡槽位置 去存储。

结论

通过以上的分析 你是否清楚了呢。不清楚的话 多看看 多想想 ,设计是如此的其妙!一个细节都是那么的优秀,值得我们去深究 和学习。

废话不多说 ,总结一下 hashMap中容量的数值都是2的幂次方 是为了降低hash的冲突,那位什么能降低hash的冲突呢,是因为2的幂次方-1 后的数组的二进制 的低位 全部都是1,这样保证了和hash值与【&】之后 能够完整的保留hash值的低位 这样就避免了不同的hash值过来被分配到一样的hash卡槽中!

总计完毕!!!!

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

Python数据分析之股票数据

发表于 2020-07-27

最近股市比较火,我7月初上车了,现在已经下了。中间虽然吃了点肉,但下车的时候都亏进去了,最后连点汤都没喝着。

这篇文章我们就用python对股票数据做个简单的分析。数据集是从1999年到2016年上海证券交易所的1095只股票。


共1000个文件。

我们的分析思路大致如下:

  • 每年新发股票数
  • 目前市值最大的公司有哪些
  • 股票一段时间的涨跌幅如何
  • 牛市的时候,个股表现如何

首先导入模块

1
2
3
4
5
6
7
8
复制代码import pandas as pd
import numpy as np
import os
import seaborn as sns
import matplotlib.pyplot as plt
# 绘图显示中文
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

用pandas读文件

1
2
3
4
5
6
7
8
9
复制代码file_list = os.listdir('./data/a-share/')

pieces = []
for file_name in file_list:
path = './data/a-share/%s' % file_name
file = pd.read_csv(path, encoding ='gb2312')
pieces.append(file)

shares = pd.concat(pieces)

使用read_csv读文件的时候需要指定文件编码encoding ='gb2312'。将各个文件的DataFrame合并后,将索引重置一下,并预览一下数据

1
2
复制代码shares.reset_index(inplace=True, drop=True)
shares.head()


这里我们最关注的列是日期、代码、简称、收盘价。

按照分析思路,我们首先来看看上市公司的总数

1
复制代码len(shares['代码'].unique())

对股票代码去重、计数可以看到一共有1095家上市公司。那我们再看看每年新增的上市公司有多少家

1
2
3
4
5
6
复制代码# 计算每只股票的最早交易时间(即:上市时间)
shares_min_date = shares.groupby('简称').agg({'日期':'min'})
shares_min_date['上市年份'] = shares_min_date['日期'].apply(lambda x: str(x)[:4])

# 每年上市公司的数量
shares_min_date.groupby('上市年份').count().plot()


可以看到,多的时候每年60-80家,而05年-13年这段时间上市后的公司特别少,尤其是13年只有1家,原因是13年暂停了IPO。

下面我们再来看看数据集中最新的时间点(2016-06-08),市值较大的公司有哪些

1
2
3
4
5
6
7
复制代码shares_market_value = shares[shares['日期'] == '2016-06-08'][['简称', '总市值(元)']].sort_values(by='总市值(元)', ascending=False)

# 市值最大的公司 top10
tmp_df = shares_market_value.head(10)

# 画图
sns.barplot(x=tmp_df['总市值(元)'], y=tmp_df['简称'])


截至16年6月8号,工商银行(爱存不存)的市值最高1.5万亿,不愧是宇宙第一大行。并且能发现市值前十的公司大部分是银行。

下面再来看看,从11.06.09 - 16.06.085年时间里个股涨跌情况。起点选11.06.09的原因是这一天包含了900左右只股票,样本较大。然后,我们抽取这两天股票的收盘价,计算涨跌幅

1
2
3
4
5
6
复制代码shares_110609 = shares[shares['日期'] == '2011-06-09'][['代码', '简称', '收盘价(元)']]
shares_160609 = shares[shares['日期'] == '2016-06-08'][['代码', '收盘价(元)']]

# 按照股票代码将2天数据关联
shares_price = shares_110609.merge(shares_160609, on='代码')
shares_price


一共有879只股票

1
2
复制代码# 多少家股票是上涨的
shares_price[shares_price['涨跌幅(%)'] > 0].count()

1
2
复制代码# 多少家股票是上涨的
shares_price[shares_price['涨跌幅(%)'] < 0].count()


可以看到,上涨的股票627只,占比71%。那我们再来看看,上涨的股票,涨幅分布情况

1
2
3
4
5
6
7
8
9
复制代码bins = np.array([0, 40, 70, 100, 1700])
# 股价上涨的公司
shares_up = shares_price[shares_price['涨跌幅(%)'] > 0]
# 按涨幅进行分组
shares_up['label'] = pd.cut(shares_up['涨跌幅(%)'], bins)
# 分组统计
up_label_count = shares_up[['label', '代码']].groupby('label').count()
up_label_count['占比'] = up_label_count['代码'] / up_label_count.sum().values
sns.barplot(x=up_label_count['占比'], y=up_label_count.index)


涨幅分布还是比较极端的,虽然上涨的股票总体比较高,但上涨的股票中有30%只股票涨幅不足40%,也就是平均一年涨8%,如果理财年收益10%算及格的话,8%明显偏低了。再加上跌的股票,收益率低于10%的股票大于50%,所以股市的钱也不是那么好挣的。

当然也有踩狗屎运的时候,比如买到了下面这些股票并且长期持有

1
2
3
复制代码# 涨幅最大的公司
tmp_df = shares_up.sort_values(by='涨跌幅(%)', ascending=False)[:8]
sns.barplot(y=tmp_df['简称'], x=tmp_df['涨跌幅(%)'])


像金证股份持有5年后可以翻16倍。

同样的方式,我们可以看看股票跌幅分布


因为代码类似,这里就不贴了。从数据上将近70%的股票5年后跌幅在0-40%的区间。

最后一个有意思的数据,我们看看牛市的时候个股涨跌是怎么样的。我们选择14.06.30和15.06.08这两天个股的涨跌情况。分析思路跟上面类似,我就直接说数据了。

牛市期间99.6%的股票都是涨的,也就是说个股基本都在上涨。来看看涨幅分布


可以看到,86%只股票翻了一番,所以牛市来了,基本上闭着眼选股都能挣钱。也不知道这种大牛市什么时候能再来一次,当然了,牛市来了能不能把握住是个大问题。

我的分析就到这里了,其实分析有意思的数据还有很多,比如结合一些市盈率等其他维度进行分析,有兴趣的朋友可以自行探索,我觉得还有一个更有挑战性的分析是预测个股的走势,虽然实践上不可行,但从学习角度来看还是挺值得研究的,如果大家点赞较多,我下周考虑写一下。

数据和源码已经打包,公众号回复关键字股票即可。

欢迎公众号 「渡码」 输出别地儿看不到的干货。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

VAVR:颠覆你的 Java 体验

发表于 2020-07-26

何方神圣?

众所周知, Java8 在一定程度上支持了函数式编程,但标准库提供的函数式 API 不是很完备和友好。

为了更好的进行函数式编程,我们就不得不借助于第三方库,而 VAVR 就是这方面的佼佼者,它可以有效减少代码量并提高代码质量。

VAVR 可不是默默无闻之辈,它的前身是发布于 2014 年的 Javaslang,目前在 github 上有着近 4k 的 star。

看到这儿,很多人就说我标题党了,一个 Java 库还来颠覆 Java ?

这可不不是我玩震惊体,打开 VAVR 的官网 ,它的首页就用加粗字体写着 「vavr - turns java™ upside down」

这翻译过来不就是颠覆 Java 吗?

食用指南

阅读本文需要读者对 Java8 的 lambda 语法和常用 API 有一定的了解。

由于是一篇框架的介绍文(地推 ing),为了避免写成官方文档的翻译,本文会有一些约束

  • 不会穷尽所有特性和 API,仅做抛砖引玉
  • 不会深入到源码细节

关于示例代码,基本会以单元测试的形式给出并保证运行通过

注:本文使用的 VAVR 版本为 0.10.3,JDK 版本为 11。

先来个概览

集合,全新的开始

不得不说 Java8 的集合库引入 Stream 以后确实很好用,但也正是因为使用了 Stream,不得不写很多样板代码,反而降低了不少体验。

1
2
3
4
5
6
复制代码// of 方法是 Java9 开始提供的静态工厂
java.util.List.of(1, 2, 3, 4, 5)
.stream()
.filter(i -> i > 3)
.map(i -> i * 2)
.collect(Collectors.toList());

而且 Java 的集合库本身是可变的,显然违背了函数式编程的基本特性 - 不可变,为此 VAVR 设计了一套全新的集合库,使用体验无限接近于 Scala。

更简洁的 API

1
2
3
复制代码io.vavr.collection.List.of(1, 2, 3, 4, 5)
.filter(i -> i > 3)
.map(i -> i * 2);

往集合追加数据会产生新的集合,从而保证不可变

1
2
3
4
5
6
7
复制代码var list = io.vavr.collection.List.of(1, 2)
var list2 = list
.append(List.of(3, 4))
.append(List.of(5, 6))
.append(7);
// list = [1, 2]
// list2 = [1, 2, 3, 4, 5, 6]

强大的兼容性,可以非常方便的与 Java 标准集合库进行转换

1
2
3
4
5
复制代码var javaList = java.util.List.of(1, 2, 3);
java.util.List<Integer> javaList2 = io.vavr.collection.List.ofAll(javaList)
.filter(i -> i > 1)
.map(i -> i * 2)
.toJavaList();

再来看一个稍微复杂一点的例子:过滤一批用户中已成年的数据,按照年龄对其分组,每个分组只展示用户的姓名。

1
2
3
4
5
6
7
8
9
复制代码/**
* 用户信息
*/
@Data
class User {
private Long id;
private String name;
private Integer age;
}

先用 Java 标准集合库来实现这个需求,可以看见 collect(...) 这一长串嵌套是真的很难受

1
2
3
4
5
复制代码public Map<Integer, List<String>> userStatistic(List<User> users) {
return users.stream()
.filter(u -> u.getAge() >= 18)
.collect(Collectors.groupingBy(User::getAge, Collectors.mapping(User::getName, Collectors.toList())));
}

再来看看 VAVR 的实现,是不是更简洁,更直观?

1
2
3
4
5
复制代码public Map<Integer, List<String>> userStatistic(List<User> users) {
return users.filter(u -> u.getAge() >= 18)
.groupBy(User::getAge)
.mapValues(usersGroup -> usersGroup.map(User::getName));
}

VAVR 的集合库提供了更多 Functional 的 API,比如

  • take(Integer) 取前 n 个值
  • tail() 取除了头结点外的集合
  • zipWithIndex() 使得便利时可以拿到索引(不用 fori)
  • find(Predicate) 基于条件查询值,在 Java 标准库得使用 filter + findFirst 才能实现
  • …..

虽然代码实例都是用的 List,但是以上特性在 Queue、Set、Map 都可以使用,都支持与 Java 标准库的转换。

元组,Java 缺失的结构

熟悉 Haskell、Scala 的同学肯定对「元组」这个数据结构不陌生。

元组类似一个数组,可以存放不同类型的对象并维持其类型信息,这样在取值时就不用 cast 了。

1
2
3
4
5
6
7
复制代码// scala 的元组,用括号构建
val tup = (1, "ok", true)

// 按索引取值,执行对应类型的操作
val sum = tup._1 + 2 // int 加法
val world = "hello "+tup._2 // 字符串拼接
val res = !tup._3 // 布尔取反

当然,Java 并没有原生的语法支持创建元组,标准库也没有元组相关的类。

不过,VAVR 通过泛型实现了元组,通过 Tuple 的静态工厂,我们可以非常轻易的创建元组( 配合 Java10 的 var 语法简直不要太美好)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
复制代码import io.vavr.Tuple;

public TupleTest {

@Test
public void testTuple() {
// 一元组
var oneTuple = Tuple.of("string");
String oneTuple_1 = oneTuple._1;

// 二元组
var twoTuple = Tuple.of("string", 1);
String twoTuple_1 = twoTuple._1;
Integer twoTuple_2 = twoTuple._2;

// 五元组
var threeTuple = Tuple.of("string", 2, 1.2F, 2.4D, 'c');
String threeTuple_1 = threeTuple._1;
Integer threeTuple_2 = threeTuple._2;
Float threeTuple_3 = threeTuple._3;
Double threeTuple_4 = threeTuple._4;
Character threeTuple_5 = threeTuple._5;
}
}

如果没有 var,就得写出下面这样冗长的变量定义

1
复制代码Tuple5<String, Integer, Float, Double, Character> tuple5 = Tuple.of("string", 2, 1.2F, 2.4D, 'c');

目前,VAVR 最多支持构造八元组,也就是支持最多 8 个类型,而不是最多 8 个值。

当元组和「模式匹配」的配合使用时,那更是强大的一塌糊涂

PS:虽然现在提模式匹配有点早了(后面会再遇见的),不过我们仍然可以提前感受一下

1
2
3
4
5
6
7
复制代码var tup = Tuple.of("hello", 1);

// 模式匹配
Match(tup).of(
Case($Tuple2($(is("hello")), $(is(1))), (t1, t2) -> run(() -> {})),
Case($Tuple2($(), $()),(t1, t2) ->run(() -> {}))
);

上面的代码其实就等同于 if…else

1
2
3
4
5
6
复制代码// 等同于 if...else
if (tup._1.equalas("hello") && tup._2 == 1) {
// ... do something
} else {
// ... do something
}

除了 Option,还有 Try、Either、Future……

Java8 引入了 Optional 去解决臭名昭著的 NullPointerException,而 VAVR 也有一个类似的工具 - Option,但它却有着不同的设计。

除了 Option 外,VAVR 还实现了 Try、Either、Future 等函数式的结构,它们都是 Java 标准库没有但非常强大的工具。

Option

Option 与 Java 标准库的 Optional 很相似,都代表着一个可选值,但是两者的设计却是大不相同的。(VAVR 的 Option 设计和 Scala 更接近)

在 VAVR 中,Option 是一个 interface,它的具体实现有 Some 和 None

  • Some: 代表有值
  • None: 代表没有值

你可以通过下面的单元测试进行验证

1
2
3
4
5
6
7
8
9
10
复制代码@Test
public void testOption() {
// 通过 of 工厂方法构造
Assert.assertTrue(Option.of(null) instanceof Option.None);
Assert.assertTrue(Option.of(1) instanceof Option.Some);

// 通过 none 或 some 构造
Assert.assertTrue(Option.none() instanceof Option.Some);
Assert.assertTrue(Option.some(1) instanceof Option.Some);
}

而对于 java.util.Optional 来说,无论通过什么方式构造,都是同一个类型。

1
2
3
4
5
6
7
复制代码@Test
public void testOptional() {
Assert.assertTrue(Optional.ofNullable(null) instanceof Optional);
Assert.assertTrue(Optional.of(1) instanceof Optional);
Assert.assertTrue(Optional.empty() instanceof Optional);
Assert.assertTrue(Optional.ofNullable(1) instanceof Optional);
}

为什么两者会有这样的设计区别呢?

本质上来讲就是对 「Option 的作用就是使得对 null 的计算保证安全吗?」这一问题的不同回答。

下面的的两个测试方法,同样的逻辑,用 Option 和 Optional 却得出了不同的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
复制代码@Test
public void testWithJavaOptional() {
// Java Optional
var result = Optional.of("hello")
.map(str -> (String) null)
.orElseGet(() -> "world");

// result = "world"
Assert.assertEquals("word", result);
}

@Test
public void testWithVavrOption() {
// Vavr Option
var result = Option.of("hello")
.map(str -> (String) null)
.getOrElse(() -> "world");

// result = null
Assert.assertNull(result);
}

在 VAVR 的测试代码中,通过 Optional.of("hello") 实际上得到了一个 Some("hello") 对象。

随后调用 map(str -> (String)null) 返回的仍然是一个 Some 对象(Some 代表有值),所以最终的 result = null,而不是 getOrElse(() -> "world") 返回的 world 字符串。

在 Java 的测试代码中,调用 map(str -> null) 时,Optional 就已经被切换为了 Optional.empty,所以最终就返回了 orElseGet(() -> "world") 的结果。

这也是函数式开发者们批判 java.util.Optional 设计的一个点

除了设计上的区别外, io.vavr.control.Option 比 java.util.Optional 也要多出更多友好的 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复制代码
@Test
public void testVavrOption() {
// option 直接转为 List
List<String> result = Option.of("vavr hello world")
.map(String::toUpperCase)
.toJavaList();
Assert.assertNotNull(result);
Assert.assertEquals(1, result.size());
Assert.assertEquals("vavr hello world", result.iterator().next());

// exists(Function)
boolean exists = Option.of("ok").exists(str -> str.equals("ok"));
Assert.assertTrue(exists);

// contains
boolean contains = Option.of("ok").contains("ok");
Assert.assertTrue(contains);
}

考虑到与标准库的兼容,Option 可以很方便的与 Optional 进行互转

1
2
3
复制代码Option.of("toJava").toJavaOptional();

Option.ofOptional(Optional.empty());

Try

Try 和 Option 类似,也类似于一个「容器」,只不过它容纳的是可能出错的行为,你是不是马上就想到了 try..catch 结构?

1
2
3
4
5
6
7
复制代码try {
//..
} catch (Throwable t) {
//...
} finally {
//....
}

通过 VAVR 的 Try,也能实现另外一种更 functional 的 try…catch。

1
2
3
4
5
6
7
8
9
10
11
复制代码/**
* 输出
* failure: / by zero
* finally
*/
Try.of(() -> 1 / 0)
.andThen(r -> System.out.println("and then " + r))
.onFailure(error -> System.out.println("failure" + error.getMessage()))
.andFinally(() -> {
System.out.println("finally");
});

Try 也是个接口, 具体的实现是 Success 或 Failure

  • Success:代表执行没有异常
  • Failure:代表执行出现异常

和 Optoin 一样,也可以通过 of 工厂方法进行构建

1
2
3
4
5
6
7
8
9
10
复制代码@Test
public void testTryInstance() {
// 除以 0 ,构建出 Failure
var error = Try.of(() -> 0 / 0);
Assert.assertTrue(error instanceof Try.Failure);

// 合法的加法,构建出 Success
var normal = Try.of(() -> 1 + 1);
Assert.assertTrue(normal instanceof Try.Success);
}

通过 Try 的 recoverWith 方法,我们可以很优雅的实现降级策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
复制代码@Test
public void testTryWithRecover() {
Assert.assertEquals("NPE", testTryWithRecover(new NullPointerException()));
Assert.assertEquals("IllegalState", testTryWithRecover(new IllegalStateException()));
Assert.assertEquals("Unknown", testTryWithRecover(new RuntimeException()));
}

private String testTryWithRecover(Exception e) {
return (String) Try.of(() -> {
throw e;
})
.recoverWith(NullPointerException.class, Try.of(() -> "NPE"))
.recoverWith(IllegalStateException.class, Try.of(() -> "IllegalState"))
.recoverWith(RuntimeException.class, Try.of(() -> "Unknown"))
.get();
}

对于 Try 的计算结果,可以通过 map 进行转换,也可以很方便的与 Option 进行转换。

还可以使用 map 对结果进行转换,并且与 Option 进行交互

1
2
3
4
5
6
7
8
复制代码@Test
public void testTryMap() {
String res = Try.of(() -> "hello world")
.map(String::toUpperCase)
.toOption()
.getOrElse(() -> "default");
Assert.assertEquals("HELLO WORLD", res);
}

Future

这个 Future 可不是 java.util.concurrent.Future,但它们都是对异步计算结果的一个抽象。

vavr 的 Future 提供了比 java.util.concurrent.Future 更友好的回调机制

  • onFailure 失败的回调
  • onSuccess 成功的回调
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
复制代码@Test
public void testFutureFailure() {
final var word = "hello world";
io.vavr.concurrent.Future
.of(Executors.newFixedThreadPool(1), () -> word)
.onFailure(throwable -> Assert.fail("不应该走到 failure 分支"))
.onSuccess(result -> Assert.assertEquals(word, result));
}

@Test
public void testFutureSuccess() {
io.vavr.concurrent.Future
.of(Executors.newFixedThreadPool(1), () -> {
throw new RuntimeException();
})
.onFailure(throwable -> Assert.assertTrue(throwable instanceof RuntimeException))
.onSuccess(result -> Assert.fail("不应该走到 success 分支"));
}

它也可以和 Java 的 CompleableFuture 互转

1
2
3
复制代码Future.of(Executors.newFixedThreadPool(1), () -> "toJava").toCompletableFuture();

Future.fromCompletableFuture(CompletableFuture.runAsync(() -> {}));

其他

最后再来简单过一下 Either 和 Lazy 吧

  • Either 它表示某个值可能为两种类型中的一种,比如下面的 compute() 函数的 Either 返回值代表结构可能为 Exception 或 String。

通常用 right 代表正确的值(英文 right 有正确的意思)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复制代码public Either<Exception, String> compute() {
//...
}

public void test() {
Either<Exception, String> either = compute();

// 异常值
if (either.isLeft()) {
Exception exception = compute().getLeft();
throw new RuntimeException(exception);
}

// 正确值
if (either.isRight()) {
String result = compute().get();
// ...
}
}
  • Lazy 也是一个容器,他可以延迟某个计算,直到该计算被首次调用,初次调用之后该结果会被缓存,后续调用就可以直接拿到结果。
1
2
3
4
5
复制代码Lazy<Double> lazy = Lazy.of(Math::random);
lazy.isEvaluated(); // = false
lazy.get(); // = 0.123 (random generated)
lazy.isEvaluated(); // = true
lazy.get(); // = 0.123 (memoized)

在 io.vavr.API 中提供了很多静态方法来模拟 Scala 的语法构造 Option、Try 这些结构,但是要结合 Java 的静态导入使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码import static io.vavr.API.*;

@Test
public void testAPI() {
// 构造 Option
var some = Some(1);
var none = None();

// 构造 Future
var future = Future(() -> "ok");

// 构造 Try
var tryInit = Try(() -> "ok");
}

当然这个大写字母开头的函数名有点不符合 Java 的方法命名规范,算是一种 Hack 手段吧。

关于更多细节的内容,有兴趣的可以去查阅官网文档学习

模式匹配:if..else 的克星

这里的模式指的是数据结构的组成模式,在 Scala 中可以直接通过 match 关键字使用模式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复制代码def testPatternMatch(nameOpt: Option[String], nums: List[Int]) = {
/**
* 匹配 Option 的结构
*/
nameOpt match {
case Some(name) => println(s"你好,$name")
case None => println("无名之辈")
}

/**
* 匹配 List 的结构
*/
nums match {
case Nil => println("空列表")
case List(v) => println(s"size=1 $v")
case List(v, v2) => println(s"size=2 $v、 $v2")
case _ => println("size > 2")
}
}

在 Java 中没有模式匹配的概念,自然就没有相关的语法了(switch 可不算)。

不过 VAVR 使用 OOP 的方式实现了了模式匹配,虽然比不了 Scala 原生的体验,但也相当接近了

Java 在 JEP 375: Pattern Matching for instanceof 提案中针对 instanceof 实现了一个模式匹配的特性(预计在 Java15 发布),不过我觉得该特性距离 Scala 的模式匹配还有一段距离

我们来实现一个将 BMI 值格式化成文字描述的需求,先用 Java 的命令式风格来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码public String bmiFormat(double height, double weight) {
double bmi = weight / (height * height);
String desc;
if (bmi < 18.5) {
desc = "有些许晃荡!";
} else if (bmi < 25) {
desc = "继续加油哦!";
} else if (bmi < 30) {
desc = "你是真的稳!";
} else {
desc = "难受!";
}
return desc;
}

接下来再用 VAVR 的模式匹配来重构吧,消灭这些 if..else。

为了让语法体验更友好,最好先通过 static import 导入 API。

1
复制代码import static io.vavr.API.*;

下面是重构后的代码段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码public String bmiFormat(double height, double weight) {
double bmi = weight / (height * height);
return Match(bmi).of(
// else if (bmi < 18.5)
Case($(v -> v < 18.5), () -> "有些许晃荡!"),
// else if (bmi < 25)
Case($(v -> v < 25), () -> "继续加油哦!"),
// else if (bmi < 30)
Case($(v -> v < 30), () -> "你是真的稳!"),
// else
Case($(), () -> "难受!")
);

}
  • Match(…),Case(…),$(…) 都是 io.vavr.API 的静态方法,用于模拟「模式匹配」的语法
  • 最后一个 $() 表示匹配除了上面之外的所有情况

为了便于读者理解,我将各个方法的签名简单列了一下(Case 和 $ 方法有很多重载,就不全列了)

1
2
3
4
5
复制代码public static <T> Match<T> Match(T value) {...}

public static <T, R> Case<T, R> Case(Pattern0<T> pattern, Function<? super T, ? extends R> f) {...}

public static <T> Pattern0<T> $(Predicate<? super T> predicate) {...}

of 是 Match 对象的方法

1
复制代码public final <R> R of(Case<? extends T, ? extends R>... cases) {...}

来,再展示一下自创的语法记忆

1
2
3
4
5
6
7
8
9
10
11
12
13
复制代码匹配一下(这个东西)的结构,是不是下面的情况之一
// Match(XXX).Of(

- 结构和 A 一样,做点什么事情
//Case( $(A), () -> doSomethingA() ),

- 结构和 B 一样,做点什么事情
//Case( $(B), () -> doSomethingB() ),
- .....

- 和上面的结构都不一样,也做点事情
//Case( $(), () -> doSomethingOthers())
//);

当模式匹配和前面提到的 Option、Try、Either、Tuple 结合时,那可是 1 + 1 > 3 的结合。

下面的代码展示了「模式匹配」是如何让 Option 如虎添翼的

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
复制代码import static io.vavr.API.*;
import static io.vavr.Patterns.$None;
import static io.vavr.Patterns.$Some;

public class PatternMatchTest {

@Test
public void testMatchNone() {
// 匹配 None
var noneOpt = Option.none();
Match(noneOpt).of(
Case($None(), r -> {
Assert.assertEquals(Option.none(), r);
return true;
}),
Case($(), this::failed)
);
}

@Test
public void testMatchValue() {
// 匹配某一个值为 Nice 的 Some
var opt2 = Option.of("Nice");
Match(opt2).of(
Case($Some($("Nice")), r -> {
Assert.assertEquals("Nice", r);
return true;
}),
Case($(), this::failed)
);
}

@Test
public void testMatchAnySome() {
// 匹配 Some,值任意
var opt = Option.of("hello world");
Match(opt).of(
Case($None(), this::failed),
Case($Some($()), r -> {
Assert.assertEquals("hello world", r);
return true;
})
);
}

private boolean failed() {
Assert.fail("不应该执行该分支");
return false;
}
}

还有 Try,顺便说一句,有时候 Case 没有返回值的时候, 第二个参数可以用 API.run() 替代

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
33
34
35
36
复制代码import static io.vavr.API.*;
import static io.vavr.Patterns.*;
import static io.vavr.Predicates.instanceOf;

public class PatternMatchTest {

@Test
public void testMatchFailure() {
var res = Try.of(() -> {
throw new RuntimeException();
});
Match(res).of(
// 匹配成功情况
Case($Success($()), r -> run(Assert::fail)),
// 匹配异常为 RuntimeException
Case($Failure($(instanceOf(RuntimeException.class))), r -> true),
// 匹配异常为 IllegalStateException
Case($Failure($(instanceOf(IllegalStateException.class))), r -> run(Assert::fail)),
// 匹配异常为 NullPointerException
Case($Failure($(instanceOf(NullPointerException.class))), r -> run(Assert::fail)),
// 匹配其余失败的情况
Case($Failure($()), r -> run(Assert::fail))
);
}

@Test
public void testMatchSuccess() {
var res = Try.of(() -> "Nice");
Match(res).of(
// 匹配任意成功的情况
Case($Success($()), r -> run(() -> Assert.assertEquals("Nice", r))),
// 匹配任意失败的情况
Case($Failure($()), r -> run(Assert::fail))
);
}
}

现在再回头看看元组的代码,你可以尝试一下自己写写三元组的模式匹配了。

最后

本文只介绍了一些常用的特性,而除此之外,VAVR 还支持 Curring、Memoization、 Partial application 等高级特性,如果想深入的学习可以前往官网了解。

最后,这块砖已经抛出去了,能不能引到你这块玉呢?

广告:

如果你正在找基于 Java9+ 的项目用于学习新特性,我自荐一下 PrettyZoo,

这是一款基于 Java11开发的 zookeeper 桌面客户端,使用了模块化,var 等诸多新特性,欢迎 star、fork、issue。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

这可能是全网最简单的KMP了

发表于 2020-07-23

今天打算为大家讲解一下KMP。

KMP 其实已经念念叨叨挺长时间了,一直没写的原因是我觉得自己可能写不好。与其误人子弟,宁可错失良机。毕竟自己懂是一码事,能讲清楚是另一码事。

所以为了写好这篇文章,我又去参考了很多别的资料。嗯。。我发现网上讲解 KMP 的文章实在是太多了,但大多数看完后还是云里雾里(纵然我已经会了,读对方的文章还是懵逼)。

我希望我的这篇文章能达到的目的是:让小白也能学会KMP。如果届时达到了目的,请帮我进行一次转发。否则,你只需要叉掉即可。

话不多说,我们直接开始。

01、图解分析

KMP 算法常被称为“看毛片算法”,由一个姓K的,一个姓M的,一个姓P 一起提出。是一种由暴力匹配改进的字符串匹配算法。

我看了下网上的 KMP 讲解基本都是由 next匹配表 开始讲起。但是说实话,如果是我第一次看这玩意,你给我讲 next匹配表,我肯定一脸懵逼。所以我打算换一种讲法。

上面说了,KMP 是由暴力匹配改进的字符串匹配算法。那什么是暴力匹配?假若我们的目标串和模式串如下图。(之前在 Sunday 匹配中讲过,所有的字符串匹配算法第一步都是对齐。不管是 暴力匹配,KMP,Sunday,BM 都是一样)

1.jpg

暴力匹配,就是目标串和模式串一个一个的对比。

2.jpg

当A匹配成功,继续开始比对,直到我们遇见一个不匹配的字符。

3.jpg

然后我们调整模式串,从目标串的下一个字符开始匹配(注意,这里是核心)。很遗憾,还是没有匹配成功(A和B)

4.jpg

继续这个步骤:

5.jpg

直到我们完成整个匹配过程:

6.jpg

假若我们目标串长度为m,模式串长度为n。模式串与目标串至少比较m次,又因其自身长度为n,所以理论的时间复杂度为**O(m*n)。**但我们可以看到,因为途中遇到不能匹配的字符时,就可以停止,并不需要完全对比(比如上图第2行)。所以虽然理论时间复杂度为 O(m*n) ,但其实大部分情况效率高很多。

暴力匹配又称为BF算法,暴风算法。代码比较简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复制代码//GO 
func BFSearch(haystack string, needle string) int {
l1 := len(haystack)
l2 := len(needle)
i, j := 0, 0
for i < l1 && j < l2 {
if haystack[i] == needle[j] {
i++
j++
} else {
i -= j - 1
j = 0
}
}
if j == l2 {
return i - j
}
return -1
}

接下来我们开始说KMP。假如还是上面的这个串。最开始其实还是一样,我们依次对比A-A,B-B,C-C,直到遇见第一个无法匹配的字符A-E。

7.jpg

现在开始不一样了,如果按照上面的暴力匹配。此时目标串我们应该回到 B 这个位置,模式串应直接回到头。但是按照 KMP 的思路,在我们在第一次匹配后,因为 BC 匹配成功了,所以我们知道了 BC 不等于 A(注意这个逻辑关系):

8.jpg

那既然已知了 BC 不等于 A,我们就没必要用 A 和 BC 进行匹配了。那我们直接用 A 越过前面不需要匹配的 BC:

9.jpg

继续向下适配,我们发现在 D-C 处,匹配不上了。

10.jpg

那我们因为前面的 B 又匹配成功了,那我们就知道 B 不等于 A,所以我们又可以直接略过前面的 B:

11.jpg

也就是说,我们可以直接从 D 处开始比较:

12.jpg

继续向下比较:

13.jpg

到现在为止,你已经掌握了 KMP 的前百分之五十:在KMP中,如果模式串和目标串没有匹配成功,目标串不回溯。现在我们需要换一个新串,来掌握接下来的百分之五十:

14.jpg

我们还是从头开始匹配,直到遇到第一个不匹配的字符:

15.jpg

到这里和上面的例子还是一样,因为我们的 BC 匹配成功了,所以我们知道 BC 不等于 A,所以我们可以跳过 BC(注意这个逻辑):

16.jpg

所以我们从 A 处开始比较:

17.jpg

直到我们再次匹配失败:

18.jpg

我想到现在你已经知道怎么做了,来和我一起说。**因为前面的 B 匹配成功了,所以我们知道 B 不等于 A,所以我们可以跳过 B。**当然,跳过之后下一次的匹配直接失败了(A-D)。

19.jpg

重点来了!!!然后我们继续匹配下一位。我们发现这一次,我们的匹配基本就要匹配成功了,但是卡在了最后一步的比较(D-B)。

20.jpg

现在怎么办?假若我们把两个串修改一下(把里边的AB修改成XY),那么显而易见,你当然知道从哪里开始:

21.jpg

但是现在的问题是,在模式串中 AB 重复出现了,那我们是不是可以在下次比较的时候直接把 AB 给让出来?

22.jpg

所以我们把这个AB让出来,让出来之后,我们相当于在 模式串 上又跳过了 2个字符。(也就是说模式串下一次匹配从C开始)

23.jpg

其实到这里 KMP 就基本完事了。我们可以稍微总结下:

  • 如果模式串和目标串匹配成功,长串短串都加一
  • 如果模式串和目标串没有匹配成功:
    • 目标串不回溯(在上面的分割线之前,我都是给你讲这个)
      • 模式串回溯到匹配未成功的字符前的子串的相同的真前缀和真后缀的最大长度**(在上面的分割线之后,我重点是给你讲这个)**

好了,我知道上面匹配成功后的第二种情况有点拗口。所以我又单独拎出来和你说。这句话是啥意思呢?

假若我们有个串 abbaab:

  • a, ab, abb, abba, abbaa,就是它的真前缀。
  • b, ab, aab, baab, bbaab, 就是它的真后缀。
  • “真”字,说白了就是不包含自己。

在我们上面的示例中,未成功的字符前的子串是 ABCEAB,它相同的最长的真前缀和真后缀就是 AB,最大长度就是2。所以我们就把模式串回溯到第2个位置处。

24.jpg

我猜有人要说话了,“不是说模式串是回溯到真前缀和真后缀的最大长度位置处吗?那为什么上面的第一个例子,是回到了起始位置呢?”

25.jpg

其实,不是我们没有回溯模式串,而是此时的最大长度(指的是相同真前缀和真后缀的最大长度,后面都省略)其实就是 0。

那我们怎么获取最大长度呢?就可以很自然的引入 next表 了。不管你是把next表 理解成描述最大长度的东东,还是把 next表 理解成用来回溯模式串的东东,其实都是可以的!!!这也是为什么你在网上看到很多人文章对next表理解不一致的原因。

26.jpg

我们拿上面标黄色那个解释一下,ABCEAB 不包含自己,那就是 ABCEA,ABCEA的 真前缀 和 真后缀 为:

  • A,AB,ABC,ABCE
  • A,EA,CEA,BCEA

所以最大长度就是 1。那这个 1 干啥用呢?我们可以在下次比的时候就直接把这个 A 让过去,直接从 B 开始比。

27.jpg

这里注意,如果我们模式串稍微修改成下面这样,此时 F 的最大长度就是 0,并不是 2。初学者很容易把 AB 误认为是最长相同的真前缀和真后缀。

28.jpg

到这里为止,其实 KMP 的思路已经快说完了。但是大神说话了,大神认为这个匹配表,还得再改改,不然会出问题。

29.jpg

为什么会出问题呢,我们说了,对 KMP 而言,**如果没有匹配成功,**目标串是不回溯的。那如果目标串不回溯,如果模式串一直都是 0,是不是意味着这个算法就没办法继续进行下去?所以大神把这个 next匹配表 改了一下,把 0 位置处的 next表 值改为了 -1。

30.jpg

那这个 -1 是干嘛用的呢?其实只是一个代码技巧!大家注意一下第 7 行代码,假若没有 j == -1,此时如果 next[j] 等于 0,是不是就进死循环了。而加上这一句,相当于说无论什么情况下,模式串的第一个字符都可以匹配(对 j 而言,此时 -1++,是不是还是0。但是此时模式串却向前走了。不就不会因为死循环而卡死了吗?请大家自行脑补没有 j==-1 这行代码时,死循环卡死在11行的过程)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
复制代码 //GO 
func KmpSearch(haystack string, needle string, next []int) int {
l1 := len(haystack)
l2 := len(needle)
i, j := 0, 0
for i < l1 && j < l2 {
if j == -1 || haystack[i] == needle[j] {
i++
j++
} else {
j = next[j]
}
}
if j == l2 {
return i - j
}
return -1
}

到这里为止,其实 KMP 就讲的差不太多了,代码还是比较简单的。但是麻烦的是?一般我们并没有现成的 next表 直接使用。那 next表 又该如何生成呢?

其实 next表 的生成,我们也可以看作是字符串匹配的过程:即原模式串和原模式串自身前缀进行匹配的过程。

我们用下面这个字符串来讲一下:XXYXXYXXX。

31.jpg

对于该字符串:

  • 真前缀为 X,XX,XXY,XXYX,XXYXX…..
  • 真后缀为 X,XX,XXX,YXXX,XYXXX…..

为了方便大家理解,我画了两种图(左图是真实的填表过程,右图是脑补过程):

  • 首先 index[0] 肯定是填写 0

32.jpg

  • 然后填写 index[1]。如果匹配上,我们把 i 和 j 都加一。

33.jpg

  • 然后填写 index[2],如果没有匹配上,就把 j 回溯到 j 当前指向的前一个位置的 index 处。在这里,也就是 0 。

34.jpg

  • 注意,是回溯完成后才开始填表,此时 index[2] 为 0

35.jpg

  • 然后我们移动 i,发现下一位匹配成功。同时给 i 和 j 加一,并填表。

36.jpg

  • 填完表后,我们发现下一位仍然匹配。继续移动 i 和 j。

37.jpg

(填表)
38.jpg

(仍然匹配,继续移动 i 和 j)

  • 仍然匹配成功,继续重复上面的操作。

39.jpg

40.jpg

41.jpg

  • 注意,到这里开始匹配失败了。上面说了,如果没有匹配成功,把 j 回溯到 j 当前指向的前一个位置的 index 处。在这里,也就是 2 。

42.jpg

43.jpg

(j 的前一个位置的 index)
44.jpg

(回溯完成后,我们发现仍然不匹配)

  • 继续这个回溯的过程。。。(这一步是整个 next表 构建的核心)

45.jpg

(这个蓝色的小标是下次的回溯位置)
46.jpg

(回溯后,我们发现匹配成功了)
47.jpg

(然后我们可以填表了)

  • 注意!这里为什么是填2,其实就是填写上次回溯到的那个匹配成功的位置的index值加1。

细心的读者,估计到这里发现一点问题。我们把填完后的表拿出来:

48.jpg

我们发现这个表和我们最上面说的不太一样,我们最上面说的 next表 的首位是 -1,并且要记录哪一个 index 位置的 next 值,是去看该元素前面所有子串的真前缀和真后缀的最大长度。这句话有点拗口,我们还是看到下面这个。

49.jpg

比如 index 为 5 时,此时next的值是看 ABCEA 的最大长度(真后缀A,真前缀A,所以为1)。但是在我们下面这个表中,我们发现我们是记录的当前索引位置处的最大长度。其实我这里要说一下,下面这个表,其实我们一般称为部分匹配表,或者pmt。

50.jpg

那这个表和我们的 next 表有什么关系吗,我们发现把这个表往后串一位,就得到了我们最终的 next 表。

51.jpg

但是但是但是!!!并不是所有讲解 KMP 的地方都会给你提一提部分匹配表的概念,有的地方干脆就直接把这个 pmt 等同于 next 表使用。**这种属于错误讲解吗?其实不是的!**因为我上面也说了,next表 在最初始位置补 -1,或者甚至干脆把 pmt 的第一位补一个 -1 当作 next表,这都统统是可以的。因为最关键的还是说你到时候怎么去使用!毕竟 next表 的定义也是人们给它赋予的!

举个例子,假如你 next表 的首位不补 -1,我们其实就可以在前面 KMP 的算法中,去掉 -1 的逻辑。而单独加一个 if 判断来解决上面说的死循环的问题。

02、总结

KMP上篇到这里就结束了! KMP系列打算分上下两篇来讲,第一讲就是讲明白 KMP 是干嘛的,next 表是干嘛的,pmt 又是干嘛的。第二讲会给大家讲讲关于 next表 的计算,以及 next表 的优化。

总之,我个人认为本篇内容放在全网讲解KMP的文章里,质量都还是可以的。如果是小白,学习本篇文章其实就够了。

今天的题目到这里就结束了,你学会了吗?快来评论区留下你的想法吧!


我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。点击即可下载

和小浩学算法

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

Nestjs 从零到壹系列(八):使用 Redis 实现登

发表于 2020-07-23

前言

上一篇介绍了如何配合 Swagger UI 解决写文档这个痛点,这篇将介绍如何利用 Redis 解决 JWT 登录认证的另一个痛点:同账号的登录挤出问题。(再不更新,读者就要寄刀片了 -_-||)

GitHub 项目地址,欢迎各位大佬 Star。

为了照顾还没学到第八课读者,本篇教程单独开了一个分支 use-redis,拉项目后记得切换

前期准备

什么是 Redis

Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。

Redis 的效率很高,官方给出的数据是 100000+ QPS,这是因为:

  • Redis 完全基于内存,绝大部分请求是纯粹的内存操作,执行效率高。
  • Redis 使用单进程单线程模型的(K,V)数据库,将数据存储在内存中,存取均不会受到硬盘 IO 的限制,因此其执行速度极快。
    另外单线程也能处理高并发请求,还可以避免频繁上下文切换和锁的竞争,如果想要多核运行也可以启动多个实例。
  • 数据结构简单,对数据操作也简单,Redis 不使用表,不会强制用户对各个关系进行关联,不会有复杂的关系限制,其存储结构就是键值对,类似于 HashMap,HashMap 最大的优点就是存取的时间复杂度为 O(1)。
  • Redis 使用多路 I/O 复用模型,为非阻塞 IO。

注:Redis 采用的 I/O 多路复用函数:epoll/kqueue/evport/select。

安装 Redis

要使用 Redis,那首先得安装 Redis,由于本篇的重点不在 Redis安装,这里贴上 Windows 和 MacOS 环境的安装教程,不再赘述:

mac os 安装 redis - 简书

在 windows 上安装 Redis - 官方

有意思的是,官方的教程中提到了:

Redis 官方不建议在 windows 下使用 Redis,所以官网没有 windows 版本可以下载。还好微软团队维护了开源的 window 版本,虽然只有 3.2 版本,对于普通测试使用足够了。

Redis 可视化客户端

1. Mac OS

笔者使用 MacOS 系统,故使用 AnotherRedisDesktopManager 作为 Redis 可视化客户端:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复制代码# clone code
git clone https://github.com/qishibo/AnotherRedisDesktopManager.git
cd AnotherRedisDesktopManager

# install dependencies
npm install

# if download electron failed during installing, use this command
# ELECTRON_MIRROR="https://npm.taobao.org/mirrors/electron/" npm install

# serve with hot reload at localhost:9988
npm start

# after the previous step is completed, open another tab, build up a desktop client
npm run electron

2. Windows

在 Windows 下,可以使用 Redis Desktop Manager

官网的需要付费,不过测试同事用的 0.8.8.384 版本,读者可自行选择:

启动 Redis 并连接客户端

由于使用的 MacOS 系统,这里直接拿 AnotherRedisDesktopManager 做演示了,Windows 也是大同小异的。

我们先将 Redis 服务开起来,进入 /usr/local/bin/(具体根据你的安装路径来定),输入下列命令:

1
复制代码$ redis-server

出现下图表示服务启动成功:


然后新开一个终端,进入同样的目录,启动 Redis 客户端:

1
复制代码$ redis-cli


使用客户端连接可能需要输入密码,我们先将它设好,这里涉及到 2 个指令

查看密码:

1
复制代码$ config get requirepass

设置密码:

1
复制代码$ config set requirepass [new passward]

下面是我的指令记录,因为设置了密码 root,所以退出重进后需要 -a [密码],还有一点是,这种方式设置的密码,重启电脑后,原先设置会消失,需要重新设置


接下来启动 AnotherRedisDesktopManager,启动方法在上文提到了,需要新开一个终端标签页启动 electron。

左上角点击【新建连接】,输入配置信息即可:


然后就可以看到总览了:


好了,终于可以步入文章正题了。


Nest 操作 Redis


1. Redis 连接配置

首先,编写 Redis 配置文件,这里就直接整合到 config/db.ts 中了:

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
33
34
35
36
37
38
39
复制代码// config/db.ts
const productConfig = {
mysql: {
port: '数据库端口',
host: '数据库地址',
user: '用户名',
password: '密码',
database: 'nest_zero_to_one', // 库名
connectionLimit: 10, // 连接限制
},
+ redis: {
+ port: '线上 Redis 端口',
+ host: '线上 Redis 域名',
+ db: '库名',
+ password: 'Redis 访问密码',
+ }
};

const localConfig = {
mysql: {
port: '数据库端口',
host: '数据库地址',
user: '用户名',
password: '密码',
database: 'nest_zero_to_one', // 库名
connectionLimit: 10, // 连接限制
},
+ redis: {
+ port: 6379,
+ host: '127.0.0.1',
+ db: 0,
+ password: 'root',
+ }
};

// 本地运行是没有 process.env.NODE_ENV 的,借此来区分[开发环境]和[生产环境]
const config = process.env.NODE_ENV ? productConfig : localConfig;

export default config;

2. 建造 Redis 工厂

将这里需要配合 ioredis 使用:

1
复制代码$ yarn add ioredis -S

添加成功后,我们需要编写一个生成 Redis 实例列表的文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复制代码// src/database/redis.ts
import * as Redis from 'ioredis';
import { Logger } from '../utils/log4js';
import config from '../../config/db';

let n: number = 0;
const redisIndex = []; // 用于记录 redis 实例索引
const redisList = []; // 用于存储 redis 实例

export class RedisInstance {
static async initRedis(method: string, db: number = 0) {
const isExist = redisIndex.some(x => x === db);
if (!isExist) {
Logger.debug(`[Redis ${db}]来自 ${method} 方法调用, Redis 实例化了 ${++n} 次 `);
redisList[db] = new Redis({ ...config.redis, db });
redisIndex.push(db);
} else {
Logger.debug(`[Redis ${db}]来自 ${method} 方法调用`);
}
return redisList[db];
}
}

因为 redis 可以同时存在多个库(公司的有 255 个,刚刚本地新建的有 15 个),故需要传入 db 进行区分,当然,也可以写死,但之后每使用一个库,就要新写一个 class,从代码复用性上来说,这样设计很糟糕,所以在这里做了个整合。

函数里面的打印,是为了方便以后日志复盘,定位调用位置。

3. 调整 token 签发流程

在用户登录成功时,将用户信息和 token 存入 redis,并设置失效时间(单位:秒),正常情况应与 JWT 时效保持一致,这里为了调试方便,只写了 300 秒:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
复制代码// src/logical/auth/auth.service.ts
import { Injectable } from '@nestjs/common';
import { UserService } from '../user/user.service';
import { JwtService } from '@nestjs/jwt';
import { encryptPassword } from '../../utils/cryptogram';
+ import { RedisInstance } from '../../database/redis';

@Injectable()
export class AuthService {
constructor(private readonly usersService: UserService, private readonly jwtService: JwtService) {}

// JWT验证 - Step 2: 校验用户信息
async validateUser(username: string, password: string): Promise<any> {
// console.log('JWT验证 - Step 2: 校验用户信息');
const user = await this.usersService.findOne(username);
if (user) {
const hashedPassword = user.password;
const salt = user.salt;
const hashPassword = encryptPassword(password, salt);
if (hashedPassword === hashPassword) {
// 密码正确
return {
code: 1,
user,
};
} else {
// 密码错误
return {
code: 2,
user: null,
};
}
}
// 查无此人
return {
code: 3,
user: null,
};
}

// JWT验证 - Step 3: 处理 jwt 签证
async certificate(user: any) {
const payload = {
username: user.username,
- sub: user.userId, // 之前笔误,写错了
+ sub: user.id,
realName: user.realName,
role: user.role,
};
// console.log('JWT验证 - Step 3: 处理 jwt 签证', `payload: ${JSON.stringify(payload)}`);
try {
const token = this.jwtService.sign(payload);
+ // 实例化 redis
+ const redis = await RedisInstance.initRedis('auth.certificate', 0);
+ // 将用户信息和 token 存入 redis,并设置失效时间,语法:[key, seconds, value]
+ await redis.setex(`${user.id}-${user.username}`, 300, `${token}`);
return {
code: 200,
data: {
token,
},
msg: `登录成功`,
};
} catch (error) {
return {
code: 600,
msg: `账号或密码错误`,
};
}
}
}

关于 Redis 的使用,文末附上了一些科普教程,如果学习过程中需要查指令,可以去这里查询: Redis 命令参考

4. 调整守卫策略

这里本来想新建一个 token.guard.ts 的,但后面感觉每个路由又全加一遍,很麻烦,故直接调整 rbac.guard.ts:

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
33
34
复制代码// src/guards/rbac.guard.ts
- import { CanActivate, ExecutionContext, Injectable, ForbiddenException } from '@nestjs/common';
+ import { CanActivate, ExecutionContext, Injectable, ForbiddenException, UnauthorizedException } from '@nestjs/common';
+ import { RedisInstance } from '../database/redis';

@Injectable()
export class RbacGuard implements CanActivate {
// role[用户角色]: 0-超级管理员 | 1-管理员 | 2-开发&测试&运营 | 3-普通用户(只能查看)
constructor(private readonly role: number) {}
async canActivate(context: ExecutionContext): Promise<boolean> {
const request = context.switchToHttp().getRequest();
const user = request.user;

+ // 获取请求头里的 token
+ const authorization = request['headers'].authorization || void 0;
+ const token = authorization.split(' ')[1]; // authorization: Bearer xxx

+ // 获取 redis 里缓存的 token
+ const redis = await RedisInstance.initRedis('TokenGuard.canActivate', 0);
+ const key = `${user.userId}-${user.username}`;
+ const cache = await redis.get(key);

+ if (token !== cache) {
+ // 如果 token 不匹配,禁止访问
+ throw new UnauthorizedException('您的账号在其他地方登录,请重新登录');
+ }

if (user.role > this.role) {
// 如果权限不匹配,禁止访问
throw new ForbiddenException('对不起,您无权操作');
}
return true;
}
}

5. 验证

我们试着登录一下:


先看看日志,Redis 有没有被调用:


再看看 Redis 客户端里的记录:


发现已经将 token 存入了,并且到截图时,已经过去了 42 秒。

然后我们将 token 复制到请求商品列表的接口,请求:


上图是正常请求的样子,然后我们再登录,不修改这个接口的 token:


附上相关日志:


上图可以看到,策略已经生效了。

再看看 Redis 中记录到期会不会消失的情况,可以点击 TTL 旁边的绿色刷新键,查看剩余时间:


TTL 为 -2 就代表该键已到期,记录不存在了,我们可以点击左边的放大镜刷新一下:

注:TTL 为 -1 代表未设置过期时间(即一直存在);为 -2 表示该键不存在(即已失效)

可以看到,该条记录已经消失了,不再占用任何空间。

至此,大功告成。

总结

本篇介绍了如何在 Nest 中使用 Redis,并实现登录挤出的功能,稍稍弥补了 JWT 策略的缺陷。这里只是抛出一个“挤出”的思路,不局限于做在守卫上,如果有更好的思路,欢迎下方留言讨论。

利用 Redis 可以做很多事情,比如处理高并发,记录一些用户状态等。我曾经就用[队列]来处理红包雨活动,压测记录是 300+ 次请求/每秒。

还可以用来处理“登录超时”需求,比如把 JWT 的时效设置十天半个月的,然后就赋予 Redis 仅仅 1-2 个小时的时效,但是每次请求,都会重置过期时间,最后再判断这个键是否存在,来确认登录是否超时,具体实现就不在这里展开了,有兴趣的读者可自行完成。

本篇收录于NestJS 实战教程,更多文章敬请关注。

参考资料:

《Redis 由浅入深深深深深剖析》

《学 Redis 这篇就够了》

本文使用 mdnice 排版

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

一文吃透时间复杂度和空间复杂度

发表于 2020-07-23

学习数据结构和算法的第一步

时间复杂度

最常见的时间复杂度有哪几种

  • 「O(1)」:Constant Complexity 常数复杂度
  • 「O(log n)」:Logarithmic ComPlexity 对数复杂度
  • 「O(n)」:Linear ComPlexity 线性时间复杂度
  • 「O(n^2)」:N square ComPlexity 平方
  • 「O(n^3)」:N cubic ComPlexity 立方
  • 「O(2^n)」:Exponential Growth 指数
  • 「O(n!)」:Factorial 阶乘

分析时间复杂度的时候是不考虑前边的系数的,比如说O(1)的话,并不代表它的复杂度是1,也可以是2、3、4…,只要是常数次的,都用O(1)表示

如何来看一段代码的时间复杂度?

最常用的方式就是直接看这段代码,它根据n的不同情况会运行多少次

1
2
3
4
5
6
7
8
9
复制代码O(1)
$n=100000;
echo 'hello';

O(?)
$n=100000;
echo 'hello1';
echo 'hello2';
echo 'hello3';

第一段代码,不管n是多少,都只执行一次,所以它的时间复杂度就是O(1)。第二个其实也同理,我们不关心系数是多少。虽然第二段代码会执行3次echo输出,但是不管n是多少,它都只执行3次,因此它的时间复杂度也是「常数复杂度」,也就是O(1)

在看下边两段代码:

1
2
3
4
5
6
7
8
9
10
11
复制代码O(n)
for($i = 1; $i <= $n; $i++) {
echo 'hello';
}

O(n^2)
for($i = 1; $i <= $n; $i++) {
for($j = 1; $j <= $n; $j++) {
echo 'hello';
}
}

这两段代码都是随着n的不同,它执行的次数也在发生变化,第一段代码执行的次数和n是线性关系的,所以它的时间复杂度是「O(n)」。

第二段代码是一个嵌套循环,当n为100的情况下,里边的输出语句就会执行10000次,因此它的时间复杂度就是「O(n^2)」。如果第二段代码中的循环不是嵌套的,而是并列的,那么它的时间复杂度应该是O(2n),因为前边的常数系数我们不关注,因此它的时间复杂度就是「O(n)」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码O(log n)
for($i = 1; $i <= $n; $i = $i*2) {
echo 'hello';
}

O(k^2)

fib($n) {
if ($n < 2) {
return $n;
}

return fib($n-1) + fib($n-2);
}

第一段代码,当n=4时,循环执行2次,所以循环内部执行的次数和n的关系为log2(n),因此时间复杂度为对数复杂度「O(logn)」。第二段是一个Fibonacci(斐波拉契)数列,这里是用了递归的这种形式,这就牵扯到了递归程序在执行的时候,如何计算它的时间复杂度,它的答案是「k^n」,k是一个常数,是一个指数级的,所以简单的通过递归的方式求Fibonacci数列是非常慢的,它是指数级的时间复杂度。具体指数级的时间复杂度是怎么得到的,后边会详细说明。下边看一下各种时间复杂度的曲线


从这张图中可以看到,当n比较小的时候,在10以内的话,不同的时间复杂度其实都差不多。但是如果当n继续扩大,指数级的增长是非常快的。因此,当我们在写程序的时候,如果能优化时间复杂度,比如说从2^n降到n^2的话,从这个曲线来看,当n较大的时候,得到的收益是非常高的。因此这也告诉我们,在平时开发业务代码的时候,一定要对自己的时间和空间复杂度有所了解,而且是养成习惯,写完代码之后,下意识的分析出这段程序的时间和空间复杂度。

从图中可以看到,如果你的时间复杂度写砸了的话,其实带给公司的机器或者说资源的损耗,随着n的增大的话,是成百上千的增加,而如果你能简化的话,对公司来说是节约很多成本的

对于不同的程序,在写法当中完成同样的目标,它可能会导致时间复杂度的不一样。下边看一个简单的例题

1
复制代码从1加到2一直加到n,求它的和

小学学数学的时候,大家都知道了有两种方法,方法一的话用程序暴力求解的话,就是从1循环到n累加。这个是一层循环,n为多少,就执行多少次累加,所以它的时间复杂度就是「O(n)」

1
2
3
4
复制代码$sum = 0;
for ($i=1; $i <=$n; $i++) {
$sum += $i;
}

方法二就是使用一个数学的求和公式:

1
复制代码y = n*(n+1)/2

用这个公式,发现程序就只有一行了,所以它的时间复杂度就是O(1)了。所以可以看到,程序的不同方法,最后得到的结果虽然是一样的,但是它的时间复杂度很不一样

对于递归这种,如何分析时间复杂度?

递归的话,关键就是要了解它的递归过程,总共执行了递归语句多少次。如果是循环的话,很好理解,n次的循环就执行了n次。那么递归的话,其实它是层层嵌套,其实很多时候,我们就是把递归它的执行顺序,画出一个树形结构,称之为它的递归状态的递归树。以前边的求Fibonacci(斐波拉契)数列的第n项为例

1
2
3
复制代码Fib:0,1,1,2,3,5,8,13,21...

F(n) = F(n-1)+F(n-2)

我之前面试的时候遇到过这么一道题,写的是最最简单的用递归的方式实现

1
2
3
4
5
6
7
复制代码fib($n) {
if($n < 2) {
retuen $n;
}

return fib($n-1)+fib($n-2);
}

前边有说到它的时间复杂度是「O(k^n)」,那么怎么得到的,可以分析一下,假设此时n取6,要计算Fib(6),就看这段代码如何执行


所以,如果想计算F(6)就引出两个分支,F(5)和F(4),至少多出了两次运算

如果要计算F(5)可同理得到,需要结算F(4)和F(3)。如果要计算F(4)可同理得到,需要结算F(3)和F(2)。这里就可以看到两个现象:

  • 每多展开一层的话,运行的节点数就是上边一层的两倍,第一层只有1个节点,第二层有2个节点,第三层就有4个节点,再下一层就是8个节点。所以它每一层的话,它的节点数,也就是执行次数,是成指数增长的。由此可见,到n的时候,它就执行了2^n次
  • 第二个可以观察到,「有重复的节点」出现在了执行的树里边,比如图中的F(4)和F(3)。如果将这个树继续展开,会发现F(4)、F(3)、F(2)都会被计算了很多次

正是因为有这么多大量冗余的计算,导致求6个数的Fibonacci数的话,就变成了2^6次方这么一个时间复杂度。因此在面试中遇到这类题,尽量别用这种方式写,否则怕是直接凉凉了。可以加一个缓存,把这些中间结果能够缓存下来(用数组或哈希存起来,有重复计算的数值,再从里边找),或者直接用一个循环来写

主定理

介绍一个叫主定理的东西,这个定理为什么重要,就是因为这个主定理的话,其实它是用来解决所有递归的函数,怎么来计算它的时间复杂度。主定理本身的话,数学上来证明相对比较复杂(关于主定理可以参考维基百科:https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86)

也就是说,任何一个分治或者递归的函数,都可以算出它的时间复杂度,怎么算就是通过这个主定理。本身比较复杂的话,那怎样化简为实际可用的办法,其实关键就是这四种,一般记住就可以了


一般在各种递归的情形的话,有上边这四种情形,是在面试和平时工作中会用上

「二分查找(Binary search)」:一般发生在一个数列本身有序的时候,要在有序的数列中找到目标数,所以它每次都一分为二,只查一边,这样的话,最后它的时间复杂度是「O(logn)」

「二叉树遍历(Binary tree traversal)」:如果是二叉树遍历的话,它的时间复杂度为「O(n)」。因为通过主定理可以知道,它每次要一分为二,但是每次一分为二之后,每一边它是相同的时间复杂度。最后它的递推公式就变成了图中T(n)=2T(n/2)+O(1)这样。最后根据这个主定理就可以推出它的运行时间为O(n)。当然这里也有一个简化的思考方式,就是二叉树的遍历的话,会「每一个节点都访问一次,且仅访问一次,所以它的时间复杂度就是O(n)」

「二维矩阵(Optimal sorted matrix search)」:在一个排好序的二维矩阵中进行二分查找,这个时候也是通过主定理可以得出时间复杂度是「O(n)」,记住就可以了

「归并排序(merge sort)」:所有排序最优的办法就是「nlogn」,归并排序的时间复杂度就是O(nlogn)

常见的关于时间复杂度的面试题

「二叉树的遍历-前序、中序、后序:时间复杂度是多少?」

答案是:「O(n)」,这里的n代表二叉树里边树的节点的总数,不管是哪种方式遍历,每个节点都有且仅访问一次,所以它的复杂度是线性于二叉树的节点总数,也就是O(n)

「图的遍历:时间复杂度是多少?」

答案:「O(n)」,图中的每一个节点也是有且仅访问一次,因此时间复杂度也是O(n),n为图中的节点总数

「搜索算法:DFS(深度优先)、BFS(广度优先)时间复杂度是多少?」

答案:「O(n)」,后边的文章会详细介绍这两种算法(n为搜索空间中的节点总数)

「二分查找:时间复杂度是多少?」

答案:「O(logn)」

空间复杂度

空间复杂度和时间复杂度的情况其实类似,但是它更加的简单。用最简单的方式来分析即可。主要有两个原则:

如果你的代码中开了数组,那么数组的长度基本上就是你的空间复杂度。比如你开了一个一维的数组,那么你的空间复杂度就是O(n),如果开了一个二维的数组,数组长度是n^2,那么空间复杂度基本上就是n^2

如果是有递归的话,那么它递归最深的深度,就是你空间复杂度的最大值。如果你的程序里边递归中又开了数组,那么空间复杂度就是两者的最大值

在快速变化的技术中寻找不变,才是一个技术人的核心竞争力。知行合一,理论结合实践

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

图片质量压缩(Java->Thumbnailator + 原

发表于 2020-07-22

一、前提说明

业务要求需要将图片在上传服务器之前进行一波压缩。要求:图片保持原尺寸,所占内存压缩

注:网上各种类似的文章基本都是重复的,资源少并且很多文章的内容根本无法实现对应说明的效果。自己从开发开始到现在也一直是在面向百度编程,本着饮水思源的心理,记一下这个坑,以及自己的处理方式。

二、目前能做到压缩的几种方式

1.Thumbnailator (推荐)

1.1简介

Thumbnailator 是一个用来生成图像缩略图的 Java 类库,通过很简单的代码即可生成图片缩略图,也可直接对一整个目录的图片生成缩略图。

支持:图片缩放,区域裁剪,水印,旋转,保持比例,图片压缩。

Thumbnailator官网:code.google.com/p/thumbnail…

1
2
3
4
5
复制代码<dependency>
<groupId>net.coobird</groupId>
<artifactId>thumbnailator</artifactId>
<version>[0.4, 0.5)</version>
</dependency>

目前官网上发布的最新版本为0.4.11 (记录当前时间:2020/07/22)

Thumbnailator文档地址:coobird.github.io/thumbnailat…

1.2 使用

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
复制代码public class ImageUtils {
/**
* 根据指定大小压缩图片
*
* @param imageBytes 源图片字节数组
* @param desFileSize 指定图片大小,单位kb
* @param imageId 影像编号
* @return 压缩质量后的图片字节数组
*/
public static byte[] compressPicForScale(
byte[] imageBytes, long desFileSize, String imageId, Double quality) {
if (imageBytes == null || imageBytes.length <= 0 || imageBytes.length < desFileSize * 1024) {
return imageBytes;
}
long srcSize = imageBytes.length;
try {
ByteArrayInputStream inputStream = new ByteArrayInputStream(imageBytes);
ByteArrayOutputStream outputStream= new ByteArrayOutputStream(imageBytes.length);
Thumbnails.of(inputStream).scale(1f).outputQuality(quality).toOutputStream(outputStream);
imageBytes = outputStream.toByteArray();
log.info(
"【图片压缩】imageId={} | 图片原大小={}kb | 压缩后大小={}kb",
imageId,
srcSize / 1024,
imageBytes.length / 1024);
} catch (Exception e) {
log.error("【图片压缩】msg=图片压缩失败!", e);
}
return imageBytes;
}
}

注意:

1.scale()为尺寸压缩,与这个方法类似的是size()方法,这两个都是指定图片尺寸的,不同的是,scale是按照比例来处理的图片尺寸,而size()是直接指定图片的width和height。outputQuality指定的是图片质量。

2.实测证明不管哪种压缩,都对JPG格式的支持力度是最好的。所以没有格式要求的情况下,请转为jpg格式。尤其是png格式的
请必转!

3.上述方法,在输出图片时,最终图片会比日志中打印的大小大30%左右,byte[],猜测是压缩后的空间碎片导致的。

1.3 深坑说明

重点!!!!!

不要做循环调用这种傻事!!!质量压缩是有固定算法的,大小固定的情况下不存在outputQuality(0.9)的时候,下一次循环质量就变成0.81了!!! 循环只会导致一个结果:亲,死循环了~

举个栗子: 循环调用导致死循环,也是在一个博客中摘得。排坑所得…

2.java原生API (挺坑的,质量系数设置小了,大小反而会变大。大家看看就好)

2.1 上代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
复制代码public static boolean compressPic(String srcFilePath, String descFilePath) throws IOException {
File file = null;
BufferedImage src = null;
FileOutputStream out = null;
ImageWriter imgWrier;
ImageWriteParam imgWriteParams;

// 指定写图片的方式为 jpg
imgWrier = ImageIO.getImageWritersByFormatName("jpg").next();
imgWriteParams = new javax.imageio.plugins.jpeg.JPEGImageWriteParam(
null);
// 要使用压缩,必须指定压缩方式为MODE_EXPLICIT
imgWriteParams.setCompressionMode(imgWriteParams.MODE_EXPLICIT);
// 这里指定压缩的程度,参数qality是取值0~1范围内,
imgWriteParams.setCompressionQuality((float)1);
imgWriteParams.setProgressiveMode(imgWriteParams.MODE_DISABLED);
ColorModel colorModel = ImageIO.read(new File(srcFilePath)).getColorModel();// ColorModel.getRGBdefault();
// 指定压缩时使用的色彩模式
// imgWriteParams.setDestinationType(new javax.imageio.ImageTypeSpecifier(
// colorModel, colorModel.createCompatibleSampleModel(16, 16)));
imgWriteParams.setDestinationType(new javax.imageio.ImageTypeSpecifier(
colorModel, colorModel.createCompatibleSampleModel(16, 16)));
try {
if (isBlank(srcFilePath)) {
return false;
} else {
file = new File(srcFilePath);
System.out.println(file.length());
src = ImageIO.read(file);
out = new FileOutputStream(descFilePath);

imgWrier.reset();
// 必须先指定 out值,才能调用write方法, ImageOutputStream可以通过任何
// OutputStream构造
imgWrier.setOutput(ImageIO.createImageOutputStream(out));
// 调用write方法,就可以向输入流写图片
imgWrier.write(null, new IIOImage(src, null, null),
imgWriteParams);
out.flush();
out.close();
}
} catch (Exception e) {
e.printStackTrace();
return false;
}
return true;
}

public static boolean isBlank(String string) {
if (string == null || string.length() == 0 || string.trim().equals("")) {
return true;
}
return false;
}

3.总结

1.其实应该不会有巨神坑的产品,循环压缩到固定大小以下的需求,不是扯淡是啥啊。

分析一下啊,比如一张5M的照片,格式相同的情况下压到500k,这图还能看吗?? 压缩图片无非就是为了效率,个人测试的时候压缩系数在0.5的话,图片不会出现明显的失真,一旦比这个低了就相当危险了。这种情况下产品觉得还不行的话,那估计就只能开战了,哈哈。

  1. 结尾:png转jpg的时候,可能会出现图片颜色失真的情况。这个可以用画图工具构建一张原图大小的空白画卷,然后将想要转换的图画进去。原理不了解~有点玄学。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

给Swagger换了个新皮肤,瞬间高大上了!

发表于 2020-07-22

SpringBoot实战电商项目mall(35k+star)地址:github.com/macrozheng/…

摘要

Swagger作为一款API文档生成工具,虽然功能已经很完善了,但是还是有些不足的地方。偶然发现knife4j弥补了这些不足,赋予了Swagger更多的功能,今天我们来讲下它的使用方法。

knife4j简介

knife4j是springfox-swagger的增强UI实现,为Java开发者在使用Swagger的时候,提供了简洁、强大的接口文档体验。knife4j完全遵循了springfox-swagger中的使用方式,并在此基础上做了增强功能,如果你用过Swagger,你就可以无缝切换到knife4j。

快速开始

接下来我们来介绍下如何在SpringBoot中使用knife4j,仅需两步即可!

  • 在pom.xml中增加knife4j的相关依赖;
1
2
3
4
5
6
复制代码<!--整合Knife4j-->
<dependency>
<groupId>com.github.xiaoymin</groupId>
<artifactId>knife4j-spring-boot-starter</artifactId>
<version>2.0.4</version>
</dependency>
  • 在Swagger2Config中增加一个@EnableKnife4j注解,该注解可以开启knife4j的增强功能;
1
2
3
4
5
6
7
8
9
复制代码/**
* Swagger2API文档的配置
*/
@Configuration
@EnableSwagger2
@EnableKnife4j
public class Swagger2Config {

}
  • 运行我们的SpringBoot应用,访问API文档地址即可查看:http://localhost:8088/doc.html

功能特点

接下来我们对比下Swagger,看看使用knife4j和它有啥不同之处!

JSON功能增强

平时一直使用Swagger,但是Swagger的JSON支持一直不是很好,JSON不能折叠,太长没法看,传JSON格式参数时,没有参数校验功能。这些痛点,在knife4j上都得到了解决。

  • 返回结果集支持折叠,方便查看;

  • 请求参数有JSON校验功能。

登录认证

knife4j也支持在头部添加Token,用于登录认证使用。

  • 首先在Authorize功能中添加登录返回的Token;

  • 之后在每个接口中就可以看到已经在请求头中携带了Token信息。

离线文档

knife4j支持导出离线文档,方便发送给别人,支持Markdown格式。

  • 直接选择文档管理->离线文档功能,然后选择下载Markdown即可;

  • 我们来查看下导出的Markdown离线文档,还是很详细的。

全局参数

knife4j支持临时设置全局参数,支持两种类型query(表单)、header(请求头)。

  • 比如我们想要在所有请求头中加入一个参数appType来区分是android还是ios调用,可以在全局参数中添加;

  • 此时再调用接口时,就会包含appType这个请求头了。

忽略参数属性

有时候我们创建和修改的接口会使用同一个对象作为请求参数,但是我们创建的时候并不需要id,而修改的时候会需要id,此时我们可以忽略id这个属性。

  • 比如这里的创建商品接口,id、商品数量、商品评论数量都可以让后台接口生成无需传递,可以使用knife4j提供的@ApiOperationSupport注解来忽略这些属性;
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
复制代码/**
* 品牌管理Controller
* Created by macro on 2019/4/19.
*/
@Api(tags = "PmsBrandController", description = "商品品牌管理")
@Controller
@RequestMapping("/brand")
public class PmsBrandController {
@Autowired
private PmsBrandService brandService;

private static final Logger LOGGER = LoggerFactory.getLogger(PmsBrandController.class);

@ApiOperation("添加品牌")
@ApiOperationSupport(ignoreParameters = {"id","productCount","productCommentCount"})
@RequestMapping(value = "/create", method = RequestMethod.POST)
@ResponseBody
public CommonResult createBrand(@RequestBody PmsBrand pmsBrand) {
CommonResult commonResult;
int count = brandService.createBrand(pmsBrand);
if (count == 1) {
commonResult = CommonResult.success(pmsBrand);
LOGGER.debug("createBrand success:{}", pmsBrand);
} else {
commonResult = CommonResult.failed("操作失败");
LOGGER.debug("createBrand failed:{}", pmsBrand);
}
return commonResult;
}
}
  • 此时查看接口文档时,发现这三个属性已经消失,这样前端开发查看接口文档时就不会觉得你定义无用参数了,是不很很好的功能!

参考资料

官方文档:doc.xiaominfo.com/guide/

项目源码地址

github.com/macrozheng/…

公众号

mall项目全套学习教程连载中,关注公众号第一时间获取。

公众号图片

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

1…791792793…956

开发者博客

9558 日志
1953 标签
RSS
© 2025 开发者博客
本站总访问量次
由 Hexo 强力驱动
|
主题 — NexT.Muse v5.1.4
0%