TCS 课堂笔记:数据库存储问题

作者: , 共 618 字

理论计算机 (I) 课上讲的一个问题,很有意思。

已经一个 n , m 和 \( \{1,2,\cdots, m\}\) 里 n 个数,设计一种保存这 n 个元素的表的数据结构形式,使得对 \( \{1,2,\cdots, m\}\) 中任何一个数,可以最少的查询次数(每次查询,可以选择一个位置,然后你能知道表中这个位置的数据),获知这个数是否在表中。

如果设计这个表为有序表,用二分法需要 \( \log n\) 次查询。

有序表是最优的么?

举一个例子,一个保存 1 , 2 , 3 里面的两个数的有序表,要想知道 2 是否在这个表里面,至少需要两次查询。可不可以用一种特定的数据结构,使得一次查询就能判定任何一个数是不是在数据库里面?

结论是可能的,见下图:

sorted table

一般的,假如表里的 n 个数的范围是 1 , 2 ,..., 2n-2 ,即 \( m=2n-2\) ,可以设计一种方法,使得,对于任何一个数, 只需要查询一次 ,便能知道这个数是否在这个表里面。

课堂上有同学当场就想出设计方法,向他致敬!

另外,利用广义的 Ramsey 定理,对于固定的 n ,能够证明当 m 足够大时,无论你怎么设计那个表的结构,也至少需要 \( \log n\) 的查询次数。

一个很神奇的问题。相关论文 Should Table be Sorted? , 上面的图片也来自这篇文章。

Q. E. D.

类似文章:
Rob Pike, 最伟大的 C 语言大师之一 , 在 Notes on C Programming ( 英文原文 ) 中从另一个稍微不同的角度表述了 Unix 的哲学 :
编程 » Java, Matlab
Matlab 2008b 才开始引入 containers.Map ,这是 Matlab 唯一的数据结构 ( 这里的数据结构是指自带一定逻辑性的数据结构,不包括普通数据类型 )。如果要有其它,比如 Queue、Set 等数据结构,只能自己编写一个。File Exchange 上有不少人做过这个工作,我也写过 Queue、List、Vector 的 Matlab 对象 。不过 Matlad 的面向对象编程效率极低,这种方法只能用于不太注重效率的场合。解决这个问题的另外一个方法是使用 Java 对象。
Excel 多表合并和查询是一个应用很广泛的问题。下面是一个简单的例子,我们需要从两张数据表里,得出每个行业的股票波动率平均值。第一个数据表保存了股票和行业的对应关系,有两列,第一列为股票名,第二列为每只股票对应的行业。第二张表保存了各个股票在各个交易日的收盘价和前收盘价,有四列,第一列是股票名,第二列为交易日,第三列和第四列分别为股票在这个交易日的前收盘价和收盘价。
这个问题在 Yao 的理论计算机课上整整讨论了 2 节课。它是一个算法设计问题,也极具趣味性。下面是它的一些介绍和解决方案 ([ 1 ])。
数学 » 圆周率
今天 gezhi 上有一篇关于 \( \pi\) 的八卦文章,里面讲到了 \( \pi\) 的计算问题。但我对其中的一些数据起了疑心,并不是说数据错了,而是作者所用的数据实在是太老了。
数学 » 数据分析, 统计
假设 某一天,某媒体发布一条消息,说清华大学研究生新生录取的面试过程中,每个系的女性报考者的通过率都要比男性报考者的通过率要低,然后攻击清华大学的新生录取歧视女性。你对这件事情有何看法?