之前对Linuxtuples的元组空间表示提出了意见，这里简单介绍一个用golang重写的版本。
第一处变化在于元组空间换用trie存储。trie中按照tag串索引具有相同tag的元组列表；注意
到在被模板tag匹配之元组集当中的每一元组都同等地有效，在模板tag中出现通配符时，只要
对以当前结点为根的所有子树进行顺序的匹配，并返回第一个匹配结果即可。
换言之，trie的字母表即是tag串的字母表。允许将具有通配符的元组投入空间（这是有意义
的，比如通信方A写入一个元组t，等待通信方B填实t中的若干域后再将其取回），但用户应该
保证一次匹配的结果集（在实现中并不存在这一集合）中所有元组仍然同等地有效；这些具有
通配符的元组将严格按tag存储，并（除去匹配顺序不论）同等地具有被匹配的可能。特别
地，作为某一元组中元素的元组并不被元组空间索引：它们只是单纯的数据。
按照这一设计，trie中每个单词结点都映射到一个元组集合，而OUT原语的精确删除由trie提
供的方法
func (root *TrieRoot) ActionOnWord(word string,
action func(interface{}) (interface{}, bool)) (
info interface{}, isDeleted, isMatched bool)
保证，也即在集合变为空集时，删除对应的单词（结点本身是否被删除取决于它是否仍具有
子树，但这并不需要被使用者——即元组空间——所知）。
IN原语通过一次检索实现，即匹配tag后获得对应的元组集合，从而完成添加操作。
READ原语通过一次检索实现。
按tag检索的trie元组空间减少了原设计中大部分的冗余查找－匹配（无通配符的成功匹配是
无冗余的，失败匹配可以保证失败发生在最长的前缀上；有通配符的成功匹配保证匹配过程中
的每次失败匹配都发生在最长的前缀上，分支数不超过空间中具有相应前缀的元组集合数目，
这些前缀对应每个通配符产生的分支状况）。实现方面采取了golang内置的map, 可以认为在
tag串字母表有限的情况下，通过索引对分支指针进行操作的时间复杂度是常数级。
第二处变化在于用于传输的元组表示。原先的元组直接按照机内表示传输，接收后解析的开销
相对较小（分析量很小，内存分配也相对连续）；一个强调细节效率的实现可以考虑改进这一
过程，也即使用网络字节序传输，保留连续的串缓冲区。这里则为元组本身提供了序列化方
法，以给出相对通用的表示方式，同时分离元组的表示和传输（即，元组的传输不再与前端相
关；实际上，原先的表示也应当提供与其传输格式相对应的打包操作，而不是将操作混杂在
收发操作当中：这为前端的实现提供了一些便利——前端只需关心I/O的实现，以及原语的原子
性即可）。序列化的文法如下（大写标识符为非终极符，其他文法符号为终极符）：
TUPLE -> quoted_str(ELEMENTS)
ELEMENTS -> int ELIST | float ELIST | quoted_str ELIST | TUPLE ELIST
ELIST -> ,int ELIST | ,float ELIST | ,quoted_str ELIST | ,TUPLE ELIST | eps
其中int和float分别是十进制表示的有符号整数和浮点数，浮点数写成小数形式。
quoted_str是用双引号"括住的字符串。
元组序列化后的例子如下：
"sti?"("hello","s??i?"("world",32),64)
"s?f"("揉揉子",-3.14)
前一个元组包含四个元素，其中第二个元素是一个包含五个元素的元组。后一个元组包含三个
元素。例子中的元组都包含通配符，在产生元组结构时会预留出通配符对应的元素空间，但
通配符不对应实际的元素取值，因此括号中的元素值顺序对应tag串中非通配符的元素类型。
这样的文法也很容易通过界定,或)以及"（对应字符串元素）完成序列化和解析；元组元素的
序列化和解析可以自然地递归进行。在这一基础上，可以独立地编写元组空间服务器／客户端
软件；不过对于当前的package来说，这反倒变成了根据实际情况来定夺的应用——也即，私以
为tuple本身到此为止即可；改变限于内部，服务器端也一并推为策略一方。如果要继续实现
下去的话，就golang而言就是goroutine（并发）和sync包（同步访问）。当然，如果在同步
粒度上继续改进的话，一部分同步需要下降到trie的实现当中——一个可能的例子，是在通配符
分支的时候，对不同的分支使用各自的读写锁。实际上，这里可以要求每个节点具有自己的
读写锁，这样可以一步一步加锁－解锁，使得同一前缀上的不同进展之间的差距相对减小。
阅读(1549) | 评论(0) | 转发(0) |
