跳到主要内容

東京大学 情報理工学系研究科 創造情報学専攻 2008年8月実施 筆記試験 第1問

标签：

Author​

itsuitsuki

Description​

Given nn records r1,r2,…,rnr_1, r_2, \dots, r_n, each has a key k1,k2,…,knk_1, k_2, \dots, k_n, respectively. Given a key, consider searching for the corresponding record. For a given query key vv, if there is a key kjk_j where v=kjv = k_j (1≤j≤n1 \le j \le n) then the search is successful and the record rjr_j is returned, otherwise the search fails and the failure is returned.

Let pjp_j be the probability where the query key vv is kjk_j, and pmissp_{\text{miss}} be the probability of the search failure. The computation time is almost proportional to the number of comparisons with vv. Let us calculate the average number of comparisons C‾\overline{C} and the maximum number of comparisons CmaxC_{\text{max}}.

(1) Consider a sequential search that compares vv with keys from k1k_1 to knk_n. (a) Obtain C‾\overline{C} and CmaxC_{\text{max}} when p1=p2=⋯=pn=12n,pmiss=12p_1 = p_2 = \dots = p_n = \frac{1}{2n}, p_{\text{miss}} = \frac{1}{2}. (b) Prove that C‾≤2\overline{C} \le 2 when p1=12,p2=14,…,pn=12n,pmiss=12np_1 = \frac{1}{2}, p_2 = \frac{1}{4}, \dots, p_n = \frac{1}{2^n}, p_{\text{miss}} = \frac{1}{2^n}.

(2) Consider a binary search after sorting the keys. Let n=2m−1n = 2^m - 1 (mm is a natural number), and moreover, one comparison will determine whether v<kj,v=kjv < k_j, v = k_j or v>kjv > k_j. (a) Obtain C‾\overline{C} and CmaxC_{\text{max}} for each case of m=1,2,3,4m=1, 2, 3, 4, when p1=p2=⋯=pn=pmissp_1 = p_2 = \dots = p_n = p_{\text{miss}}. (b) Obtain C‾\overline{C} and CmaxC_{\text{max}} as a function of mm when p1=p2=⋯=pn=pmissp_1 = p_2 = \dots = p_n = p_{\text{miss}}.

(3) Consider a search using a hash table. The records r1,…,r8r_1, \dots, r_8 are inserted into the hash table of size S=17S = 17 using the hash function h(x)=x mod Sh(x) = x \bmod S. Let the key values each be k1=10,k2=1,k3=17,k4=97,k5=21,k6=4,k7=39,k8=73k_1 = 10, k_2 = 1, k_3 = 17, k_4 = 97, k_5 = 21, k_6 = 4, k_7 = 39, k_8 = 73. (a) Draw the structure of the hash table by choosing an appropriate method for avoiding collision. (b) Obtain C‾\overline{C} and CmaxC_{\text{max}} when p1=p2=⋯=p8,pmiss=0p_1 = p_2 = \dots = p_8, p_{\text{miss}} = 0.

(4) Describe in general the advantages and disadvantages of sequential search, binary search and search using a hash table.

题目描述​

给定 nn 条记录 r1,r2,…,rnr_1,r_2,\ldots,r_n，对应键为 k1,k2,…,knk_1,k_2,\ldots,k_n。对查询键 vv，若存在 v=kjv=k_j（1≤j≤n1\le j\le n），则查找成功并返回 rjr_j；否则返回失败。记 v=kjv=k_j 的概率为 pjp_j，失败概率为 pmissp_{\mathrm{miss}}。计算时间近似与同 vv 比较的次数成正比，以下均要求平均比较次数 C‾\overline C 和最大比较次数 Cmax⁡C_{\max}。

  1. 按 k1k_1 到 knk_n 的顺序进行顺序查找。

    1. 当 p1=⋯=pn=12np_1=\cdots=p_n=\frac1{2n}、pmiss=12p_{\mathrm{miss}}=\frac12 时，求 C‾\overline C 与 Cmax⁡C_{\max}。
    2. 当 p1=12,p2=14,…,pn=12np_1=\frac12,p_2=\frac14,\ldots,p_n=\frac1{2^n}、pmiss=12np_{\mathrm{miss}}=\frac1{2^n} 时，证明 C‾≤2\overline C\le2。

  2. 将键排序后进行二分查找。令 n=2m−1n=2^m-1，其中 mm 为自然数；一次比较即可判断 v<kjv<k_j、v=kjv=k_j 或 v>kjv>k_j。

    1. 在 p1=⋯=pn=pmissp_1=\cdots=p_n=p_{\mathrm{miss}} 时，分别对 m=1,2,3,4m=1,2,3,4 求 C‾\overline C 与 Cmax⁡C_{\max}。
    2. 在相同等概率条件下，用 mm 表示 C‾\overline C 与 Cmax⁡C_{\max}。

  3. 使用大小 S=17S=17 的哈希表和哈希函数 h(x)=x mod Sh(x)=x\bmod S，依次插入键值

    k1=10, k2=1, k3=17, k4=97, k5=21, k6=4, k7=39, k8=73.k_1=10,\ k_2=1,\ k_3=17,\ k_4=97,\ k_5=21,\ k_6=4,\ k_7=39,\ k_8=73.
    1. 自选一种合适的冲突处理方法，画出哈希表结构。
    2. 当 p1=⋯=p8p_1=\cdots=p_8、pmiss=0p_{\mathrm{miss}}=0 时，求 C‾\overline C 与 Cmax⁡C_{\max}。

  4. 概括比较顺序查找、二分查找和哈希表查找各自的优缺点。

Kai​

以下ではキーは相異なり、キーとの三方向比較1回を1比較と数える。配列境界の検査やハッシュ値の計算は比較回数に含めない。

(1)​

成功時に kjk_j まで調べれば比較回数は jj、失敗時は nn である。

(a)

C‾=∑j=1nj2n+n2=3n+14,Cmax⁡=n.\overline C=\sum_{j=1}^n\frac{j}{2n}+\frac n2 =\boxed{\frac{3n+1}{4}},\qquad \boxed{C_{\max}=n}.

(b) 有限等比級数の微分から

∑j=1nj2j=2−n+22n\sum_{j=1}^n\frac{j}{2^j}=2-\frac{n+2}{2^n}

なので、

C‾=∑j=1nj2j+n2n=2−21−n≤2.\boxed{\overline C=\sum_{j=1}^n\frac{j}{2^j}+\frac n{2^n} =2-2^{1-n}\le2}.

最悪回数は依然 nn であり、平均の小ささは高頻度キーを先に置いた分布による。

(2)​

n=2m−1n=2^m-1 の二分探索木は高さ mm の完全な木になる。深さ d=1,…,md=1,\ldots,m には 2d−12^{d-1} 個のキーがあり、それぞれ成功するまで dd 比較を要する。失敗時も mm 個のキーを調べる。失敗という事象全体の確率が各キー1個の確率と等しいので、各 pj=pmiss=1/(n+1)=2−mp_j=p_{\mathrm{miss}}=1/(n+1)=2^{-m} である。

(a)

mmnnC‾\overline CCmax⁡C_{\max}
11111
237/47/42
375/25/23
41553/1653/164

(b) ∑d=1md2d−1=(m−1)2m+1\sum_{d=1}^m d2^{d-1}=(m-1)2^m+1 を用いて、

C‾=∑d=1md2d−1+m2m=m−1+m+12m,Cmax⁡=m.\boxed{\overline C=\frac{\sum_{d=1}^m d2^{d-1}+m}{2^m} =m-1+\frac{m+1}{2^m}},\qquad \boxed{C_{\max}=m}.

(3)​

(a) 連鎖法を用い、各バケットの末尾へ挿入する。各要素にはキーとレコードへの参照を保存する。

bucket  0: (17, r3) -> null
bucket  1: ( 1, r2) -> null
bucket  2: null
bucket  3: null
bucket  4: (21, r5) -> (4, r6) -> null
bucket  5: (39, r7) -> (73, r8) -> null
bucket  6: null
bucket  7: null
bucket  8: null
bucket  9: null
bucket 10: (10, r1) -> null
bucket 11: null
bucket 12: (97, r4) -> null
bucket 13: null
bucket 14: null
bucket 15: null
bucket 16: null

例えば 21 mod 17=4 mod 17=421\bmod17=4\bmod17=4、39 mod 17=73 mod 17=539\bmod17=73\bmod17=5 なので衝突する。

(b) 各キーの確率は 1/81/8。比較1回のキーが6個、2回のキーが2個だから、

C‾=6+2⋅28=54,Cmax⁡=2.\boxed{\overline C=\frac{6+2\cdot2}{8}=\frac54},\qquad \boxed{C_{\max}=2}.

(4)​

方法長所短所・条件
順序探索未整列のデータや連結リストに使え、追加が容易。高頻度順なら平均を改善できる一般に平均・最悪とも O(n)O(n)
二分探索整列済み配列なら最悪 O(log⁡n)O(\log n)、大小順や範囲検索も扱える整列とランダムアクセスが必要。配列の途中への挿入・削除は一般に O(n)O(n)
ハッシュ探索良好な分散と有界の負荷率なら平均 O(1)O(1)。等値検索や動的な集合に適する衝突処理と容量管理が必要。偏ったハッシュでは最悪 O(n)O(n)、大小順・範囲検索には向かない

ハッシュの平均定数時間は分散と負荷率についての仮定に依存し、キーのハッシュ計算自体が高価な場合はそのコストも加わる。

本页目录