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

作者: , 共 626 字 , 共阅读 0

理论计算机(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 的哲学:
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::sorted_vector_setfolly::sorted_vector_map,是std::mapstd::set在小数据集上的优化版。代码见: https://github.com/facebook/folly/blob/master/folly/sorted_vector_types.h
编程 » C++
假设在 C++里有一个数据结构:
这个问题在 Yao 的理论计算机课上整整讨论了 2 节课。它是一个算法设计问题,也极具趣味性。下面是它的一些介绍和解决方案([1])。
Excel 多表合并和查询是一个应用很广泛的问题。下面是一个简单的例子,我们需要从两张数据表里,得出每个行业的股票波动率平均值。第一个数据表保存了股票和行业的对应关系,有两列,第一列为股票名,第二列为每只股票对应的行业。第二张表保存了各个股票在各个交易日的收盘价和前收盘价,有四列,第一列是股票名,第二列为交易日,第三列和第四列分别为股票在这个交易日的前收盘价和收盘价。
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
2014-03-25 更新:我已经将该类修改成函数形式,并增加新功能,参见更新 Excel 的数据库查询函数库
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
数学 » 圆周率
今天 gezhi 上有一篇关于$ \pi$ 的八卦文章,里面讲到了$ \pi$ 的计算问题。但我对其中的一些数据起了疑心,并不是说数据错了,而是作者所用的数据实在是太老了。
数学 » 数据分析, 统计
假设某一天,某媒体发布一条消息,说清华大学研究生新生录取的面试过程中,每个系的女性报考者的通过率都要比男性报考者的通过率要低,然后攻击清华大学的新生录取歧视女性。你对这件事情有何看法?