Trie(前缀树)

Trie

Trie ,也叫做 digital tree(数字树) 有时候也是 radix tree(基数树) 或者 prefix tree(前缀树) (因为他们可以通过前缀进行搜索) 是一种 search tree - 一种用来存储通常键为 stringsdynamic set 或者 associative array 有序的 tree 数据结构. 不像 binary search tree(二叉搜索树) , Trie 树里的节点不存储与该节点关联的键,而是使用他在树里的位置来表明它所关联的键.一个节点的所有子节点都有该节点关联的字符串前缀,并且根节点关联的是一个空字符串.键倾向于与叶子关联,也有一些内部节点也有关联了键.因此,并不是每一个节点都会有关联的键.有关于前缀树的空间优化,可以参考 compact prefix tree .

如同示例所示,键展示在节点中,而值在节点的下面.每一个英文单词都有一个值.一个 trie 可以视为一个 树形的 deterministic finite automaton . 每一个 有限语言(finite language) 都是由一个 trie 自动机(automaton)生成的,并且每个 trie 可以被压缩成一个 deterministic acyclic finite state automaton .

它的键不仅仅可以使用字符串的字符,它同样可以使用相同的算法来适配一些相同功能的任何构造组成的有序列表,比如数字或者形状(shapes)的列表排序.特别是,一个 bitwise trie 是使用二进制数据的固定长度的 bit 来当做建,比如使用一个整数或者存储器地址.

应用

替换其他数据结构

trie 和 binary search tree 相比有很多的优点. Trie 同样可以用来替换 hash table ,它拥有以下的优点:

Read More

依赖注入

依赖注入

[TOC]

概述

依赖注入(Denpendecy Injection ,DI) 通常和 控制反转(Inverse of Control,IoC) 一起出现.它是实现IoC的主要手段之一.通过依赖注入类可以不关心自身的依赖应该如何构造,而是由注入器代理这个职责,将类需要的依赖构建好后注入到类里.可以达到分离关注点,分离调用方和依赖,提高可复用性和可维护性.

为什么需要依赖注入

为什么需要依赖注入呢? 这和为什么需要IoC的原因基本相同.

在常规的开发过程中,很多时候一个类都是要依赖于其他的类才能实现某些功能,才能够更好的将关注点分离,比如一个车 Car 类 内部需要使用燃油引擎 Engine 类,那么他需要在 Car 的内部做类似 new Engine() 这样的操作, 看起来没有任何的问题,但是当需要更换引擎为他的子类电气引擎ElectricEngine 的时候,问题就来了,我们需要在 Car 的内部修改 Engine 类,或者是当 Engine 做了修改需要额外的参数的时候,也会需要改动到 Car 的内部,并且每个类都得对自身的依赖有更多的了解,这就违反了底米特原则(todo) 和 开闭原则(todo)导致了代码的耦合度极高,不利于维护和扩展.

如图

Read More

IoC 控制反转

IoC 控制反转

[toc]

概述

控制反转(Inversion of Control,缩写为IoC),它是软件开发中的一种设计原则,可以降低代码的耦合度,使得程序更加的模块化,更易于扩展.

为什么叫做控制反转?又为什么能够降低代码的耦合度呢?

在常规的开发过程中,很多时候一个类都是要依赖于其他的类才能实现某些功能,才能够更好的将关注点分离,比如一个车 Car 类 内部需要使用燃油引擎 Engine 类,那么他需要在 Car 的内部做类似 new Engine() 这样的操作, 看起来没有任何的问题,但是当需要更换引擎为他的子类电气引擎ElectricEngine 的时候,问题就来了,我们需要在 Car 的内部修改 Engine 类,或者是当 Engine 做了修改需要额外的参数的时候,也会需要改动到 Car 的内部,并且每个类都得对自身的依赖有更多的了解,这就违反了底米特原则(todo) 和 开闭原则(todo)导致了代码的耦合度极高,不利于维护和扩展.

如图

Read More

Serializable

Serializable

通过实现 java.io.Serializable 可以让 class 实现序列化的功能,否则无法使用序列化的功能。一个实现序列化的类的子类都是可以进行序列化的。Serializable 接口没有方法,字段等只是一个标记它是可以序列化的作用。

序列化是指将数据结构或对象状态转换成可取用格式(例如存成文件,存于缓冲,或在网络中传送),并在需要的时候恢复原先状态的过程。

当子类实现了 Serializable 接口而父类没有实现的时候,父类要有一个可以访问的无参构造函数。

在反序列化的时候,没有实现序列化的类字段将会使用 public 或者 protect 的无参构造函数进行初始化。无参构造函数必须是实现序列化的子类可访问的,

如果需要在序列化和反序列化的时候进行一些特殊操作的话,需要自己实现以下某些方法:

Read More

实现键值对存储 第五部分 Hash table 实现

实现键值对存储-第五部分: Hash table 实现

原文链接

这篇文章是 IKVS 系列的第五部分,”实现一个键值对存储”.你也可以查看 Table of Contents 来查看其他部分.

在这篇文章中,我将会学习C++中实际的 hash table 来理解它的瓶颈在哪里.Hash 函数是 CPU-密集型的操作应该要进行优化.然而,大多数的 hash table 的机制都只是关注于高效的内存和I/O读取,这也是这篇文章主要的焦点.我将会学习三种不同的 C++中的hash table 的实现,同时包含内存中的和硬盘中的,并且会观察这些数据都是怎么组织和访问的.这篇文章将会包含以下内容.

[TOC]

kvstore-part5-intro

Read More

Binary Search(二分搜索)

Binary Search(二分搜索)

二分搜索(binary search),也叫做 折半搜索(half-interval search),对数搜索(logarithmic search),对半搜索(binary chop),是一种在有序数组中查找某一特定元素的搜索算法.

二分搜索有几个变体.特别是,分散层叠(fractional cascading)(将每个数组里的值集合成一个数组,元素为11[0,3,2,0] 的形式,括号内的数字是该值在对应数组中应该返回的数字)提高了在多个数组中查找相同值的效率,高效的解决了一系列计算几何和其他领域的查找问题).指数查找(Exponential search)延伸了二分查找到一个没有边界的 list.binary search treeB-tree是基于 binary search 延伸的.

原理

搜索时从数组中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果中间元素大于或者小于要查找的元素,则在数组中大于或者小于查找元素的一半中继续查找,重复这个过程直到找到这个元素,或者这一半的大小为空时则代表找不到.这样子每一次比较都使得搜索范围缩小一半.

步骤

给定一个有序数组 A 是 A0,…,An-1并保证 A0<=…<=An-1,以及目标值 T.

Read More

自定义视图及其性能

线程性能

性能中很关键的一点就是多线程的使用.Android 中很多事件只能在主线程中执行,比如 输入事件,应用程序回调服务,警报等等.

这意味着这些事件会形成一个阻塞队列,这些任务会依次按顺序执行.然而UI 渲染也是在主线程中的,而他们每 16ms 就会渲染一次,来达到一个平滑的过渡,但是如果有大量的其他任务堆积在主线程中,可能会导致你错过某一个 16ms 的渲染机会,导致丢帧的情况.

为了处理这种情况,我们可以把一些耗时较长的任务转移到其他线程处理,这样主线程就能够更快的响应了.Android 中提供了一些有助于这个目的的类.

  • AsyncTask : 帮助你区分 UI 线程和非 UI 线程的工作
Read More

Android 模块依赖版本管理

Android 模块依赖版本管理

由于 Android 模块化的需要,依赖库要保持统一,但是每次一旦某个模块版本变动,就要手动修改所有模块的版本号未免显得有些繁琐,而且有一些共用的模块可能在不同的项目中要使用不同的版本.所以需要一个统一管理版本模块的方法.

步骤

1. 在项目主目录下新建一个名为 dependency.gradle 的文件

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
32
33
34
35
36
37
38
39
40
41
42
43
44
ext {
ext.deps = [:]
def deps = [:]
// 统一的版本号管理
def versions = [:]
versions.kotlin = "1.3.70"
versions.android_gradle_plugin = "3.5.2"
versions.appcompat = "1.1.0"
versions.dagger = "2.16"
versions.material = "1.2.0-alpha03"
versions.work = "2.3.0-alpha01"
versions.retrofit = "2.3.0"
versions.recyclerview = "1.1.0"
versions.okhttp = "3.0.1"
versions.guava = "20.0"
versions.navigation = "2.3.0-alpha01"
versions.multidex = "1.0.0"
//------------------------------------------------------------------------------
// 一组依赖可以使用这个方式
def navigation = [:]
navigation.runtime = "androidx.navigation:navigation-runtime:$versions.navigation"
navigation.runtime_ktx = "androidx.navigation:navigation-runtime-ktx:$versions.navigation"
navigation.fragment = "androidx.navigation:navigation-fragment:$versions.navigation"
// 这句要记得
deps.navigation = navigation
...
// 单个依赖可以使用这中方式
deps.app_compat = "androidx.appcompat:appcompat:$versions.appcompat"
// app 本身的版本管理也可以放进来
def build_versions = [:]
build_versions.min_sdk = 19
build_versions.compile_sdk = 29
build_versions.target_sdk = 29
build_versions.build_tools = "29.0.3"
ext.build_versions = build_versions
ext.deps = deps
}

如上图所示,配置文件就完成了

3. 使用

在 root 目录下的 build.gradle 中加上 apply from: "dependency.gradle"

在需要添加依赖的 Module 中使用,如下

Read More

Gradle Kotlin DSL

Gradle Kotlin DSL

[TOC]

我觉得你们可以先看最后的彩蛋再决定是不是要看

强烈推荐先看文章最后的彩蛋!!!

为什么选择 Gradle Kotlin DSL

首先我们要先明确我们这么做的原因有哪些?是否值的我们从 groovy 迁移到 kotlin.

Kotlin 相比于 Groovy 有这么几个好处:

Read More

工具 严格模式

Tool: Strict Mode

[TOC]

背景

当你的应用中的事件处理超过了 5 秒钟没有响应的时候,Android 会弹出一个 ANR 弹窗. 这是因为 UI 线程被阻塞了,它在等待某些事情的完成.因为 UI 线程是唯一一个可以处理输入和绘制的线程,当它停止响应的时候,你的 app 也停止了响应.

那么什么会导致 UI 线程像这样停止呢?通常情况下系统调用可以无期限的阻塞它,就像磁盘或者网络获取.这些阻塞调用是你应用中的定时炸弹.在正常情况下,它们运行的非常快,你甚至无法注意到他们.但在某些软件和硬件条件以及一些运气的情况下,他们爆炸了.

方案

接下来我们来介绍一下如何找到这些隐藏的问题.这个工具的名字叫 Strict Mode ,你可以在 开发者模式中勾选上 Strict Mode Enabled 来启动它.当它是启动的时候,在你的应用中如果有在 UI 线程中的耗时操作的时候屏幕的边框会变成红色的.

Strict Mode 实际上定义了你在什么线程中可以做什么事,它有点像一个运行时的 Lint . 它是对你的线程策略做了一个规定,策略是由两个部分呢组成的

Read More
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×