记一次被 Android 进程复用坑的经历

因为需求需要,把某个功能拆分成一个独立的服务,并由一个全局的 service manager 去控制这个服务;服务对客户端暴露的实现也是通过 service manager

因为服务不需要运行在一个独立进程,manager 和 service 直接通过一个包含服务对象的 local binder 相互通信,看上去大概就这样:

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
public class LocalService extends Service {
public class LocalBinder extends Binder {
LocalService getService() {
return LocalService.this;
}
}
@Override
public IBinder onBind(Intent intent) {
return mBinder;
}
private final IBinder mBinder = new LocalBinder();
}
// This class is in fact a singleton.
public class ServiceManager {
private LocalService.LocalBinder mServiceBridge;
private ServiceConnection mConnection = new ServiceConnection() {
public void onServiceConnected(ComponentName className, IBinder service) {
mServiceBridge = (LocalService.LocalBinder)service;
}
public void onServiceDisconnected(ComponentName className) {
mServiceBridge = null;
}
};
public void startService() {
bindService(...);
}
public void stopService() {
unbindService(...);
}
}

考虑到语义的逻辑,我一开始选择了在自定义的 MainApplicationonCreate 中启动服务;并且为了避免不必要的消耗,在用户从主 activity 退出时,会停止这个服务。

过了几天,有同事在测试过程中反馈说,每次正常从 app 退出后,再次打开 app 运行涉及服务的功能都会抛 mServiceBridge 的空指针访问异常,但是下一次打开 app,相关功能又是好的。

我一开始觉得莫名其妙,因为对象空指针只能意味着服务没有被启动,但是启动服务是在 Application.onCreate 中进行的,这说不过去。

后来我不小心瞥到 DDMS 的进程列表,发现即使关闭了所有的 activity 退出了应用,相应的进程并没有退出…正如牛逼顿被苹果砸到的那个瞬间,一个想法一闪而过。

经过 demo 验证,问题出在 android 的进程复用上。

和传统 PC 上的做法不同,考虑到移动设备的特殊环境,即使所有的 activity 退出了,系统也不会马上回收 app 所在的进程。进程的资源、状态仍被保留,只是会进入一个不稳定状态:系统随时都能回收这个进程。

而如果在进程被系统回收前又打开了 app,那么系统会复用之前的进程。因为进程并没有被重新创建,所以 onCreate 函数被跳过了。在上面的环境下,就会跳过启动服务,导致 mServiceBridge 对象为空。

解决方案有两个:

  • 把启动服务的操作放到某个 activity 启动中,例如 the infamous splash activity
  • 主 activity 结束后强行退出进程

另外,根据上面的情况起码要明白,如果某个行为(例如一些设施的初始化)要放在 Application.onCreate 中完成,那么语义上这个操作形成的作用是跟随整个进程生命周期的;而进程的生命周期在 android 上是不可知的,所以相应的,这个行为的设计也要考虑到这点。

自己轮的 string_view 和它的小伙伴 tokenizer

String View

string_view 是 C++ 17 引入的一个基础设施,和 array_view 类似,表示一种 non-owning object

实际上,StringPiece 也是一种类似 string_view 的实现,并且一开始也作为提供 string_view 的范例实现之一出现在相关的 proposal 中。

但是既然标准委员会已经钦定了 string_view,我们就应该用它。

不过 VS 2015 update 2 附带的 STL 实现中并没有包含 string_view,于是出于其他需求,我做了如下两件小事:

  1. 按照标准要求,自己轮了一个 string_view实现
  2. 移除了 StringPiece,并用自己实现的 StringView 替换。

不过自己实现的代码,代码风格还是按照自己的偏好。

Tokenizer

某个需求是这样的:从文本读入一段数据,数据用固定标记分隔成一段一段,需要对每段数据做相关处理。

一种直接的方式是利用 kbase::SplitString 将数据分段。但是 SplitString 会一下将所有数据分段,在数据量很大的情况下会消耗不小的空间。而如果每段数据前后没有依赖关系,那么只要每次能获取到那一段的数据即可。

Tokenizer 就是在这种情况下被实现出来的。

Tokenizer 依赖前面提到的 StringView,因为它实际上也是一个 non-owning viewer,不会对原始数据造成任何可修改的影响。

Tokenizer 利用提供的 iterator 实现对数据段的遍历,并且利用标准的 begin end 可以直接支持 C++ 11 的 ranged-base for。额外的好处是让编译器对和 end() 比较的代码进行优化。

虽然从标准而言,begin()end() 应该具有常数时间复杂度,但是在以 token 为目标数据的条件下,begin() 很难做到常数时间复杂度,一般情况下需要 $O(l)$ 的复杂度,其中 $l$ 为数据段长度。不过好在初始调用并不频繁。

一个简单的范例看起来大概是这样的

1
2
3
4
5
6
7
8
9
10
11
std::string str = "anything that cannot kill you makes you stronger.\n\tsaid by Bruce Wayne\n";
std::vector<std::string> exp { "anything", "that", "cannot", "kill", "you", "makes", "you",
"stronger", "said", "by", "Bruce", "Wayne" };
Tokenizer tokenizer(str, " .\n\t");
size_t i = 0;
for (auto&& token : tokenizer) {
if (!token.empty()) {
EXPECT_EQ(exp[i], token.ToString());
++i;
}
}

具体实现见这里

推荐 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。