利用字符串驻留技术实现分层字段排序
2025年9月24日
(作者目前正在美国寻求就业机会。)
在最近遇到的一个实际问题中，我需要从缓冲区加载异构记录序列。记录布局在序列之前的头部中定义。每个字段都是数值类型，并具有一个唯一的名称，该名称由非空的字母数字段组成，段之间用点号分隔，段表示嵌套结构。字段名称是一个逗号分隔的列表，按记录布局的顺序排列。促使我写这篇文章的关键点是：嵌套结构不一定是连续的。在我转换后的表示中，需要嵌套结构是连续的。为了说明目的，这里将用于JSON输出。我想出了一个我认为很有趣的解决方案，并使用之前讨论过的技术在C语言中实现了它。
上面的描述可能本身就令人困惑，一个例子胜过千言万语，所以这里列出了一个包含7个字段的示例：
timestamp,point.x,point.y,foo.bar.z,point.z,foo.bar.y,foo.bar.x
其中point是一个子结构，foo和bar也是，但请注意它们在记录中是交错的。所以如果一个记录包含这些值：
{1758158348, 1.23, 4.56, -100, 7.89, -200, -300}
JSON表示将如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
{
"timestamp": 1758158348,
"point": {
"x": 1.23,
"y": 4.56,
"z": 7.89
},
"foo": {
"bar": {
"z": -100,
"y": -200,
"x": -300
}
}
}
|
注意point.z上移了，而foo.bar.z下移了，这样子结构在这个表示中就是连续的，这是JSON所要求的。按字典序对字段名排序可以作为一种简单的解决方案将它们分组在一起。然而，作为一个额外的约束，我希望尽可能保留原始字段顺序。例如，timestamp在原始表示和JSON表示中都是第一个，但排序会把它放在最后。如果所有子结构已经是连续的，则不应有任何改变。
使用字符串驻留的解决方案
我的解决方案是驻留段字符串，按照观察顺序为每个段分配一个唯一的、单调递增的整数令牌。在我的程序中，零被保留为特殊的“根”令牌，因此第一个字符串的值为1。具体的值并不重要，重要的是它们是单调分配的。
诀窍在于，字符串总是在先前令牌的“命名空间”中被驻留。也就是说，我们正在构建一个(令牌, 字符串) -> 令牌的映射。对于我们的段，该命名空间是父结构的令牌，顶级字段则在保留的“根”命名空间中被驻留。应用于示例时，我们得到令牌序列：
1
2
3
4
5
6
7
|
timestamp -> 1
point.x -> 2 3
point.y -> 2 4
foo.bar.z -> 5 6 7
point.z -> 2 8
foo.bar.y -> 5 6 9
foo.bar.x -> 5 6 10
|
我们的映射表如下：
1
2
3
4
5
6
7
8
9
10
|
{0, "timestamp"} -> 1
{0, "point"} -> 2
{2, "x"} -> 3
{2, "y"} -> 4
{0, "foo"} -> 5
{5, "bar"} -> 6
{6, "z"} -> 7
{2, "z"} -> 8
{6, "y"} -> 9
{6, "x"} -> 10
|
注意由于命名空间不同，"x"被分配为3和10。这很重要，否则foo.bar的字段将与point的顺序相同。命名空间赋予了这些字段唯一的身份。
一旦我们有了令牌表示，就按令牌字典序排序。这会将point.z拉到它的兄弟字段旁边。
1
2
3
4
5
6
7
|
timestamp -> 1
point.x -> 2 3
point.y -> 2 4
point.z -> 2 8
foo.bar.z -> 5 6 7
foo.bar.y -> 5 6 9
foo.bar.x -> 5 6 10
|
现在我们得到了具有最小重排序的“输出”顺序。如果子结构已经是连续的，则不会有任何变化。假设映射合理，这是O(n log n)复杂度，主要源于排序。
替代方案
在我想到命名空间之前，我最初的想法是驻留段的整个前缀。查找序列将是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
"timestamp" -> 1 -> {1}
"point" -> 2
"point.x" -> 3 -> {2, 3}
"point" -> 2
"point.y" -> 4 -> {2, 4}
"foo" -> 5
"foo.bar" -> 6
"foo.bar.z" -> 7 -> {5, 6, 7}
"point" -> 2
"point.z" -> 8 -> {2, 8}
"foo" -> 5
"foo.bar" -> 6
"foo.bar.y" -> 9 -> {5, 6, 9}
"foo" -> 5
"foo.bar" -> 6
"foo.bar.x" -> 10 -> {5, 6, 10}
|
最终它产生相同的令牌，并且这是一个更直接的字符串 -> 字符串映射。前缀充当了命名空间。然而，我这样写它是一种视觉证明：注意每个字段的字符串形成的直角三角形形状。从面积我们可以看出，将前缀作为字符串处理是O(n^2)二次时间，相对于段的数量！在我的实际问题中，输入从未大到需要考虑这个问题的程度，但我讨厌留下可避免的二次算法。
使用令牌作为命名空间将前缀扁平化为常量大小。另一个选项是为每个命名空间使用不同的映射。所以对于foo.bar.z，在根（字符串 -> 映射）中查找"foo"映射（字符串 -> 映射），然后在其中查找"bar"表（字符串 -> 令牌）（因为这是倒数第二段），然后在该表中驻留"z"以获取其令牌。那不会具有二次时间复杂度，但似乎比单一的、扁平的(令牌, 字符串) -> 令牌映射复杂得多。
C语言实现
由于标准库对我们没什么帮助，我建立在先前已定义的基础上，所以请参考那篇文章获取Str等基本定义。首先，令牌将是一个大小类型整数，这样我们永远不必担心令牌计数器溢出。我们会先耗尽内存：
我们正在构建一个(令牌, 字符串) -> 令牌的映射，所以我们需要为这样的键提供一个哈希函数：
1
2
3
4
5
6
7
8
9
|
uint64_t hash(Token t, Str s)
{
uint64_t r = (uint64_t)t << 8;
for (ptrdiff i = 0; i < s.len; i++) {
r ^= s.data[i];
r *= 1111111111111111111u;
}
return r;
}
|
映射本身是一个永远有用的哈希字典树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
typedef struct Map Map;
struct Map {
Map *child[4];
Token namespace;
Str segment;
Token token;
};
Token *upsert(Map **m, Token namespace, Str segment, Arena *a)
{
for (uint64_t h = hash(ns, segment); *m; h <<= 2) {
if (namespace==(*m)->namespace && equals(segment, (*m)->segment)) {
return &(*m)->token;
}
m = &(*m)->child[h>>62];
}
*m = new(a, 1, Map);
(*m)->namespace = namespace;
(*m)->segment = segment;
return &(*m)->token; // caller will assign
}
|
我们将使用这个映射将命名字段的字符串转换为令牌序列，所以我们需要一个切片。字段在记录内还有一个偏移量和类型，我们将通过其原始顺序来跟踪，我将使用一个索引字段（例如，指向原始头部的索引）来跟踪。同时跟踪原始名称。
1
2
3
4
5
|
typedef struct {
Str name;
ptrdiff_t index;
Slice(Token) tokens;
} Field;
|
为了对字段排序，我们需要一个比较器：
1
2
3
4
5
6
7
8
9
10
11
|
ptrdiff_t field_compare(Field a, Field b)
{
ptrdiff_t len = min(a.tokens.len, b.tokens.len);
for (ptrdiff_t i = 0; i < len; i++) {
Token d = a.tokens.data[i] - b.tokens.data[i];
if (d) {
return d;
}
}
return a.tokens.len - b.tokens.len;
}
|
因为字段名是唯一的，每个令牌序列也是唯一的，所以我们不需要在比较器中使用索引。
最后进入正题：分割列表并使用已建立的push宏构建令牌序列。排序函数并不有趣，可以简单到像libc的qsort加上上述比较器（和适配器），所以我只列出原型。
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
|
void field_sort(Slice(Field), Arena scratch);
Slice(Field) parse_fields(Str fieldlist, Arena *a)
{
Slice(Field) fields = {};
Map *strtab = 0;
ptrdiff_t ntokens = 0;
for (Cut c = {.tail=fieldlist, .ok=true}; c.ok;) {
c = cut(c.tail, ',');
Field field = {};
field.name = c.head;
field.index = fields.len;
Token prev = 0;
for (Cut f = {.tail=field.name, .ok=true}; f.ok;) {
f = cut(f.tail, '.');
Token *token = upsert(&strtab, prev, f.head, a);
if (!*token) {
*token = ++ntokens;
}
*push(a, &field.tokens) = *token;
prev = *token;
}
*push(a, &fields) = field;
}
field_sort(fields, *a);
return fields;
}
|
这里的用法表明Cut::ok应该反转为Cut::done，以便更好地进行零初始化。这是我需要考虑的。因为所有内容都是从竞技场分配的，所以不需要析构函数或类似的东西，因此这就是完整的实现。回到例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
Str fieldlist = S(
"timestamp,"
"point.x,"
"point.y,"
"foo.bar.z,"
"point.z,"
"foo.bar.y,"
"foo.bar.x"
);
Slice(Field) fields = parse_fields(fieldlist, &scratch);
for (ptrdiff_t i = 0; i < fields.len; i++) {
Str name = fields.data[i].name;
fwrite(name.data, 1, name.len, stdout);
putchar('\n');
}
|
这个程序将打印正确的输出字段顺序。在实际程序中，我们会保留字符串表，定义一个反向查找来将令牌转换回字符串，并在生成输出时使用它。我在我的探索性程序rec2json.c中正是这样做的，写得与上面介绍的方式略有不同。它使用排序后的令牌来编译一个简单的字节码程序，当针对记录运行时，产生其JSON表示。它将示例编译为：
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
|
OPEN # 打印 '{'
KEY 1 # 将令牌1作为键打印，即 "timestamp:"
READ 0 # 打印记录偏移量0处的double
COMMA # 打印 ','
KEY 2 # 将令牌2作为键打印，即 "point:"
OPEN
KEY 3
READ 8 # 打印记录偏移量8处的double
COMMA
KEY 4
READ 16
COMMA
KEY 8
READ 32
CLOSE # 打印 '}'
COMMA
KEY 5
OPEN
KEY 6
OPEN
KEY 7
READ 24
COMMA
KEY 9
READ 40
COMMA
KEY 10
READ 48
CLOSE
CLOSE
CLOSE
|
看到它写出来，我注意到了更多改进的空间。优化传递可以合并指令，例如，OPEN然后KEY在编译时连接成单个字符串，这样只需要一条指令。这个程序可以是15条指令而不是31条。在我的实际案例中，我不需要这么复杂的东西，但探索起来很有趣。