队列的特点是FIFO,遵循一个先来后到,但是如果有的任务本身执行时间很短但由于排队时间太长导致执行过慢就不是很合逻辑,因此就有了优先队列(priority queue)这样的数据结构,优先队列同样有入栈和出栈,特殊的地方在于出栈是找到其中min然后出栈,定义实现了优先队列的数据结构叫堆(heap)

堆的性质

结构性

堆又叫做完全二叉树,它的特点是所有节点都被填满,除了底层之后,并且底层的元素是从左向右填入(左有右没有),这里需要区分满二叉树:所有节点都填满。

完全二叉树有个规律,它可以直接用数组来表示出来

1
2
3
4
5
6
7
         A
/ \
B C
/ \ / \
D E F G
/ \ /
H I j
1
2
A B C D E F G H I J
1 2 3 4 5 6 7 8 9 10

对于i上的元素x,x的父节点是array[i/2],左儿子是array[2i],右儿子是array[2i+1]。
这样的好处在于一个完全二叉树可以用一个数组来表示,另外需要一个表示数组大小的整型变量。

堆序性

因为每次出栈都是弹出min元素,因此需要把min元素放在root上是最简单的。这就需要插入或者删除的时候需要调整堆来保证堆序性(也需要保证结构性)。
堆序性可以这样表述: 对于i上的元素x来说,x永远大于等于x的父节点(array[i/2])

1
2
3
4
5
6
     13                      13
/ \ / \
25 36 7 16
/ \ / \
66 77 23 32
满足堆序性 由于7<13,因此不满足堆序性

要保证这样的堆序性就是为了root节点是min节点,最简单最快的找到min节点。

插入

假设有这样的一个堆,向该堆中插入14。

1
2
3
4
5
6
7
             13
/ \
21 16
/ \ / \
24 31 19 68
/ \ / \
65 26 32

堆有个性质可以用数组来表示

1
2
   13 21 16 24 31 19 68 65 26 32   14
0 1 2 3 4 5 6 7 8 9 10 11

如果只是把14插入最后就破坏了堆序性:14 > array[11/2] (array[5] = 31),因此我们将14和31交换位置,发现14依然小于他的父节点(array[5/2] = 21),继续和21交换位置,由于14大于他的父节点13,所以插入到此结束。

1
2
3
4
5
6
7
public insert (int x) {
int hole = currentSize++;
for (array[0] = x ; x.compareTo(array[hole/2] <0) ; hole /= 2) {
array[hole] = array[hole/2];
}
array[hole] = x;
}

由于是在底层然后一层层往上找空位的,因此这个操作叫上滤。

删除最小元

由于root节点就是最小元,因此要寻找它不怎么难,但是将他删除之后的空位需要怎么填补是个问题。

1
2
3
4
5
6
7
             13
/ \
14 16
/ \ / \
24 21 19 68
/ \ / \
65 26 32 31

因此只能用min节点的子节点中偏小的那个来填充这个空。如上述的堆中,13没了之后应该用14来填补,然后14又空出来了,继续用21来填补,而21又空出来了,因此用31来填补,所以删除了13之后变成了这样

1
2
3
4
5
6
7
             14
/ \
21 16
/ \ / \
24 31 19 68
/ \ /
65 26 32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public T deleteMin() {
T min = findMin();
array[1] = array[currentSize--];
percolateDown(1);
return min;
}
public void percolateDown(int hole) {
int child;
T tmp = array[hole];
for (;hole * 2 <= currentSize;chile = hole) {
child = hole * 2;
if (child != currentSize && array[chile].compareTo(array[child + 1]) < 0) {
child++;
}
if (array[hole] < array[childe]) {
break;
} else {
array[hole] = array[child];
}
}
array[hole] = tmp;
}

具体实现的思路是将最后一个值先放入min节点中,然后层层向下和子节点比较,直到找到合适的位置,这种操作叫做下滤。

const pointer

cont int *

const int * 表示的是一个指针 - 指向一个int常量,因此这个指针所指向的东西是只读的。但指针本身是可写的。

1
2
3
4
5
int i = 100;
const int* pt = &i;// 表示指向一个int常量的指针
*pt = 101; // error: Read-only variable is not assignable
int j = 101;
pt = &j; // good

int* const pt

int * const 表示的是一个常量指针 - 指向int类型,因此这个指针是只读的,但是他所指向的东西是可以改变的。

1
2
3
4
5
6
int i = 100;
int j = 101;
cout << &i << endl;
int* const pt = &i;// 表示一个指向int类型的常量指针
pt = &j; // Cannot assign to variable 'pt' with const-qualified type 'int *const'
*pt = 1000; // good

Summary

关于c或者c++这种指针类型的解释是有规律的,只需要倒过来读就可以了,*表示a pointer to(一个指针 - 指向)

  • int* == pointer to int == 一个指针 - 指向int类型
  • int const * == pointer to const int == 一个指针 - 指向int常量
  • int * const == const pointer to int == 一个常量指针 - 指向int类型
  • int const * const == const pointer to const int == 一个常量指针 - 指向int常量

const处于首位的时候,放在类型的两边的都可以

  • const int * == int const *
  • const int * const == int const * const

Clockwise/Spiral Rule:

http://c-faq.com/decl/spiral.anderson.html

Python ImportError

在执行python项目的时候,出现了这样的报错

1
ImportError: No module named user_util

去check了一下代码,发现user_util确实在目录中,令人不解。

在google了之后才知道需要设置PYTHONPATH或者sys.path,执行如下指令就可以解决ImportError

1
export PYTHONPATH=`pwd`

在看了doc之后,原来是这样的,sys.path的类型是一个list,而编译器是在这个list中寻找import的module,如果这个list中找不到就会报出ImportError。而这个变量是从PYTHONPATH初始化来的,当然还有一些系统默认自带的路径。需要注意的是在执行某个文件的时候,会将这个文件的目录加入sys.path中,比如这个文件

1
/Users/star/PycharmProjects/Practice/osinfo.py

如果在osinfo.py中打印一下sys.path会得到如下输出

1
['/Users/star/PycharmProjects/Practice', '/Users/star/PycharmProjects/Practice', '/usr/local/Cellar/python/3.7.0/Frameworks/Python.framework/Versions/3.7/lib/python37.zip', '/usr/local/Cellar/python/3.7.0/Frameworks/Python.framework/Versions/3.7/lib/python3.7', '/usr/local/Cellar/python/3.7.0/Frameworks/Python.framework/Versions/3.7/lib/python3.7/lib-dynload', '/Users/star/PycharmProjects/Practice/venv/lib/python3.7/site-packages', '/Users/star/PycharmProjects/Practice/venv/lib/python3.7/site-packages/setuptools-39.1.0-py3.7.egg', '/Users/star/PycharmProjects/Practice/venv/lib/python3.7/site-packages/pip-10.0.1-py3.7.egg']

可以看到sys.path[0]sys.path[1]表示的是该文件的当前目录,而其余都是python自带的目录。

因此不仅仅需要check module是否存在,还需要checkPYTHONPATH变量。

Inline

C++中有inline关键字,传统函数中我们调用函数的时候,其实是将该指令的内存地址保存下来,并将函数参数复制到堆栈。当函数运行完之后再跳回去。这样来回跳跃会加大开销。而如果一个函数被inline修饰的话,在编译的时候则是直接将该函数的body拷贝到执行的地方。

Kotlin中也有相同的关键字,一般用于高阶函数,想知道有什么变化,还是看对应的Java文件更清晰点。

(IntelliJ的Decompiler不太靠谱,所以这里用的JD-GUI)

源文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class User {
fun nonInlined(block: () -> Unit) {
println("before")
block()
println("after")
}

inline fun inlined(block: () -> Unit) {
println("before")
block()
println("after")

}
}

fun main(args: Array<String>) {
val user = User()

user.nonInlined { println("noninline") }

println("**********")

user.inlined { println("inline") }
}
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
public final class UserKt
{
public static final void main(@NotNull String[] args) {
Intrinsics.checkParameterIsNotNull(args, "args"); User user = new User();

user.nonInlined((Function0)UserKt$main$1.INSTANCE);

String str1 = "**********"; boolean bool1 = false; System.out.println(str1);

User this_$iv = user; int $i$f$inlined = 0;

String str2 = "before"; boolean bool2 = false; System.out.println(str2);
int $i$a$-inlined-UserKt$main$2 = 0; String str3 = "inline"; boolean bool3 = false; System.out.println(str3);
str2 = "after"; bool2 = false; System.out.println(str2);
}

static final class UserKt$main$1 extends Lambda implements Function0<Unit> {
public static final UserKt$main$1 INSTANCE = new UserKt$main$1();

public final void invoke() {
String str = "noninline";
boolean bool = false;
System.out.println(str);
}

UserKt$main$1() { super(0); }
}
}

可以看到用inline修饰的部分直接copy了函数体到调用的地方。和C++上的作用一样。

关于这篇文章:https://stackoverflow.com/questions/44471284/when-to-use-an-inline-function-in-kotlin解释的非inline方法会创建一个实例结合这个例子来看有些不太匹配的地方。文章中说Kotlin中调用高阶函数会创建一个匿名内部类,类似这样:

1
2
3
4
5
6
nonInlined(new Function() {
@Override
public void invoke() {
System.out.println("do something here");
}
});

但是从JD decompile的结果来看,它是创建了一个静态的实例。猜测是新的Kotlin版本进行了优化。

1
2
3
4
5
6
7
8
9
10
11
static final class UserKt$main$1 extends Lambda implements Function0<Unit> {
public static final UserKt$main$1 INSTANCE = new UserKt$main$1();

public final void invoke() {
String str = "noninline";
boolean bool = false;
System.out.println(str);
}

UserKt$main$1() { super(0); }
}

需要注意的是inline修饰的函数无法调用private修饰的方法或者变量

1
2
3
4
inline fun inlined(block: () -> Unit) {
dummy() //compilation error
println(i) //compilation error
}

Anyway,inline关键字和C++中的一样,都是为了减少内存开销。但它的副作用在于额外增加了字节码。因此如果一个函数体的逻辑比较复杂则不那么适合用inline

Sealed

Java中的枚举一般用于switch中使得代码更简洁优美。比如根据类型来播放不同的铃声

1
2
3
4
5
enum class RingerType {
Outgoing,
Incoming,
Busy
}

不过枚举类有个缺点,如果想增加额外的数据就会变成这样,这还只是加了一个String类型,额外带个自定义的类型会更加复杂,并且对于NotFound来说在构造的时候不需要任何参数。

1
2
3
4
5
6
enum class RingerType(s: String) {
Outgoing("R.raw.outgoing"),
Incoming("R.raw.outgoing"),
Busy("R.raw.outgoing"),
NotFound("")
}

这种情况则可以使用sealed class来描述,如果有额外的数据结构用data来修饰,没有任何参数的则可以直接用class

1
2
3
4
5
6
sealed class RingerType {
class NotFound : RingerType()
data class Outgoing(val uri: String) : RingerType()
data class Incoming(val uri: String) : RingerType()
data class Busy(val uri: String) : RingerType()
}

因此kotlin官网上说sealed class是枚举的一种延展或者加强版

1
They are, in a sense, an extension of enum classes.

JNI

最近项目中需要添加JNI接口,顺便学习了一下JNI。JNI简单来说就是Java和C++交互的一个中间层。Java可以通过JNI来调用C++代码,反之亦可。

HelloJNI

JNI在Java中的体现需要用native关键字来修饰,而需要使用库则使用System.loadLibrary("hello")来加载库。先来个最基本的HelloJNI。

1
2
3
4
5
6
7
8
9
10
11
12
public class HelloJNI {
static {
System.loadLibrary("hello");
}

private native void sayHello();

public static void main(String[] args) {
HelloJNI hello = new HelloJNI();
hello.sayHello();
}
}

使用Javac编译这个文件

1
javac -h . HelloJNI.java

之后会生成HelloJNI.class和HelloJNI.h两个文件。生成头文件中定义了对应Native的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class HelloJNI */

#ifndef _Included_HelloJNI
#define _Included_HelloJNI
#ifdef __cplusplus
extern "C" {
#endif
/*
* Class: HelloJNI
* Method: sayHello
* Signature: ()V
*/
JNIEXPORT void JNICALL Java_HelloJNI_sayHello
(JNIEnv *, jobject);

#ifdef __cplusplus
}
#endif
#endif

接下来就是实现这个Native的方法,需要导入jni.h和HelloJNI.h。

1
2
3
4
5
6
7
8
#include <jni.h>
#include <stdio.h>
#include "HelloJNI.h"
#include <iostream>
JNIEXPORT void JNICALL Java_HelloJNI_sayHello(JNIEnv *env, jobject thiz)
{
std::cout << "Hello JNI" << std::endl;
}

然后开始编译lib库,需要注意的是Java中System.loadLibrary("hello")这个lib的名称在编译库的时候需要加上lib,也就是libhello

1
2
3
g++ -c -fPIC -I${JAVA_HOME}/include -I${JAVA_HOME}/include/darwin HelloJNI.cpp -o HelloJNI.o

g++ -dynamiclib -o libhello.dylib HelloJNI.o -lc

最后执行下,cp就是classpath,是指定类运行所依赖其他类的路径。-Djava.library.path指定加载库的路径。

1
java -cp . -Djava.library.path=. HelloJNI

传递参数

通常调用lib库的函数需要传递一些参数,这就是需要JNI的帮忙了。

如果是基础类型直接使用就可以。在JNI都有和JAVA一一对应的基础类型,例如jint - int、jboolean - boolean。

JNI的基础类型也可以直接传入给C++的函数中。

复杂一点的是传递一个对象,需要从对象中拿到成员变量值。

首先需要搞清楚jobject和jclass的概念,其实和Java中的Object和Class的概念是一样的。Class可以理解为是一种模板,而Object则是具体的一个对象。下面代码中User就是一个类,而star就是一个具体的对象也就是Object

1
User star = new User();

假设有这样一个类User,有两个成员变量,name和password

1
2
3
4
5
6
7
8
class User {
String name;
String password;
User(String name, String password) {
this.name = name;
this.password = password;
}
}

定义了一个native方法来传递User的参数

1
private native void passUserObject(User user);

对应的JNI函数为

1
JNIEXPORT void JNICALL Java_HelloJNI_passUserObject(JNIEnv *env, jobject thiz, jobject user){}

在JNI中是不能直接使用user.name来获取的,必须提供给JNI一个成员变量的名称和类型他才能看得懂。而这两者都是Class的概念,因此需要先拿到user的class,这两种方法都可以拿到

1
2
jclass userClass = env->FindClass("packagename/UserData");
jclass cls = env->GetObjectClass(user);

接下来就是去拿成员变量的id,第二个参数是名称,第三个参数是类型。如果是自定义的类型则是"L+PackageName/Type;",包名依然是用斜杠分开。

1
jfieldID name_id = env->GetFieldID(cls, "name", "Ljava/lang/String;");

之后就是根据这个id在传进来的对象user中取出name

1
jstring name = (jstring)env->GetObjectField(user , name_id);

如果是int类型的参数可以直接用env->GetIntField(user, id)

枚举

如果是枚举类型则稍微复杂一点。枚举类型都有个方法ordinal是返回枚举值。

1
2
3
4
5
enum class VideoStreamType {
NotVideo, //VideoStreamType.NotVideo.ordinal return 0
Video,
Presentation
}

利用这个方法我们可以将枚举转化成int类型,然后再map成C++的枚举类型。

首先将枚举类型变量取出 - vsTypeJni_

1
2
jfieldID vsType_id = env->GetFieldID(eccVideoParasClass, "vsType","Lcom/star/VideoStreamType;");
jobject vsTypeJni_ = env->GetObjectField(videoParas, vsType_id);

然后调用ordinal方法,返回vsTypeJni_对应的int值,这个vsTypeJint就是我们想要的。

1
2
3
jclass vsTypeClass = env->GetObjectClass(vsTypeJni_);
jmethodID ordinal = env->GetMethodID(vsTypeClass, "ordinal", "()I");
jint vsTypeJint = env->CallIntMethod(vsTypeJni_, ordinal);

如果想返回枚举的话则需要先用Java枚举的values方法获取到所有存储枚举类型的数组,然后根据index得到对应的Java枚举类型。

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
inline jobject GetEnumObjectRingerType(RingerType type) {

jobject result = nullptr;

bool bAttached = false;
JNIEnv *env = JniBase::AttachEnv(JniBase::ms_jvm, bAttached);

if (env) {

jclass enumClass = JniBase::FindClass(env,
"com/star/RingerType");
jmethodID methodId = env->GetStaticMethodID(enumClass, "values",
("()[Lcom/star/RingerType;"));
jobjectArray valueArray = static_cast<jobjectArray>(env->CallStaticObjectMethod(
enumClass, methodId));
int index = GetEnumRingerTypeAtIndex(type);
result = env->GetObjectArrayElement(valueArray, index);

env->DeleteLocalRef(valueArray);
env->DeleteLocalRef(enumClass);
}

JniBase::DetachEnv(JniBase::ms_jvm, bAttached);

return result;
}

inline int GetEnumRingerTypeAtIndex(RingerType type) {
int result = 0;
switch (type) {
case RingerType::Outgoing:
result = 1;
break;
case RingerType::BusyTone:
result = 2;
break;
case RingerType::Reconnect:
result = 3;
break;
}
return result;
}

调用Java方法

在处理枚举类型的时候调用了Java方法,和获取变量一样,需要先获取方法id,第二个参数是方法名,第三个参数中括号中的是入参类型,括号后的是返回值,例如env->GetMethodID(class, "calculate", "(III)I",jint a, jint b, jin c)是这样的方法。

1
int calculate(int a, int b, int ) {}

然后就可以调用Java方法了

1
env->CallObjectMethod(object, methodId);

总结

对JNI来说,它只是提供了一个Java和Native代码之间的桥梁,因此没有太多复杂的东西,jclass供我们获取方法或者变量的id,一旦id拿到我们就可以处理对象了。

然而JNI也有缺点,它丢失了Java语言最大的特点:write once, run anywhere。并且由于多了一层导致程序更复杂并且在通信时有额外的消耗。

Tree

二叉查找树(BST)

二叉树是一棵树,其中每个节点都不能多于两个儿子。其平均深度为O(√N)。

二叉查找树是有特殊性质的二叉树,它的任意一个节点X,X的所有左儿子都比X小,X的所有右儿子都比X大。BST的平均深度是O(logN)。

以下是常用api的简单实现,BST大部分的处理都是采用递归的方式:

contains

由于BST的性质,只需要和节点X比较,如果比X大,则继续从X的右儿子寻找,否则从X的左儿子寻找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean contains(int data) {
return contains(data, root);
}

public boolean contains(int data, Node root) {
if (root == null) {
return false;
}
if (data > root.data)
return contains(data, root.right);
else if (data < root.data)
return contains(data, root.left);
else
return true;
}

insert

思路上和contains差不多,沿着树并根据节点大小查找,这儿并不处理重复值的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public Node insert(int data) {
return insert(data, root);
}

private Node insert(int data, Node root) {
if (root == null) {
new Node(data);
}
if (data > root.data)
root.right = insert(data, root.right);
else if (data < root.data)
root.left = insert(data, root.left);
else
;
return root;
}

remove

删除的情况比较复杂,如果节点X是树叶,那么直接删除即可,如果X只有一个儿子那么重新调整下父节点的链接。

如果X有两个儿子的话可以用右子树中最小的节点代替X,由于最小的节点只有一个儿子因此再remove一次会比较容易。如图删除2节点,那么先去2节点的右子树中找到最小的value为3,用3去替代2,再去删除3(这个比较容易)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void deleteKey(int key) { 
root = deleteRec(root, key);
}

Node deleteRec(Node root, int key) {
if (root == null) return root;
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = minValue(root.right);
root.right = deleteRec(root.right, root.key);
}
return root;
}

还有种策略叫做懒惰删除,就是在执行删除操作的时候该元素依然留在树种,只是将其标记为删除。

AVL树

如果向一个BST插入一个已经排序好了的集合,那么将有可能只有左子树和右子树,这样的话就和链表没有区别,因此引入了一个带有平衡条件的BST,条件就是左右子树的高度最多差1。并且所有的树操作都可以以时间O(logN)来执行。

下图就不是AVL树,因为节点2的高度是2,而节点8的高度是0,差为2。

对于AVL树来说,插入或者删除都有可能破坏AVL树的平衡性,由于每个节点最多两个儿子,因此一共有四种可能性破坏平衡条件:

  1. 左 - 左

  2. 左 - 右

  3. 右 - 左

  4. 右 - 右

其中1、4是对称情形,2、3是对称情形

单旋转

左 - 左

1
2
3
4
5
6
7
       z                                      y 
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2

右 - 右

1
2
3
4
5
6
7
  z                                y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4

双旋转

左 - 右

1
2
3
4
5
6
7
     z                               z                           x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2

右 - 左

1
2
3
4
5
6
7
   z                            z                            x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4

左 - 左的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node rotateWithLeftChild(Node y) {
Node x = y.left;
y.left = x.right;

// Perform rotation
x.right = y;

// Update heights
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), y.height) + 1;

// Return new root
return x;
}

左- 右的实现:先将其变为左 - 左的情况,在执行左 - 左的旋转

1
2
3
4
private Node doubleWithLeftChild(Node k3) {
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}

为了检查是否需要执行平衡操作需要在Node增加一个成员变量height

1
2
3
4
5
6
7
8
9
class Node {
int key, height;
Node left, right;

Node(int d) {
key = d;
height = 1;
}
}

因此,最后平衡的操作实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private Node balance(Node t) {
if (t == null) {
return t;
}

if (height(t.left) - height(t.right) > 1) {
if (height(t.left.left) >= height(t.left.right)) {
t = rotateWithLeftChild(t);
} else {
t = doubleWithLeftChild(t);
}
} else {
if (height(t.right) - height(t.left) > 1) {
if (height(t.right.right) >= height(t.right.left)) {
t = rotateWithRightChild(t);
} else {
t = doubleWithRightChild(t);
}
}
}
t.height = Math.max(height(t.left), height(t.right)) + 1;
return t;
}

伸展树

假设一棵树存了百万级别的key,但其中只有20%是经常用到的,如果用AVL树的话时间为O(logN),但是用伸展树的可能只需要O(1)。伸展树的基本思想是当一个节点被访问后,它会经过一系列的旋转被推到root上,这样下次再访问这个节点的话会更快,当然如果由于节点X被推到root上,而导致其他的节点依然处于较深的位置,这样并没有提升多少效率,因此伸展树也需要能平衡这棵树。

List/Stack/Queue

数组实现

数组的get操作花费常数时间,不过插入和删除却有可能有巨大开销。因为最坏的情况下,在位置0的插入将会把之后所有的元素后移一位。而删除第一个元素将把之后所有的元素前移一位。相反如果删除和插入都在表的高端,开销则没有那么大。

Java中用数组实现的列表为ArrayList,对get和set的调用花费常数时间,但插入和删除开销较大,除非是在末端进行。

以下为自己用数组实现的List,用mCount表示list中的元素个数。

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
//扩展数组
public void expandArray() {
T old[] = mItems;
mItems = (T[]) new Object[mItems.length * 2];
for (int i = 0; i < size(); i++) {
mItems[i] = old[i];
}
}

public void add(int index, T value) {
if (size() == mItems.length) {
expandArray();
}
for (int i = size(); i > index; i--) {
mItems[i] = mItems[i - 1];
}
mItems[index] = value;
mCount++;
}

public T remove(int index) {
T needToRemove = mItems[index];
for (int i = index; i < size(); i++) {
mItems[i] = mItems[i + 1];
}
mCount--;
return needToRemove;
}

public T get(int index) {
return mItems[index];
}

public void clear() {
mCount = 0;
mItems = (T[]) new Object[DEFAULT_CAPACITY];
}

//将Iterator作为内部类实现
class MyArrayListIterator<T> implements Iterator<T> {
private int current = 0;

@Override
public boolean hasNext() {
return current < size();
}

@Override
public void remove() {
MyArrayList.this.remove(--current);
}

@Override
public T next() {
return (T) mItems[current++];
}
}

https://github.com/StarIsCoder/DataStructure-BasicAlgorithm/blob/master/src/base/datastructure/MyArrayList.java

链表实现

使用链表查找开销较大,因为需要遍历整个list,但是对于删除和插入只需要操作某一个节点的next即可(需要知道该节点的位置),由于对第一项和最后一项的操作属于特殊操作,因此一般都会新增头节点和尾节点(也就是说一个空的list有两个节点),在Java的LinkedList中有addFirstaddLast等api。

以下为简单实现,用mSize表示元素个数:

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class MyLinkedList<T> implements Iterable<T> {
private Node<T> head;
private Node<T> tail;
private int mSize;

public MyLinkedList() {
init();
}

private void init() {
head = new Node<>(null, null, null);
tail = new Node<>(null, head, null);
head.next = tail;
mSize = 0;
}

public int size() {
return mSize;
}

public void add(T data) {
add(size(), data);
}

public void add(int index, T data) {
addBefore(getNode(index), data);
}

public void addBefore(Node<T> p, T data) {
Node<T> newNode = new Node<>(data, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
mSize++;
}

public void remove(int index) {
Node<T> needToRemove = getNode(index);
needToRemove.prev.next = needToRemove.next;
needToRemove.next.prev = needToRemove.prev;
mSize--;
}

private Node<T> getNode(int index) {
Node<T> p;
if ((size() / 2) > index) {
p = tail;
for (int i = size(); i > index; i--) {
p = p.prev;
}
} else {
p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
}
return p;
}

@Override
public Iterator<T> iterator() {
return new MyLinkedListIterator();
}

class MyLinkedListIterator implements Iterator<T> {
private Node<T> current = head.next;
private int count = 0;

@Override
public boolean hasNext() {
return current != tail;
}

@Override
public T next() {
T nextItem = current.data;
current = current.next;
return nextItem;
}
}

private static class Node<T> {
public Node(T data, Node<T> prev, Node<T> next) {
this.data = data;
this.prev = prev;
this.next = next;
}

public T data;
public Node<T> prev;
public Node<T> next;
}
}

对LinkedList来说不使用增强for循环那么搜索操作花费的时间为O(N^2),因为get需要O(N),但使用增强for循环的则是O(N),因此对于搜索操作来说,不管是Array还是Link都是O(N),都是低效的操作。

https://github.com/StarIsCoder/DataStructure-BasicAlgorithm/blob/master/src/base/datastructure/MyLinkedList.java

栈是限制插入和删除只能在一个位置上进行的表,特点是LIFO,一般只有push和pop操作,至于栈的实现用数组和链表都可以实现:

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
//数组实现
public T pop() {
if (count > 0) {
return items[count--];
}
return null;
}

public void push(T data) {
items[++count] = data;
}

//链表实现,bottom是栈底的元素
public void push(V data) {
Node<V> newNode = new Node<>(data);
Node<V> temp = bottom;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}

public V pop() {
Node<V> temp = bottom;
if (temp.next == null) return null;
while (temp.next.next != null) {
temp = temp.next;
}
V v = temp.next.value;
temp.next = null;
return v;
}

栈的应用,例如括号匹配,JVM中的栈帧,现代计算机的指令。

https://github.com/StarIsCoder/DataStructure-BasicAlgorithm/blob/master/src/base/datastructure/MyArrayStack.java

https://github.com/StarIsCoder/DataStructure-BasicAlgorithm/blob/master/src/base/datastructure/MyLinkedStack.java

队列

队列和栈有点类似,不过是FIFO,主要操作有enqueue和dequeue,也可以用数组或者链表来实现,以下为数组实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//用了first和last两个指针来表示头和尾
public void enqueue(T data) {
if (last == mItems.length - 1) {
last = -1;
}
mItems[++last] = data;
}

public T dequeue() {
T temp = mItems[first++];
if (first == mItems.length)
//绕回到开头
first = 0;
return temp;
}

队列有个问题,那就是下面这种情况,看上去都满了但其实有一些是空着的,最简单的办法就是绕回到开头,当然队列也有需要扩充的情况。

1
2
[- - - - - - - 9 7 6]
f e

队列的应用比如有Android中的MessageQueue等等。

https://github.com/StarIsCoder/DataStructure-BasicAlgorithm/blob/master/src/base/datastructure/MyArrayQueue.java

Bytecode Execution Engine

运行时栈帧结构

栈帧(stack frame)是用于支持虚拟机方法调用和方法执行的数据结构。它是虚拟机运行时数据区的虚拟机栈的栈元素。栈帧存储了局部变量、操作数栈、方法返回地址等。一个方法的调用到结束对应了一个栈帧的入栈和出栈。

局部变量表(Local Variable Table)

局部变量表是一组变量值存储空间,用于存放参数和方法内部定义的局部变量。最小的单位是变量槽(Variable Slot)。虚拟机是通过索引来定位哪个槽的。如果执行的是非static方法,默认第0位是this。

为了节省栈帧空间,局部变量表中的slot是可以复用的。因为方法中定义的局部变量不一定会覆盖整个方法体,比如for循环中的变量。

slot复用可能导致GC问题。

1
2
3
4
5
6
public static void main(String[] args) {
{
byte[] holder = new byte[64 * 1024 * 1024];
}
System.gc();
}

以上代码由于holder所占用的slot一直没人再使用,所以GC没法回收holder。如果希望回收holder,则只需要随便定义一个变量即可。

1
2
3
4
5
6
7
public static void main(String[] args) {
{
byte[] holder = new byte[64 * 1024 * 1024];
}
int a = 0;
System.gc();
}

操作数栈

也就是操作栈,方法执行过程中会有各种字节码指令向操作栈写入或者读取内容。用1+1来举例的话。先将两个1压入栈中,用过add指令将最顶上的两个元素弹出并相加之后将结果压入栈中。

方法返回地址

当一个方法开始执行之后,只有两种方式可以退出,一种是正常结束比如return。另一种则是运行过程中出现了异常。方法退出的实际过程就是等于把栈帧出栈。因此可能会恢复上层的局部变量表和操作栈,并将返回值压入调用者的操作栈中。

方法调用

方法调用并不等于方法执行,唯一的任务就是决定调用哪一个方法。

解析

在类加载的解析阶段主要就是将符号引用转化为直接引用,但是这样的一个前提就是在真正运行之前就能确定到底调用那个版本的方法并且在运行期间是不可改变的。符合这种“编译期可知,运行期不可变”的方法主要是static和private。

Java虚拟机有5条方法调用字节码指令:

  1. invokestatic: 调用静态方法。
  2. invokespecial: 调用实例构造器,私有、父类方法。
  3. invokevirtual: 调用虚方法。
  4. invokeinterface: 调用接口方法。
  5. invokedynamic: 运行时动态解析。
    以上1和2调用的方法都可以在解析阶段就确定唯一的版本。这类方法称为非虚方法,其他的称为虚方法。比较特殊的是final方法,虽然final是用invokevirtual指令来调用的但是由于它无法被重写因此也属于非虚方法。

分派

分派主要分为静态单分派、静态多分派、动态单分派、动态多分派。先来确定两个概念:静态类型和实际类型。

1
2
3
4
5
6
7
8
9
static class Father {

}

static class Son extends Father {

}

Father son = new Son();

上述代码中的Father叫做静态类型或外观类型,而Son叫做实际类型。两者最大的区别在于静态类型是编译期可知的,而实际类型是运行期间才可知的。

静态分派

顾名思义就是根据静态类型来决定方法版本的分派叫做静态分派。比如

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 Test {
static class Human {
}

static class Man extends Human {
}

static class Woman extends Human {

}

void helloWorld(Human guy) {
System.out.println("guy");
}

void helloWorld(Man man) {
System.out.println("man");
}

void helloWorld(Woman woman) {
System.out.println("woman");
}

public static void main(String[] args) {
Human man = new Man();
Human woman = new Woman();
Test test = new Test();
test.helloWorld(man);
test.helloWorld(woman);
}
}

1
2
3
Result:
guy
guy

在确定方法接受者是test之后,决定哪个方法的版本只和方法的参数数量和参数类型有关。而方法的参数类型中只有静态类型。

静态分派在虚拟机中的应用就是重载,重载是通过参数的静态类型来决定的。静态分派发生在编译期间,因此确定静态分派的动作不是由虚拟机执行的。

动态分派

动态分派就是根据实际类型来决定方法版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Test {
static class Human {
}

static class Man extends Human {
void sayHello() {
System.out.println("Man");
}
}

static class Woman extends Human {
void sayHello() {
System.out.println("Woman");
}
}

public static void main(String[] args) {
Human man = new Man();
Human woman = new Woman();
((Man) man).sayHello();
((Woman) woman).sayHello();

}
}

sayHello的版本决定于new之后的实际类型。这就是动态分派应用在了重写中。

使用javap查看字节码发现这里调用方法的指令用的是invokevirtual。这就有点类似于C++中virtual关键字的作用。

invokevirtual指令的解析过程主要有以下:

  1. 找到操作数栈顶第一个元素所指向的对象的实际类型。
  2. 如果找到与常量中的描述符和简单名称都相符的方法,则进行访问权限校验,如果通过则直接使用这个方法的引用。
  3. 否则,从下往上依次检索父类并且验证。
  4. 如果还找不到就跑出AbstractMethodError异常

重写的本质就是在运行期间把方法的符号引用解析到不同的直接引用上。

动态分派的实现

由于动态分派比较耗时,因此在方法区中建立一个虚方法表(Virtual Method Table),对于invokeinterface则是接口方法表(Interface Method Table),也就是用索引来提高性能,这一点又和C++的VTable非常相似。方法表中每个索引对应方法的实际入口,如果子类未实现则会直接指向父类。

关于Java动态类型、MethodHandle、Reflection之后另写一篇。

Search Algorithm

二分法

二分查找有两种,递归和循环。

时间复杂度:

  • O(Logn)
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
private int binarySearchIteration(int input[], int target) {
int l = 0;
int r = input.length - 1;
while (l <= r) {
int tmp = (l + r) / 2;
int value = input[tmp];
if (value == target) {
return tmp;
}
if (value > target)
r = tmp - 1;
else
l = tmp + 1;
}
return -1;
}

private int binarySearchRecursive(int input[], int target) {
return binarySearchRecursive(input, 0, input.length - 1, target);
}

private int binarySearchRecursive(int input[], int l, int r, int target) {
if (l <= r) {
int tmp = (l + r) / 2;
if (input[tmp] == target) return tmp;
if (input[tmp] > target)
return binarySearchRecursive(input, l, tmp - 1, target);
else
return binarySearchRecursive(input, tmp + 1, r, target);
}
return -1;
}

这个二分法是假设数组中没有重复的元素,如果有重复的元素并且希望能找到第一个或者最后一个index的话,这个算法就需要修改一下,当然在target大于或者小于input[tmp]的时候low和high的指针变化是一样的,区别在于target == input[tmp]的时候,这个tmp是否是最小的index,因此我们需要在判断下input[tmp -1]的值是否依然和target相等,因为二分法的数组都是排序好的,如果input[tmp -1]和target不相等,那说明确实找到了最小的index,如果相等那么在tmp之前还存在着更小的index。对最大值来说反之亦然。

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
int firstIndex(int[] input, int target) {
int l = 0;
int r = input.length - 1;
while (l <= r) {
int mid = (l + r) / 2;
//key code
if (input[mid] == target) {
if (mid == 0) {
return mid;
} else if (input[mid - 1] != target) {
return mid;
} else {
r = mid - 1;
}
} else if (target > input[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}

int lastIndex(int[] input, int target) {
int l = 0;
int r = input.length - 1;
while (l <= r) {
int mid = (l + r) / 2;
//key code
if (input[mid] == target) {
if (mid == input.length - 1) {
return mid;
} else if (input[mid + 1] != target) {
return mid;
} else {
l = mid + 1;
}
} else if (target > input[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}