前言

提到Android的多线程机制，常用的有如下几种方式：

• AsyncTask: 封装了线程池和Handler，为 UI 线程与工作线程之间进行快速切换提供一种便捷机制。适用于当下立即需要启动，但是异步执行的生命周期短暂的使用场景。
• HandlerThread: 一个已经拥有了Looper的线程类，内部可以直接使用Handler。为某些回调方法或者等待某些任务的执行设置一个专属的线程，并提供线程任务的调度机制。
• ThreadPool: 把任务分解成不同的单元，分发到各个不同的线程上，进行同时并发处理。
• IntentService: 适合于执行由 UI 触发的后台 Service 任务，并可以把后台任务执行的情况通过一定的机制反馈给 UI。

尽管Android已经设计了基本的Handler异步消息机制提供给我们进行线程间通信，不过对于频繁得UI更新操作Handler用起来确实有点细碎，为了更加方便我们在子线程中更新UI元素，Android从1.5版本就引入了一个AsyncTask类，使用它我们可以非常灵活方便地从子线程切换到UI线程。

我们就从AsyncTask的基本用法开始，一起分析下AsyncTask源码，看看它是如何实现的。

使用AsyncTask

由于AsyncTask是一个抽象类，所以如果我们想使用它，就必须要创建一个子类去继承它。在继承时我们可以为AsyncTask类指定三个泛型参数，这三个参数的用途如下：

1. Params：在执行AsyncTask时需要传入的参数，可用于在后台任务中使用。
2. Progress：后台任务执行时，如果需要在界面上显示当前的进度，则使用这里指定的泛型作为进度单位。
3. Result：当任务执行完毕后，如果需要对结果进行返回，则使用这里指定的泛型作为返回值类型。

一个最简单的自定义AsyncTask就可以写成如下方式：

1

private class MyTask extends AsyncTask<Void, Void, Void> { ... }

前言

提到Android的多线程机制，除了我们常用的Thread来实现异步任务之外，还有

1. AsyncTask：封装了线程池和Handler，主要为了子线程更新UI；
2. HandlerThread：一个已经拥有了Looper的线程类，内部可以直接使用Handler；
3. IntentService：一个内部采用HandlerThread来执行任务的Service服务，任务执行完毕后会自动退出；

今天我们来根据平时的使用方式来分析一下第三个IntentSevice到底是什么怎么实现的？

IntentService的使用

IntentService继承了Service并且它本身是一个抽象类，因此使用它必须创建它的子类才能使用。所以这里我们自定义一个MyIntentService，来处理异步任务：

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

public class MyIntentService extends IntentService {

	private static final String TAG = "MyIntentService";
    private boolean isRunning = true;
    private int count = 0;

    public MyIntentService() {
        super("MyIntentService");
    }

    @Override
    public void onCreate() {
        super.onCreate();
    }

    @Override
    protected void onHandleIntent(Intent intent) {
        try {
	        //查看线程id
	        Log.i(TAG, intent.getStringExtra("params") + ", 线程id:" + Thread.currentThread().getId());
            Thread.sleep(1000);

            //从0-100渐增
            isRunning = true;
            count = 0;
            while (isRunning) {
                count++;
                Log.i(TAG, "MyIntentService 线程运行中..." + count);
                if (count >= 100) {
                    isRunning = false;
                }
                Thread.sleep(50);
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    @Override
    public void onDestroy() {
        super.onDestroy();
    }
}

概述

EventBus是Android中一个基于观察者模式的事件发布/订阅框架，开发者可以通过极少的代码去实现多个模块之间的通信，主要功能是替代Intent，Handler，BroadCast 在 Fragment，Activity，Service，线程Thread之间传递消息。优点是开销小，使用方便，可以很大程度上降低它们之间的耦合。 类似的库还有Otto ，今天就带大家一起研读 EventBus 的源码。

这是EventBus源码中的介绍：

1
2
3
4
5
6
7
8
9
10

/**
 * EventBus is a central publish/subscribe event system for Android. Events are posted ({@link #post(Object)}) to the
 * bus, which delivers it to subscribers that have a matching handler method for the event type. To receive events,
 * subscribers must register themselves to the bus using {@link #register(Object)}. Once registered, subscribers
 * receive events until {@link #unregister(Object)} is called. Event handling methods must be annotated by
 * {@link Subscribe}, must be public, return nothing (void), and have exactly one parameter
 * (the event).
 *
 * @author Markus Junginger, greenrobot
 */

EventBus 是Android上的以发布\订阅事件为核心的库。事件 (event) 通过 post() 发送到总线，然后再分发到匹配事件类型的订阅者 (subscribers) 。订阅者只有在总线中注册 (register) 了才能收到事件，注销 (unrigister) 之后就收不到任何事件了。事件方法必须带有 Subscribe 的注解，必须是 public ，没有返回类型 void 并且只能有一个参数。

EventBus3 与之前的相比，其主要差别在于订阅方法可以不再以onEvent 开头了，改为用注解。

实验

对于try-catch-finally语句中return的执行顺序，我们都有知道，finally块中的内容会先于try中的return语句执行，如果finall语句块中也有return语句的话，那么直接从finally中返回了，这也是不建议在finally中return的原因。

下面通过实验来看这几种情况的执行顺序到底是什么。

1、try中有return，finally中没有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class TryCatchTest {

	public static void main(String[] args) {
		System.out.println("test()函数返回：" + test());
	}

	private static int test(){
		int i = 0;
		try {
			System.out.println("Try block executing: " + ++i);
			return i;
		}catch (Exception e){
			System.out.println("Catch Error executing: " + ++i);
			return -1;
		}finally {
			System.out.println("finally executing: " + ++i);
		}
	}
}

本文来自： 从多项式乘法到快速傅里叶变换 — miskcoo

概述

计算多项式的乘法，或者计算两个大整数的乘法是在计算机中很常见的运算，如果用普通的方法进行，复杂度将会是$ \mathcal O(n^2) ​$的，还有一种分治乘法，可以做到 $\mathcal O(n^{\log_23}) ​$时间计算（可以看Karatsuba 乘法）。下面从计算多项式的乘法出发，介绍快速傅里叶变换（Fast Fourier Transform, FFT）如何在 $\mathcal O(n\log n) ​$的时间内计算出两个多项式的乘积。

准备知识

这里介绍一些后面可能会用到的知识（主要是关于多项式、卷积以及复数的），如果你已经知道觉得它太水了或者想用到的时候再看就跳过吧。

多项式

简单来说，形如 $ a_0+a_1X+a_2X^2+\cdots+a_nX^n $ 的代数表达式叫做多项式，可以记作$P(X)=a_0+a_1X+a_2X^2+\cdots+a_nX^n$，$a_0, a_1, \cdots, a_n $叫做多项式的系数，$X $是一个不定元，不表示任何值，不定元在多项式中最大项的次数称作多项式的次数

多项式的系数表示法

像刚刚我们提到的那些多项式，都是以系数形式表示的，也就是将 n 次多项式$ A(x) $的系数 $a_0, a_1, \cdots, a_n $看作 $n+1 $维向量$ \vec a=(a_0,a_1,\cdots,a_n)$，其系数表示（coefficient representation）就是向量$ \vec a$ 。

题目

编写两个任意位数的大数相乘的程序，给出计算结果。比如：

题目描述： 输出两个不超过100位的大整数的乘积。
输入： 输入两个大整数，如1234567 和 123
输出： 输出乘积，如：151851741

或者

1

求 1234567891011121314151617181920 * 2019181716151413121110987654321 的乘积结果

分析

所谓大数相乘（Multiplication algorithm），就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。

参考了很多资料，包括维基百科词条Multiplication algorithm，才知道目前大数乘法算法主要有以下几种思路：

1. 模拟小学乘法：最简单的乘法竖式手算的累加型；
2. 分治乘法：最简单的是Karatsuba乘法，一般化以后有Toom-Cook乘法；
3. 快速傅里叶变换FFT：（为了避免精度问题，可以改用快速数论变换FNTT），时间复杂度O(N lgN lglgN)。具体可参照Schönhage–Strassen algorithm；
4. 中国剩余定理：把每个数分解到一些互素的模上，然后每个同余方程对应乘起来就行；
5. Furer’s algorithm：在渐进意义上FNTT还快的算法。不过好像不太实用，本文就不作介绍了。大家可以参考维基百科Fürer’s algorithm

前言

研究算法能提高我们的编程功底，更好地编写出高效稳健的代码。今天，我们研究的是 —— 反转字符串。

1
2
3

//输入一个字符串，输出它的倒序字符串
input:  Hello
output: olleH

解法

反转字符串，确实没什么难度，但是我无意间搜索了一下，才发现这么一个看似简单的反转算法实现起来真可谓花样繁多。这里我们尽可能分别总结介绍一下。

1、使用字符数组倒序输出

最常规的解法，也是最容易想到的一种方法就是使用字符数组倒序输出。

具体思路是：倒序遍历字符串字符循环给char数组赋值

1
2
3
4
5
6
7
8
9

public static String strReverseWithArray(String string) {
    if (string == null || string.length() == 0) return string;
    
    char[] array = new char[string.length()];
    for(int i = 0; i < string.length(); i++){
        array[i] = string.charAt(string.length() - i - 1);
    }
    return new String(array);
}

前言

多线程的消息传递处理，从初学Android时的Handler，懵懵懂懂地照猫画虎，到后来一头雾水的疑惑它为什么这么复杂，再到熟悉之后的叹为观止，一步步地都是自己踩过的足迹，都是成长啊哈哈哈。虽然离出神入化的境界还远十万八千里呢，但Android中的Handler多线程消息传递机制，的确是研发技术学习中不可多得的一个宝藏。本来我以为自己之前的学习以及比较了解 Handler，在印象中 Android 消息机制无非就是：

1. Handler 给 MessageQueue 添加消息
2. 然后 Looper 无限循环读取消息
3. 再调用 Handler 处理消息

但是只知道整体流程，细节还不是特别透彻。最近不甚忙碌，回头看到这块又有些许收获，我们来记录一下吧。

在整个Android的源码世界里，有两大利剑，其一是Binder IPC机制，另一个便是消息机制。Android有大量的消息驱动方式来进行交互，比如Android的四剑客Activity, Service, Broadcast, ContentProvider的启动过程的交互，都离不开消息机制，Android某种意义上也可以说成是一个以消息驱动的系统。而Android 消息机制主要涉及 4 个类：

• Handler
• Message
• MessageQueue
• Looper

我们依次结合源码分析一下。

一、跨进程通信

为了演示方便，将Service与Activity处于不同的进程，可以在AndroidManifest.xml中，把service配置成android:process=":remote" ，也可以命名成其他的。

AIDL

（1） IRemoteService.aidl：定义Server端提供的服务接口

1
2
3
4
5
6
7
8
9
10
11
12
13

// IRemoteService.aidl
package com.cuc.myandroidtest;

import com.cuc.myandroidtest.MyData;
import com.cuc.myandroidtest.IServiceCallback;

interface IRemoteService {
    int getPid();			//获取服务端进程ID
    MyData getMyData();		//从服务端获取数据

    void registerCallback(IServiceCallback callback);		//注册服务端回调
    void unregisterCallback();
}

（2） IServiceCallBack.aidl：定义服务端回调接口，把Service的下载进度通知给客户端ClientActivity

1
2
3
4
5
6
7

// IServiceCallBack.aidl
package com.cuc.myandroidtest;

interface IServiceCallback {
    void onDownloadProgress(double progress);   //服务端下载进度通知
    void onDownloadCompleted();                 //下载完成通知
}

（3） MyData.aidl：定义传输的Parcel数据

1
2
3
4

// MyData.aidl
package com.cuc.myandroidtest;

parcelable MyData;

这是一道Google 笔试题

题目

一个有n个结点的连通图的生成树是原图的最小连通子图, 且包含原图中所有n个结点，并且有保持图联通的最少的边。最大生成树就是权和最大生成树，现在给出一个无向带权图的邻接矩阵，权为0表示没有边。

1
2
3
4
5

{{0, 4, 5, 0, 3}, 
 {4, 0, 4, 2, 3}, 
 {5, 4, 0, 2, 0}, 
 {0, 2, 2, 0, 1}, 
 {3, 3, 0, 1, 0}}

求这个图的最大生成树的权和。

A、11

B、12

C、13

D、14

E、15