推荐 google samples for android-architecture

在 Android 正式支持 data binding & MVVM 之前,MVP 可以算是最好的 android app 架构模式。

但是直到前不久,Google 才在 github 上提供了推荐的 android-mvp 做法。

虽然现在能找到各式各样实现 MVP 的 blog posts 和 samples,但是不得不说 Google 这次提供的 sample 依然惊艳十足,并且还是来自官方钦定。

Sample 将 view layer 和 presenter layer 需要协定的接口写到了一个单独的 xyz_contract 文件里,view 和 presenter 都需要实现各自的接口。

Sample 中 view layer 对应的是具体的 fragment,activity 只是充当了一个 startup facility。我觉得这个里可以做一个灵活的选择:如果引入 fragment 是没有必要的,那么可以直接将 view layer 放到 activity 中。

Model layer 的实现到可以不用那么讲究,如果项目中提供了 dependency injection 的设施,或者需要单独对 model layer 做 unit test(一般有这种需求手头应该有支持 DI 的设施了),则可以在 presnter – model 间协定一个 contract,present 持有实现了 contract 的对象,做到进一步解耦。

反之,如果不需要在 model layer 有太多的变化余地,则可以直接把具体的 model object 暴露给上层的 presenter。

讲真,如果没有 DI 协助,多一个 model contract 其实也挺多余。

Google samples 采用的是混合方式…看代码的话就知道了。

为了更快速的熟悉 google 推荐的做法,我花了点时间做了一个 login demo。view 直接放在了 activity,并且 model 直接暴露给了 presenter。

举个例子:

因为 view 中不能包含除了 UI 设置以外的代码,所以 login button 是否可用状态是 view 层监听输入框消息,并且将事件 delegate 到 presenter,presenter 通过判断后通知 view(调用 view 暴露的接口),改变按钮状态。

整个流程拆解后虽然变得繁琐,但是责任却变清晰了,所以在业务逻辑变得复杂的时候,这种 view – presenter 的拆分会逐渐体现出优点。

不过很明显,如果采用 MVVM,上面的实现会变得更加优雅、简单。

最后还是推荐一下 android devs 看一下这个 demo(虽然我不是很想做 android app -‘’-)。

让 Path 更自然

虽然 C++ 17 终于加入了对文件系统的支持,并且主流编译器的标准库也大都提供了一个 experimental implementation,但是就实际的反馈而言,当前的标准和实现都有点莫名其妙。

对,说的就是 filesystem::path

对于一个 path class 而言,最常用的操作不外乎:parent_path filename append/join

首先,对于函数 parent_path(),文档是这么描述的:

Returns the path to the parent directory.
Returns empty path if empty() or there’s only a single element in the path (begin() == –end().

但是对于路径形如 C:\path 对象,Visual Stuido 2015 update 2 提供的实现的调用 parent_path() 的结果居然是 C:

好吧,看来这个实现版本认为 C:C:\ 的 parent path。

然而这个认为却是极大错误的。

实际上,C:\ 才是和 Unix/Linux 下的 / 一样,是一个完整的根目录表示。而按照标准的要求描述,路径形如 C:\ 的 parent path 应该是一个空字符串。

不过这估计也得怪 Windows 奇葩的路径设计。谁能想到 C:tmp.txtC:\tmp.txt 是两个完全不同的路径表示呢?更别提还存在 \\server\path 这种 UNC 路径格式,以及必杀招:用以支持超过 MAX_PATH 的长路径的 \\?\C:\very-long-path 格式。

而对于 filename,实现上倒是没什么原则性的问题,但是 example 里反映的

1
2
fs::path("/foo/bar").filename(); // output bar
fs::path("/foo/bar/").filename(); // output .

给人一种刻板过头的感觉。你确定路径后面拖着的那个 trailing separator 是我可以要用来表示.的么?

不过也可能这是 unix/linux 下的一种神奇的用法,不过实在理解不能。

filesystem::path 不光提供了标准的 append,还顺带提供了纯字符串操作的 concat。抛开两个操作对应的符号重载是否美观不谈,操作 concat 的引入总给人一种 I wanna to make it complete 的无力感。

不过这个操作符对前面分辨 C:/C:\ 不能倒是提供了一个帮助,Orz。

补救

很早之前在 kbase 里也提供了一个路径类的实现 FilePath

在暂时无法接受 filesystem::path 的情况下,我对 FilePath 做了一次不大不小的重构。

首先把名字给换成了 Path,并且相关的几个操作也都保持和标准库一致。

但是这回 Pathparent_path 可是可以正确处理上面说的 dark cases 的;并且 filename 会在返回数据前机智的去掉 redundant trailing separator。

重复一遍,C:\\ 可不是 redundant trailing separator。

另外,filesystem::path 提供了一个 iterator 用来遍历路径的每个 component;而且实际上,parent_pathfilename 都是直接用这个 iterator 构建的。

不过因为时间所限,我没有在 Path 里加上这个 iterator。(我怕强迫症犯了一天内肯定写不完)不过也仍然提供了一个类似的操作 GetComponents

不同之处是这个函数会一下返回所有的 components,于是显得不那么 C++ philosophi compliant。不过还是将就着用吧,毕竟没有标准库实现那样有神奇的结果。

最新的代码可见 这里这里;实例参见附带的 unittest case

BTW:我删除了 kbase 的 dev 分支,打算换一种 git workflow。原来的 branch model 感觉有点不够拥抱变化。

挖坟:一个非侵入式的 buddy allocator 实现

离职前夕清理公司硬盘数据的时候,偶然发现原来自己去年三月份的时候还写过一个 non-intrusive buddy allocator 呢。因为时间太过久远加上之前写的时候没有加上该有的注释,导致花了一番功夫才看懂核心算法再写什么,更别说几个看起来完全不明觉厉的 offset-to-address 的计算。

于是我想,应该有必要整理一下,万一哪天真的需要呢?

Theory

Non-intrusive 的做法是,不在实际分配的内存中加入 meta-data,而是将 buddy-allocator 自身做成一个 allocation bookkeeper。

考虑到 allocator 要求管理的内存块必须是$2^k, k \in Z$大小,我们可以把一块内存对应的 bookkeeping 做成一棵 perfect binary tree。以大小为 8K 的内存块为例,对应的 perfect binary tree 结构如下:

每一个节点对应内存块中的一个可用区域(考虑从上往下的映射);最下层叶子节点对应完整的内存块,每个叶子节点对应一个最小的内存单元;父节点对应的内存区域包含子节点对应的内存区域。

而 perfect binary tree 又可以用数组来表示(实际上是特殊的 complete binary tree),一方面可以提升内存利用率(没有额外的前后继指针),又可以提高访问性能(减少动态分配以及连续内存带来的 cache-locality)。

Implementation

为了实现方便以及让分配、释放算法看起来更加简洁,作如下两个设定

  • 定义 maximum consecutive block (MCB) 为一个能被直接管理的最大的连续内存区域,大小仍然要满足$2^k$的要求
  • 用 bookkeeper tree 中的每个节点去保存对应内存区域的 MCB 的大小

于是得到对于每一个节点的递归定义

$$M(i)=\begin{cases}\max\left\{M(LC(i)),M(RC(i))\right\} & \text{otherwise}\\M(LC(i))+M(RC(i)) & M(LC(i))=M(RC(i))\end{cases}$$

上面 $M(i)$ 表示节点 $i$ 的 MCB 值,也即实际保存在节点里的值;$LC(i)$ 和 $RC(i)$ 分别表示节点 $i$ 的左子节点和右子节点。

仍然以前面 8K 大小的内存块举例,假设我们要从内存块里分配出大小 1K 的内存,那么这棵树的状态则变成如下样子:

后面实现过程中会发现这个定义解决掉了很多麻烦。

implementing allocation

分配算法大体顺序如下:

  1. 比较请求分配的内存大小和根节点的值,确认是否还有足够的空间可以分配。如果根节点的大小小于请求大小,很明显没有空间了。
  2. 如果空间足够,则沿着根节点向下搜索,采用 last-fit strategy,即最后一个满足要求的节点,找到目标节点。因为父节点覆盖的内存区域是包括子节点的,所以要使用 last-fit。
    实际上我们可以利用一个性质来简化第2步的逻辑:如果存在满足要求的节点,那么具有这个大小的节点所在的 depth/height 是固定的,和树当前状态无关(得益于前面 MCB 的定义)。于是我们可以在一棵假想的、全新的树上遍历,结合实际的树的信息去判断左右的走向。
  3. 将目标节点标记为0,然后回溯向上到根节点,修正路径上节点的信息。
  4. 假设目标节点在数组中的序号为 $i$,那么利用公式 $\text{offset} = (i+1) \cdot \text{block_size_needed} - \text{total_block_size}$ 算出分配的内存的起始序号相对于完整内存块的偏移量(其实就是内存块对应的第一个叶子节点在整个叶子节点中的序号)。
    至于这个公式怎么来的,后面再说。
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
size_t BinManager::Allocate(size_t slots_required)
{
assert(slots_required != 0);
if (slots_required == 0) {
return noffset;
}

size_t slots_needed = buddy_util::NearestUpperPowerOf2(slots_required);
if (max_consecutive_slot_[0] < slots_needed) {
return noffset;
}

size_t index = 0;
for (auto node_slots = total_slot_count_;
node_slots != slots_needed;
node_slots >>= 1) {
if (max_consecutive_slot_[buddy_util::LeftChild(index)] >= slots_needed) {
index = buddy_util::LeftChild(index);
} else {
index = buddy_util::RightChild(index);
}
}

// The relative distance from first slot in the bin just now allocated to the
// first slot in the underlying raw memory chunk.
size_t offset = (index + 1) * slots_needed - total_slot_count_;

max_consecutive_slot_[index] = 0;
while (index) {
index = buddy_util::Parent(index);
max_consecutive_slot_[index] = std::max(
max_consecutive_slot_[buddy_util::LeftChild(index)],
max_consecutive_slot_[buddy_util::RightChild(index)]);
}

return offset;
}

Deallocation

释放的过程就相对简单。

输入是前面 allocation 过程得到的 offset,首先转换利用上面的公式的变形(上面公式中的 block_size_needed 等于叶子节点的大小,为1),转换得到原来的 $i$,然后从 $i$ 指向的叶子节点开始,向上搜索,碰到的第一个标记为0的节点就是要找的目标节点,恢复其大小(前面提到的性质)。

接着仍然向上回溯到根节点,修正路径上的节点信息。

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
void BinManager::Free(size_t offset)
{
// The value of noffset can be regarded as positive infinity.
assert(offset < total_slot_count_);
if (offset >= total_slot_count_) {
return;
}

// Since multiple indices can be mapped into a single offset, we backtrace to
// locate the bin from bottom.
// The first bin we meet in the path whose slot count is 0 is the target.
// Incorrect |offset| may cause undesired deallocation for yet another bin.
size_t node_slot_count = 1;
size_t index = offset + total_slot_count_ - 1;
while (max_consecutive_slot_[index]) {
// Reached the root. The |offset| is incorret.
if (index == 0) {
return;
}

node_slot_count <<= 1;
index = buddy_util::Parent(index);
}

max_consecutive_slot_[index] = node_slot_count;
while (index != 0) {
index = buddy_util::Parent(index);
node_slot_count <<= 1;

size_t lc_slots = max_consecutive_slot_[buddy_util::LeftChild(index)];
size_t rc_slots = max_consecutive_slot_[buddy_util::RightChild(index)];

// Merge adjacent bins if possible.
if (lc_slots + rc_slots == node_slot_count) {
max_consecutive_slot_[index] = node_slot_count;
} else {
max_consecutive_slot_[index] = std::max(lc_slots, rc_slots);
}
}
}

Derivation of the Formula

最后解释一下怎么得到公式 $\text{offset} = (i+1) \cdot \text{block_size_needed} - \text{total_block_size}$。

首先做如下假设

  • 拥有的总内存块 total_block_size 为 $2^n$
  • 请求的内存大小 block_size_needed 是 $2^k$
  • 目标节点在数组中的序号是 $j$
  • perfect binary tree 对应的数组下标从1开始,i.e. 根节点在数组中的序号是1。这个假设是必要的,因为可以让左右子节点的公式更加简单

基于上述假设,我们就有

  1. 目标节点所在的高度一定是 $k$ (叶子节点位于高度0)。于是目标节点覆盖的第一个子节点的序号是 $j \cdot 2^k$。只需要不断的访问左子节点,直到叶子
  2. 第一个叶子节点的序号是 $ 2^n $
  3. 算得两个叶子节点的偏移量 $ \text{offset} = j \cdot 2^k - 2^n $
  4. 因为实现时数组下标 $i$ 从0开始,所以我们有 $ j = i + 1$
  5. 带入(3)中的式子,得到 $\text{offset} = (i+1) \cdot 2^k - 2^n $

公式就这样出来了,基本没有什么太复杂的东西。

假设数组从1开始也是一个常用的技巧,可以极大地简化运算和推导。所以你会看到算法导论里的数组一直都是从1开始的,因为是在可以极大的简化分析。而最后也只需要一个线性变换就拿到了实际环境下的公式。

安利时刻

对于非侵入式的 allocator 来说,前面实现的分配/释放只起到了 bookkeeping 的作用。你还需要自己提供一个能够分配/释放真实内存的模块,并利用前面实现的 buddy allocator 去管理。

一个完整的实现可以参考这里

这个实现里核心的部分是

  • MemoryBin:提供真实、连续的内存块,由一个个 slot 组成,每个 slot 大小可以设置,默认是 4KB
  • BinManager:基于 buddy allocator 的 bookkeeper,管理的基本单位是 MemoryBin 中的 slot
  • BuddyAllocator:前两个类的一个 facade,透露给外部用户的接口层

Trie, Ternary Search Tree, and Autocomplete

Trie

对于给定前缀p要求返回集合中所有匹配该前缀的元素的一类问题,例如autocomplete和字典搜索,Trie是一个很自然的选择。

前两天闲的蛋疼,于是自己做了一个quick-and-dirty的实现,也算是小小地回顾了下当年造数据结构轮子的光景。

不考虑优化手段,trie的核心性质在于:给定一个字母表T, 每个trie node除了表示当前一个字符之外,还有len(T)个child nodes,每个child node对应下一个可能的字符,于是一个字符串就这样被保存在了路径上。

直觉上看,trie是通过增加宽度来减小高度(高度和最长的单词长度一直),以减小查询的时间复杂度。

不过在细节上,node保存的信息可以有不同处理:

第一种做法是node保存从root到此node的完整路径信息,如图:

这么做的好处是之后需要路径信息时不需要额外的处理;当然不好的一点是node耗费的内存也变大了。

第二种做法是node仅保存当前字符的信息,如图:

我最后选择了第二种做法。

另外,每个node还要有一个end-of-word的mark,因为路径中间的node有可能已经是一个完整的单词,例如hehere的前缀,但是两个都是完整的单词。

实现提供了三个接口:

  • Insert负责插入一个word到trie中
  • Contains检查trie当前是否存在某个word
  • Search接受一个前缀,返回一个包含所有满足改前缀的word的集合

接口的实现如果采用递归的话,会变成弱智一般的简单。

不过好在就算是采用迭代,也不会麻烦到哪里去,除了Search

为了返回所有包含前缀的单词,实际上我们需要对trie做一个pre-order traversal,于是我们就有了一个stack。

一开始我是打算用stack保存一个node里还没有处理过的child nodes。这样就需要在迭代时不断往stack里加node,以及不断地从stack里取出node做处理。

我觉得这个思路很直接,并且觉着写起来会非常的流畅。但是有个不好的地方是,stack最多时需要保存所有的leaf nodes。而trie恰恰是通过增加宽度换取较低的高度,因此内存开销会比较大。

回龙观周杰伦大木老师提供了另外一个思路:利用stack保存正在处理的nodes。这样stack保存的恰好是构成目标字符串的路径,内存开销也成功压缩到了$O(h)$。

不愧是德艺双馨的亚洲人气小天王,服!

不过如果采用这个方法,还需要保存一个额外的信息,指明某个node已经处理过了多少child node,这样才能确定下一个要处理的child node。

别忘了一个node有字母表大小个children,而我们需要在node和他的child node之前来回切换。当然,如果语言自身提供了类似yield的设施,那实现就轻松多了。

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
std::vector<std::string> Trie::Search(const std::string& prefix) const
{
std::vector<std::string> words;

// Locate the node matching the last character of `prefix`.
const TrieNode* node = header_;
for (char ch : prefix) {
auto pos = Alphabet::GetCharacterIndex(ch);
if (pos == Alphabet::npos) {
return words;
}

const TrieNode* child = node->children[pos];
if (!child) {
return words;
}

node = child;
}

// We use `processing_nodes` as a stack to maintain nodes that are being processed.
using CludeNode = std::pair<const TrieNode*, size_t>;
std::vector<CludeNode> processing_nodes;
processing_nodes.emplace_back(CludeNode(node, 0U));
while (!processing_nodes.empty()) {
// Don't access `current` after having pushed another node into `processing_nodes`.
// Because the push might result in memory reallocation, rendering `current` an invalid
// reference.
auto& current = processing_nodes.back();
bool child_node_found = false;
while (current.second < current.first->children.size()) {
const TrieNode* child = current.first->children[current.second];
++current.second;
if (child) {
processing_nodes.emplace_back(CludeNode(child, 0U));
child_node_found = true;
break;
}
}

if (!child_node_found) {
if (processing_nodes.back().first->last_char_of_word) {
std::string word = prefix;
std::for_each(processing_nodes.cbegin() + 1, processing_nodes.cend(),
[&word](const auto& clude_node) {
word += clude_node.first->character;
});
words.push_back(std::move(word));
}

processing_nodes.pop_back();
}
}

return words;
}

对于写迭代形式的算法,我一直比较推荐采用循环不变式(loop invariant)去理解的做法。这几乎是我认为一个人能从算法导论里学到的最精华的基础

Ternary Search Tree

默认的trie内存开销比较大,所以又有很多针对内存做了优化的改进数据结构,ternary search tree便是其中之一。

如名所述,ternary search tree的一个node只有三个child nodes:left, middle, right。

三子节点的做法来源于,一次比较会产生三种结果:大、小、相等。

假设字符间的大小关系为字符在字母表的先后顺序,TST的核心规则如下:

  • 如果字符c和当前node的字符相等,表示当前字符匹配,则进入当前node的middle-child
  • 如果字符c比当前node的字符小,则进入当前node的left-child尝试匹配
  • 如果字符c比当前node的字符大,则进入当前node的right-child尝试匹配

如果把TST放在一个三维空间上考虑的话,我认为left-child和right-child更像是当前node的sibling nodes。

匹配过程就像从顶部的root node一直向下搜索,匹配时middle-node连接下一层的node,失败时在当前层由sibling nodes构成的平面上搜索。

不过因为二维平面更加容易理解,所以还是在这个维度上考虑。

InsertContains的非递归实现并不难,只要选择好loop invariant。

我在实现时选择的loop invariant是:

  1. 每次对一个字符的迭代结束后,一定停留在这个字符对应的node上
  2. 每次开始迭代时,始终尝试进入当前node(上一轮迭代结束停留的位置)的middle-node
  3. 第2步失败时,根据比较信息在左子树/右子树中找到目标node

并且为了实现方便,root node被我实现为一个sentinel node。

不过非递归的Search实现起来非常繁琐,因为一个node的三个child nodes不在一个语义层,所以需要为了遍历需要用两个stack维护不同的信息。

我在纸上尝试了一下就回头选择了递归地实现=’’=。

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
void SearchWord(Node* node, std::vector<std::string>* words, std::vector<char>* seq,
const std::string& prefix)
{
seq->push_back(Alphabet::GetCharacter(node->char_index));
if (node->end_word) {
std::string word(prefix);
word.append(seq->begin(), seq->end());
words->push_back(std::move(word));
}

if (node->children[Node::kMiddle]) {
SearchWord(node->children[Node::kMiddle], words, seq, prefix);
}

seq->pop_back();

if (node->children[Node::kLeft]) {
SearchWord(node->children[Node::kLeft], words, seq, prefix);
}

if (node->children[Node::kRight]) {
SearchWord(node->children[Node::kRight], words, seq, prefix);
}
}

std::vector<std::string> TernaryTree::Search(const std::string& prefix) const
{
std::vector<std::string> words;

// Locate the node matching the last character of `prefix`.
const Node* node = root_;
for (char ch : prefix) {
auto index = Alphabet::GetCharacterIndex(ch);
if (index == Alphabet::npos) {
return words;
}

const Node* next_node = node->children[Node::kMiddle];
if (!next_node) {
return words;
}

while (index != next_node->char_index) {
if (index < next_node->char_index) {
next_node = next_node->children[Node::kLeft];
} else {
next_node = next_node->children[Node::kRight];
}

if (!next_node) {
return words;
}
}

node = next_node;
}

if (node->end_word) {
words.push_back(prefix);
}

std::vector<char> sequence;
if (node->children[Node::kMiddle]) {
SearchWord(node->children[Node::kMiddle], &words, &sequence, prefix);
}

return words;
}

完整的实现在这里

Epilogue

我会写Trie是因为看到了the-trie-a-neglected-data-structure这篇文章,有张图片也是从文章里截取的。

而Ternary Search Tree则是不小心看到了efficient-auto-complete-with-a-ternary-search-tree,同样从文章里“借”了一张图片

再次对两位作者表示感谢!

其实一开始写实现时,我犹豫了一会儿是应该用raw pointer还是smart pointer。虽然raw pointer不是什么evil的东西,但是owned raw pointers对我来说始终有点不太舒服。

后来我看见了这个post,再联想C++提供的muli-paradigms的目的就是为了offer you the best-practice whenever you need, and you don’t pay what you don’t use

于是我就不断地给自己洗脑:nodes themselves are resources managed by a Tree.

再然后,我就释然了XD。

Reincarnated: Hello World

和某花闹掰之后神奇地发现托管在0GiNr上的blog被和谐了,何厚铧。

伤脑筋,这总得找个地儿写写口水文章吧,不然时间一长肯定被自己憋死,即影响了中华民族的伟大复兴,又对不起社会主义接班人的称号,罪该万死。

最后思来想去,索性直接在Github上架blog好了,一来有现成的工具,二来还省得麻烦。我这个人特别怕麻烦。

在几个社区上转了一圈,最后选择Hexo作为搭建工具,主要原因还是这东西用起来简单,不那么折腾,并且自带的默认主题还特别对我口味,interesting。

最后效果大概就是现在看到的样子,虽然比较简陋,但是起码可以用不是。反正写的都是口水文,掀不起风浪,传不了后世,make不了difference,欣然接受便是。

不过Hexo也有一个很麻烦的缺点,github上保存的只是最后生成的内容,并不是源内容,所以如果要在多台设备上使用,还要考虑程序自己的同步。

因为我没有Github的private repo,所以不能直接简单的把整个目录丢上去;不过我已经想到了一个还不错的workaround,回头试试。

如果要说可惜,大概是之前写了那么久的文章什么都没剩下了;不过,again, 反正口水文主要还是为了感动一下自己罢了,何厚铧。至于域名,懒得弄了,原域名就这样挂着好了,也懒得转移了,到期了就让他reclaimed好了,也省了之后每年一百多块钱的支出。

最后,某些人看上去表面强大,内心脆弱的很,这是心理残疾,估计难治。