Fastbit中的bitmap索引算法

目录 开源, 算法

摘要:bitmap 索引是一种典型的数据库索引方案,本文基于 Fastbit 软件包,使用实际用例对一些常用的 bitmap 索引算法进行了一个较为系统的介绍。

一、Fastbit是什么?

引用 Fastbit 的官方网站上的介绍:Fastbit是一个追随 NoSQL(Not Only SQL) 运动精神的开源的数据处理程序库,它提供了一系列的用压缩的 bitmap 索引支持的查询函数。在这里,我们关注的关键词是“bitmap 索引”。Fastbit 使用的是按列存储方式,其 bitmap 索引也是在按列存储的数据上建立起来的。

二、Fastbit 中的 bitmap 索引算法

Fastbit 的源代码有着非常清晰的结构。在 Fastbit 的源代码中,每个索引算法都用一个 C++ 类来实现,所有的索引算法类都是基类 index 的派生,并且在 fastbit 源代码中保存为以 i 开头的源文件。

下面是 Fastbit 中的索引类的派生关系图,从美观考虑,直接使用 xmind 思维导图而不是 UML 来展现了:

fastbit 索引算法派生关系图

下面我们将对其中部分算法进行简单的介绍。我们将这些索引算法分为几大类:基础算法、扩展算法、多层算法和多成分算法。

三、基础 bitmap 索引算法

基础的 bitmap 索引算法是最简单的 bitmap 索引算法,给出了 bitmap 索引的基本原理。

3.1 relic

relic (定义在 irelic.h 中,实现在 irelic.cpp ) 是最原始的 equality-encoded 算法,这个单词代表“遗迹”的意思。它可谓是最简单直观的 bitmap 索引算法。relic 为需要索引的每个值都建立一个 bitvector,在该 bitvector 中,只有等于该值的列才会被置 1,其它位都被置 0,如下表所示:

数据 索引(bitmap)
a b d e g
a 1 0 0 0 0
g 0 0 0 0 1
d 0 0 1 0 0
e 0 0 0 1 0
b 0 1 0 0 0
d 0 0 1 0 0
g 0 0 0 0 1
e 0 0 0 1 0
3.2 bin

bin (定义于 ibin.h,实现在 ibin.cpp)是 binned equality-encoded 算法,这里它代表“桶”的意思。它可以视为是 relic 的一种变形,它将值域分为几个不相交的区间,将原本是相等才置一的规则转变为值落在该区间内就置一,如下表所示。当然,relic 也可以视为 bin 的一个特例(将区间定义为 [a, a+ε)。bin 每个区间的范围由程序遵从某些规则设定,这些规则由命令行通过参数传入。

数据 索引(bitmap)
(…,b) [b,e) [e,…)
a 1 0 0
g 0 0 1
d 0 1 0
e 0 0 1
b 0 1 0
d 0 1 0
g 0 0 1
e 0 0 1
3.3 bin->range

range (定义于 ibin.h,实现于 irange.cpp)是 range-encoded 算法,这里它代表“范围”的意思。正如它字面所表达的意思,range 的每个 bitvector 标记着小于某边界值的值,如下表所示。因此,它可以视为是 bin 的一个累积表示,这也是 fastbit 软件包中所做的:首先构造 bin,然后累加转换成 range。值得注意的是,一般最后一列代表着小于无穷大,因此该 bitvector 全为 1,会被略去不写。

数据 索引(bitmap)
(…,b) (…,e) (…,g)
a 1 1 1
g 0 0 0
d 0 1 1
e 0 0 1
b 0 1 1
d 0 1 1
g 0 0 0
e 0 0 1
3.4 bin->mesa

mesa (定义于 ibin.h,实现于 imesa.cpp)是 interval-encoded 算法[1],它与 bin 类似,只不过它的区间之间有重叠部分。与 range 相同,在 fastbit 软件包中,它也是通过 bin 构造起来的。

数据 索引(bitmap)
(…,d) [a,e) [b,g) [d,…)
a 1 1 0 0
g 0 0 0 1
d 0 1 1 1
e 0 0 1 1
b 1 1 1 0
d 0 1 1 1
g 0 0 0 1
e 0 0 1 1

四、扩展 bitmap 索引算法

4.1 direkte

direkte (定义于 idirekte.h,实现于 idirekte.cpp)是丹麦语中的 direct,它与 relic 几乎是一样的,不同点只是它为小于最大值的所有值都建立了一个 bitvector(即使该值并不存在于列中)。

数据 索引(bitmap)
a b c d e f g
a 1 0 0 0 0 0 0
g 0 0 0 0 0 0 1
d 0 0 0 1 0 0 0
e 0 0 0 0 1 0 0
b 0 1 0 0 0 0 0
d 0 0 0 1 0 0 0
g 0 0 0 0 0 0 1
e 0 0 0 0 1 0 0
4.2 relic->slice

slice(定义于 irelic.h,实现于 islice.cpp)实现了 O'Neil'97 [2] 提出的 bit-slice 算法。它的基本思想就是首先将原始数据用二进制进行编码,bitmap 就是所有值的二进制编码表示的集合,bitvector 的个数由最大值的二进制表示决定,如下表所示:

数据 编码 索引(bitmap)
a 0 0 0 0
g 4 1 0 0
d 2 0 1 0
e 3 0 1 1
b 1 0 0 1
d 2 0 1 0
g 4 1 0 0
e 3 0 1 1
4.3 bin->bak

bak (定义于 ibin.h,实现于 idbak.cpp)是丹麦语中的 bin,因此它是 bin 的变形。它使用减精度来表示 bin 区间的中心,即它的每一个区间都是用一个更低精度的数来表示,具体来说就是四舍五入啦。下面是一个对 1-100 的数据列建立 bak 索引的输出,其中第一列表示区间的中心,第二三列代表区间最小最大值,第四列代表该区间内数据的个数:

index (equality encoding on reduced precision values) for data.a contains 19 bitvectors for 100 objects
1   1   1   1
2   2   2   1
3   3   3   1
4   4   4   1
5   5   5   1
6   6   6   1
7   7   7   1
8   8   8   1
9   9   9   1
10  10  14  5
20  15  24  10
30  25  34  10
40  35  44  10
50  45  54  10
60  55  65  11
70  66  74  9
80  75  84  10
90  85  94  10
100 95  100 6
4.4 bin->bak2

bak2 (定义于 ibin.h,实现于 idbak2.cpp)是 bak 的变形,也是以减精度来表示区间。但与 bak 不同的是,它将 bak 的每个区间区分为两个区间:小于减精度数的区间,和大于等于减精度数的区间。虽然注释中这样说,但实现时 bak2 是将 bak 的区间分为了三个:小于、等于和大于。下面是一个对 1-100 的数据列建立 bak2 索引的输出,每列的含义与 bak 中示例相同:

index (equality encoding on reduced precision values) for data.a contains 37 bitvectors for 100 objects
1   1   1   1
2   2   2   1
3   3   3   1
4   4   4   1
5   5   5   1
6   6   6   1
7   7   7   1
8   8   8   1
9   9   9   1
10  10  10  1   
10  11  14  4   
15  15  19  5
20  20  20  1
20  21  24  4
25  25  29  5
30  30  30  1
30  31  34  4
35  35  39  5
40  40  40  1
40  41  44  4
45  45  49  5
50  50  50  1
50  51  54  4
55  55  59  5
60  60  60  1
60  61  65  5
66  66  69  4
70  70  70  1
70  71  74  4
75  75  79  5
80  80  80  1
80  81  84  4
85  85  89  5
90  90  90  1
90  91  94  4
95  95  99  5
100 100 100 1

除了上面几个算法之外,扩展的算法还有 roster 和 keywords,这两种算法比较复杂,这里就不示例讲解了。

五、多层 bitmap 索引算法

有了几个基础的 bitmap 索引算法,我们就可以考虑将这些算法组合成一个层次的结构,构造出多层的 bitmap 索引算法。下面的几个算法,即是由前面的基础 bitmap 索引算法构造出来的二(多)层 bitmap 索引算法。

5.1 bin->ambit

ambit(定义于 ibin.h,实现于 ixambit.cpp)是 multilevel-range based算法,在这个算法中索引分为多层,每层索引都是基于 range 的索引。具体实现时,fastbit 首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 ambit。分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则由一简单算法确定,确定分组个数的算法为(第一个桶不参与分组):

ixambit.cpp:
33     // the default number of coarse bins is determined based on a set
34     // of simplified assumptions about expected sizes of range encoded
35     // bitmaps and word size being 32 bits.
36     const uint32_t defaultJ = static_cast
37         (nbins < 100 ? sqrt((double)nbins) :
38          0.5*(31.0 + sqrt(31.0*(31 + 4.0*nbins))));

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 ambit:

ambit 索引

5.2 bin->pale

pale(定义于 ibin.h,实现于 ixpale.cpp)是 two-level binned equality-range算法,它的索引分为两层,第一层为 binned equality(bin) 索引,第二层为 range 索引。在具体实现时,pale 首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 pale。与 ambit 相同,分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当 bin 桶数大于31时,默认第一层为16个组:

ixpale.cpp:
45     else { // default -- 16 coarse bins
46         if (nbins > 31) {
47         j = 16;
48         }
49         else {
50         j = nbins;
51         }
52     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 pale:

pale 索引

5.3 bin->pack

pack(定义于 ibin.h,实现于 ixpack.cpp)是 two-level binned range-equality 算法。它的索引分两层,与 pale 相反,第一层为 range 索引,第二层为 binned equality(bin) 索引。具体实现时,fastbit 首先构造 bin,然后对桶进行分组(调用bin::divideBitmaps),然后构造 pack。分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当bin桶数大于63时,默认第一层为31个组:

ixpack.cpp:
44     else { // default -- 31 coarse bins
45         if (nbins > 63) {
46         j = 31;
47         }
48         else {
49         j = nbins;
50         }
51     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 pack:

pack 索引

5.4 bin->zone

zone(定义于 ibin.h,实现于 ixzone.cpp)是 two-level binned equality-equality 算法,它的索引分两层,两层均为 binned equality(bin) 索引。它的实现方式也是首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 zone。其分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当bin桶数大于31时,默认第一层为14个组:

ixpack.cpp:
46     else { // default -- 14 coarse bins
47         if (nbins > 31) {
48         j = 14;
49         }
50         else {
51         j = nbins;
52         }
53     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 zone:

zone 索引

5.5 bin->fuge

fuge(定义于 ibin.h,实现于 ixfuge.cpp)是 two-level binned interval-equality 算法,fuge 为德语中 interstice 的表述。fuge 的索引分两层,第一层为 interval(mesa) 索引,第二层为 binned equality(bin) 索引,它也是采用首先构造 bin,然后基于 bin 构造 fuge 的方式。其分组粒度由 ncoarse=x 指定,否则默认的分组个数由下面算法确定:

ixfuge.cpp:
887     // default size based on the size of fine level index sf: sf(w-1)/N/sqrt(2)
...
899     if (ncoarse < 5U && offset32.back() >
900     offset32[0]+static_cast(nrows/31)) {
901     ncoarse = sizeof(ibis::bitvector::word_t);
...
913     else {
914         ncoarse = ncmax;
915     }
916     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 fuge:

fuge 索引

5.6 relic->bylt

bylt(定义于 irelic.h,实现于 ixrelic.cpp)是 two-level unbinned range-equality 算法,bylt 是丹麦语的 pack(binned 版本算法)。bylt 索引分两层,第一层为 range 索引,第二层为 unbinned equality(relic) 索引。在实现时首先构造 relic,然后对桶进行分组(调用bin::divideBitmaps),然后构造 bylt。分组粒度可以由 ncoarse=x 指定,bylt 保证每组中桶数是大致均匀的,否则由下面算法决定分组的个数:

ixbylt.cpp:
182     // default size based on the size of fine level index sf:
183     // (w-1) * sqrt(sf*(sf-N/(w-1))) / (2N)
184     if (ncoarse < 5U && offset64.back() > offset64[0]+(int32_t)(nrows/31U)) { 
185     ncoarse = sizeof(ibis::bitvector::word_t);
     const int wm1 = ncoarse*8-1;
...
199         ncoarse = ncmax;
200     }
201     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 bylt:

bylt 索引

5.7 relic->fuzz

fuzz(定义于 irelic.h,实现于 ixfuzz.cpp)是two-level unbinned interval-equality 算法,即 fuge 的 unbinned 版本,名字起源于 fuzzy 聚类/分类。fuzz 索引分两层,第一层为 interval(mesa) 索引,第二层为 unbinned equality(relic) 索引,具体实现时 fastbit 也是采用首先构造 relic,然后构造 fuzz 的方式。其分组粒度可以由 ncoarse=x 指定,否则默认分组个数由下面算法确定:

ixfuzz.cpp:
168     // default size based on the size of fine level index sf: sf(w-1)/N/        sqrt(2) 
169     if (ncoarse < 5U && offset64.back() > offset64[0]+nrows/31U) {
170     ncoarse = sizeof(ibis::bitvector::word_t);
...
182     else {
183         ncoarse = ncmax;
184     }
185     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 fuzz:

fuzz 索引

5.8 relic->zona

zona(定义于 irelic.h,实现于 ixzona.cpp)是 two-level unbinned equality-equality 算法,zona 是丹麦语的zone(binned 版本算法),其索引分两层,两层均为 unbinned equality(relic) 索引。首先构造 relic,然后对桶进行分组构造zona,分组个数默认为11个。下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 zona:

zona 索引

六、多成分 bitmap 索引

多成分(multi-component)bitmap 索引[3]是使用一组基数将数据值分解成多个部分,分别对每个部分进行 bitmap 索引的方案。原理描述如下:给定 n-1 个基数 { bn-1, bn-2, ..., b1},那么一个值 v 可以通过下式分解为 {vn, vn-1, ..., v1}:

数据值的分解

这和数的表示法类似,如果令 bi 都是 10,那么 vi 就是十进制表示法中第 i 位的值(大于等于0,小于10)。更准确的表述可以参考[3]。下面我们来看 fastbit 中的几个实现。

6.1 relic->fade

fade(定义于 irelic.h,实现于 ifade.cpp)是 multicomponent range-encoded 算法,即在每个部分中,是使用的 range 索引。下面来看一个 range-encoded 的例子:

fade 索引

在(b)图中,选择的基数是 9,那么索引就变成了一个单成分的 range 索引算法;在(c)图中,选择的基数是 <3, 3> 这样一个双成分编码,对分解出来的每个成分(大于等于0,小于3)生成 range 索引,就得出了 (c) 图中的结果。

6.2 relic->fade->sapid

sapid(定义于 irelic.h,实现于 isapid.cpp)是 multicomponent equality-encoded 算法,即在每个部分中是使用的 equality(relic) 索引。下面来看一个 equality-encoded 的例子:

sapid 索引

在(b)图中,选择的基数是 <3, 4> 这样一个双成分编码,对分解出来的每个成分生成 relic 索引,就得到了 (b) 图中的索引结果。

除了这两个索引算法之外,还有 sbiad(multicomponent interval-encoded),egale(multicomponent equality code on bins), entre(multicomponent interval code on bins), moins(multicomponent range code on bins)这几个索引算法。从括号中我们可以大致猜出这些索引的实现方式,但是由于我们现在没有一个很好的示例展现方式,用实际用例来展现这些索引算法的效果将会留给以后的文章进行。

七、总结

这篇文章基于 fastbit 软件包,加以实际的用例对常用的 bitmap 索引算法进行了一个较为系统的介绍。不过生成 bitmap 索引仅仅是第一步,bitmap 索引在存储时会有很大的开销,在不损害(较少损害)查询效率的情况下,对 bitmap 索引进行有效的压缩是一个非常有挑战性的课题。除了 bitmap 索引的生成和存储之外,在不同类型的 bitmap 索引上实现高效的各种类型的查询,也是一个值得进一步探讨的问题。我们很高兴地看到 fastbit 软件包实现了很多这些相关领域的算法,为我们提供了非常宝贵的资料。

参考文献

[1] C-Y. Chan and Y. E. Ioannidis, An efficient bitmap encoding scheme for selection queries, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1999.
[2] P. O’Neil and DalIan Quass, Improved Query Performance with Variant Indexes, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1997.
[3] C-Y. Chan and Y. E. Ioannidis, Bitmap Index Design and Evaluation, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1998.

Math in CS:置换的轮换分解

目录 数学, 算法

随便一本《近世代数》或者《抽象代数》书上在讲到置换群的时候,应该都会讲到这样一个定理:
任何一个置换都可以表示为不相交轮换的乘积,若不计因子的顺序,其分解式是唯一的。

一、简单解释

没有数学背景的人,这句话很难读懂,下面我们来看一个简单的例子。假设我们有这样一个置换 P:

1, 2, 3, 4, 5
2, 5, 4, 3, 1

那么这个置换是什么样的轮换的乘积呢?我们先从 1 出发,1 被换到 2,2 被换到 5,5 又被换到 1,这就是一个轮换;然后再从 3 出发,3 被换到 4,4 又被换到 3,这又是一个轮换。也就是说 P 是两个不相交轮换 (1, 2, 5) 和 (3,4) 的乘积。

二、一个应用:全排列判断问题

下面我们来看这个定理有什么作用,考虑下面这道题目[1][2]:

给一个 n 长的数组,判断它是否为一个 1, 2, ..., n 的全排列,要求在线性时间,常数空间内实现。

我们可以容易看到,每个全排列都可以视为 1, 2, ..., n 上的一个置换。问题就转化为检测该数组是不是一个 1, 2, ..., n 的置换。由本文开头提到的定理可知,我们只需要检查该置换是不是由不相交的轮换构成的即可。

还是上面那个例子,怎么检查

1, 2, 3, 4, 5
2, 5, 4, 3, 1

是不是一个置换呢?首先从 1 开始,a[1]=2,那么再检查 a[a[1]]=a[2]=5,然后再检查a[a[a[1]]]=a[5]=1,这样就发现了一个轮换 (1, 2, 5)。然后接下来检测第二个,第三个轮换...

如何保证检查的高效以及所有轮换都不相交呢?我们每次检查完一个数,就将它置负,这样遇到负值,循环就终止了。如果终止前检查的那个数与起始的数相同,那么我们就发现了一个轮换,否则它就不是一个轮换,说明 P 不是一个置换。由于检查过的轮换中的数字都被置为负值,所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值,且循环正常终止,那么说明它们都在不相交的轮换里,那么 P 就是一个置换。

如果想要查找过程不影响最终数组的值,到最后把所有置负的元素都重新置正即可。

代码实现如下[2]:

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
 * the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
  int i, j;
  if (a == NULL)  return 0;     /* Test input */
  a[0] = 1;
  for (i = 1; i <= n; ++i)      /* Test input */
    if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
      a[0] = 0;
      return a[0];
    }

  for (i = 1; i <= n; ++i)
    if (a[i] > 0) {
      j = i;
      while (a[j] > 0) {        /* Follow the cycle */
        a[j] = -a[j];
        j = -a[j];
      }
      if (j != i)  a[0] = 0;    /* Test the cycle */
    }

  for (i = 1; i <= n; ++i)
    a[i] = a[i] > 0 ? a[i] : -a[i];

  return a[0];
}

三、另一个应用:100 囚徒碰运气问题

那么这个定理还有其它的用处没有呢?考虑下面这道题目[3][4]:

100 个囚犯,每人有一个从 1 到 100 的不重复不遗漏的号码,国王把这些号码收集起来,打乱放进 100 个箱子里,每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前,每人可以打开至多 50 个箱子来寻找自己的号码,可以一个一个打开(即可以根据之前箱子里看到的号码来决定后面要打开的箱子)。如果有一个囚犯没有找到自己的号码,那么这 100 个人一起被处死;只有当所有的囚犯都找到了自己的号码,他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策,但是一但打开了箱子,他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率?

显然,每个人随机选 50 个箱子打开,100 个人的存活概率会是 1/2 的 100 次方,即1/1267650600228229401496703205376,可以小到忽略不计。但是事实上有一种极简单的办法,其存活概率高达 30% 。至于有没有更好的办法?我不知道。

存活率达 30% 的策略就是:

囚犯打开自己号码对应的箱子,就按照箱子中的号码打开另一个箱子,一直到找到自己号码或者选50 次为止,这样就能保证整体有 30% 的存活概率。

这个策略背后的数学原理是什么呢?其实国王所作的事情,就是一个 1 到 100 元素集合的置换,囚犯所做的事情,就是顺着自己号码所在的轮换找自己号码。那么什么时候所有人都不用死呢?就是这个置换中所有的轮换长度都不大于 50,因为每个囚犯号码的轮换都不大于 50,那么他总能在 50 次以内找到自己的号码。

怎么计算这个概率 P 呢?{这个置换中所有的轮换长度都不大于 50 的概率},就是 1 - {存在轮换长度大于 50 的概率},进而 1 - {存在轮换长度为 51, 52, ..., 100 的概率},由此,我们可以得到下面的等式:

P=1-\frac{1}{100!}\sum_{k=51}^{100}\binom{100}{k}(k-1)!(100-k)!=1-\sum_{k=51}^{100}%20\frac{1}{k}=1-(H_{100}-H_{50})

其中,Hn 代表调和数(Harmonic Number)。虽然调和数没有精确的公式,但是我们知道调和数和自然对数有着密切的联系[5],那么我们就可以用自然对数来近似:

P\approx1-(ln(100)-ln(50))=1-ln(2)\approx0.30685281944005469059[6]

因此,我们可以得到,使用这种策略 100个囚犯的存活概率 P 约为 30%。

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[3] http://tydsh.spaces.live.com/Blog/cns!435F1A315756AD5D!833.entry
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是:0.31182782068980479698,Bash 代码:

STR="1-("
for i in `seq 51 99`; do
  STR+="1/$i+"
done
STR+="1/100)"
echo $STR | bc -l

25 马问题

目录 算法

这是以前在 TopLanguage 讨论组讨论过的一道题目 ,题目描述为:

有 25 匹马和 1 个赛场,但赛场只有 5 条赛道,即一次只能给最多 5 匹马提供比赛机会,并且不能计时。请问如何设计比赛策略得到最快的 3/5 匹马,使得使用赛道的次数最少。

我想了一下,下面尝试给出我的分析,如果不对的话,还请指正。

一、决出前三名的策略

决出前 3 名网上有很多讨论,答案是 7 次,没有见过更少的,策略如下:

1. 将 25 匹马分成 5 组,分别赛一轮,得出一个先后顺序,共 5 轮。
2. 将每组的头马组成一组,再赛一轮,得出一个先后顺序。这第 6 轮能确定第一名。
3. 将最快一组的二三名,第二那组的一二名,以及第三那组的第一名五匹马放在一起,再赛一轮。这第 7 轮的前两名就是最终的二三名。总共赛 7 轮。

下面是分析。不失一般性,在赛 6 次之后,我们假设这 25 匹马的序号为:

A1 A2 A3 A4 A5  // 1 <-------
B1 B2 B3 B4 B5  // 2  |     |
C1 C2 C3 C4 C5  // 3 Main   |
D1 D2 D3 D4 D5  // 4  |  Extended
E1 E2 E3 E4 E5  // 5 <--    |
--------------  //          |
A1 B1 C1 D1 E1  // 6  {A1} <-

其中主矩阵列出了 25 匹马的序号,扩展矩阵的每行是每轮比赛的结果。我们可以看到主矩阵的行有序,第一列有序,那么现在我们知道第一名是 A1。

由于已知 A1 是第一名,第二名肯定是在每轮中紧挨在 A1 后面的,因此第二名的候选集为 {A2, B1}。

它们两个占不满 5 个赛道,我们再来看第三名的候选集。第三名在每轮中只可能是挨在第一或第二名的后面,也就是说在 {A1} U {A2, B1} 的后面,那么第三名的候选集就是 {A2, A3, B1, B2, C1},正好 5 匹马(第二名的候选集肯定包含在第三名候选集中)。那么第二三名只可能在这 5 匹马中,因此我们只需要让 {A2, A3, B1, B2, C1} 这 5 匹马再比一次,得到前两名,与 {A1} 合起来就是总的前三名。这样总共的比赛次数是 7 次。

2. 决出前五名的策略

决出前 5 名,就比较复杂了,我们按照同样策略再往下思考:

{A2, A3, B1, B2, C1} 决出前两名,有几种可能呢?如果它们没有比过,可能性就是从 5 个中取 2 个后的排列数,20 种可能。但是我们前面的比赛已经得到了一些快慢信息,我们就可以发现,第 7 轮 {A2, A3, B1, B2, C1} 决出前两名只有 5 种可能情况:

A2 A3 B1       B2/C1 * // 7  {A1, A2, A3}
B1 B2 A3/C1    *     * // 7  {A1, B1, B2}
B1 C1 A2/B2    *     * // 7  {A1, B1, C1}
A2 B1 A3/B2/C1 *     * // 7  {A1, A2, B1}
B1 A2 A3/B2/C1 *     *

去掉可交换的 A2 B1,其实只有 4 种情况。我们分别来考虑这 4 种情况:

1. {A1, A2, A3}

第四名肯定是 {A1, A2, A3} 之后的马,候选集为 {A4, B1};元素不足 5,再推一下第五名,即{A1, A2, A3} U {A4, B1} 之后的马,候选集为 {A4, B1, A5, B2, C1},只有 5 匹马。就是说第四、五名可以从这五匹马中产生,那么我们只需要再比一轮,取前两名,与 {A1, A2, A3} 并起来就能得到整个的前 5 匹马。那么最少的比赛次数是 8 次。

2. {A1, B1, B2}

这种情况下,同理,第四名候选集为 {A2, B3, C1} ,第五名候选集为 {A2, A3, B3, B4, C1, C2, D1},元素多于 5 个。因此我们必须先让 {A2, B3, C1} 比赛得到第 4 名,才能将第五名候选集的元素个数减少到 5 个以内。穷举:第 8 轮 A2 第一,可以消去 {C2, D1, B4, A2};B3 第一,可以消去 {B3, A3, C2, D1};C1 第一,可以消去 {C1, A3, B4},均能保证第五名的取值集合减少到 5 以内,因此只需要再一轮,就可以得到第五名。总的比赛次数是 9 次。

3. {A1, B1, C1}

同理,第四名候选集为 {A2, B2, C2, D1},第五名候选集为{A2, A3, B2, B3, C2, C3, D1, E1}。第四名无论取哪个,都会消去四个第五名候选集中的元素,总的比赛次数仍然是 9 次。

4. {A1, A2, B1}

同理,第四名候选集为{A3, B2, C1},第五名候选集为{A3, A4, B2, B3, C1, C2, D1}。第四名无论取哪个,至少消去第五名候选集中的 3 个元素,总的比赛次数也是 9 次。

穷举结束了,现在我们可以得出结论:最坏情况下该策略决出前 5 匹马的最少比赛次数是 9 次。

三、扩展问题

我有一个问题是:这种策略下取3, 5名比赛次数一定是最少的吗?有没有数学证明?

再扩展一点儿,如果需要求前 n 名,最少需要比赛几次?

在我们的这种策略下,因为主矩阵只有 5 行,每行还是有序的,那么求下一名的候选集最多有 5 个元素。也就是说多求一名,至多需要增加一轮比赛。什么情况下可以少于一轮呢?当已经确定第 n 名的情况时,第 n+2 名的候选集元素少于 5 个,我们就可以一轮比赛确定两个名次了。

我还比较好奇的是,如果需要决出所有 25 匹马的快慢顺序,最坏情况下至少需要比赛几次?

在我们这种策略下,假设 f(n) 是第 n 名最坏情况下的最少比赛次数,我们已知 f(1) = 6, f(2) = f (3) = 7, f(4) = 8, f(5) = 9,f(n) <= (n-5)+9 = n+4。那么 f(25) = f(20)+1 <= (20-5)+9 + 1 = 25 次,其上界应该是 25。但其准确值怎么确定?穷举就太困难了。 但是如果题目要求是确定 25 个的全部顺序,我们这种策略未必是最好的。这时候这题可以看成 n 路归并排序,并且可同时比较 n 个数的优化问题。过程中有很多可优化的可能。比如我们预处理时可以对每行和每列都排一下序,能否可以得到一些额外的信息?当主矩阵(去掉已确定顺序的元素)显得不那么平衡时,用扩展矩阵中的比较信息是否可以将主矩阵平衡一下,或者消去某些行列,这样做是否有帮助?