CS6.006 Problem Set 4を解く
問題はこちら 意訳が間違っていたらご指摘ください。
大問1
(a) 文字列の文字コードの和(のmod)をハッシュ値として使った場合、
を達成できるか？
1. Yes, 文字列の長さに基づいて均等にハッシュ値がばらける
2. Yes, 文字列中の文字に基づいて均等にハッシュ値がばらける
3. No, 文字を並べ替えた場合は同じハッシュ値になってしまう
4. No, Simple uniform Hashingの前提にある、independence conditionが崩れてしまうから。
文字並び替えても同じハッシュ値になってしまうので、Simple Uniform Hashingになっていない。3と4が答え?
答え: 3
なんで4が答えに入っていないのか？文字コードによるハッシュ値は、すでにハッシュ表に入っている要素に関係なく文字によってのみ決まるので、independence conditionは保たれていると解釈できるからなのか？
(b)
1. Dynamic resizingはcorrectnessとperformanceを保証する。
2. Dynamic resizingはcorrectnessだけ保証する。
3. Collision resolutionはperformanceだけ保証する。
4. Dynamic resizingとCollision resolutionは二つ揃ってはじめてcorrectnessとperformanceを保証する。
correctnessとperformanceという、二つのプロパティについて。 - correctness: キーに対応する値を正しく返せるかどうか。 - performance: O(1)で値を返せるかどうか。
4が答え？
答え: 4
合ってた。
(c)
個の要素が入ったハッシュ表のサイズを
から
に拡張する時にかかる最良計算量は？
の表を一から作って、そこに
個の要素を移し替えるので、
(拡張時なので
としてよい)
7が答え？
答え: 7
合ってた。
(d) ハッシュ表の拡張はサイズを2倍にするように行うのが通常だが、定数倍増やすように行ってもよいかどうか？
n個の要素を一つづつ挿入し、ハッシュ表が埋まったら拡張するケースの、合計計算量を考える。
- 定数倍増やしていく場合( →
): [tex:O(n2)]
- 倍づつにしていく場合(
→
):
という計算結果になった。
実際にはメモリを2倍とった時に無駄になるメモリの数は大したことがないので、倍ずつとったほうがよいのではないか。
答え: amortized costでO(n)かかる(つまり合計だと[tex:O(n2)])。これは、
の操作を
また、2倍にしていく方法はビットシフトだけで数字が計算できるし、メモリサイズも2の倍数なので確保しやすいから、この方法が多く採られる。
大問2
(a)
1. dictionaryを作成し、大量の挿入があった後、検索の用途で主に使われる
2. dictionaryを作成し、対流の挿入があった後、検索のみに使われる
3. 挿入、削除、検索を同じぐらいの回数で行うために使われる
4. 挿入だけ、削除だけ、検索だけの操作の塊が代わる代わる行われるために使われるCreated once and then rarely changes.
とか
Many calls to __contains__() or has_key().
に当てはまるものは, 1だと思う。
答え: 1
合ってた。
(b) Membership Testingに特化したハッシュ表の実装をするなら、どれが適切か?
1. 開始時のサイズが大きく、足りなくなったら2倍に拡張する
2. 開始時のサイズが小さく、足りなくなったら2倍に拡張する
3. 開始時のサイズが大きく、足りなくなったら4倍に拡張する
4. 開始時のサイズが小さく、足りなくなったら4倍に拡張する
これは、
Any size of dict
と書いてあるし、サイズ関係ないのではと思ったが、クラスのメンバ関数などはいくつあるかわからないので、 なるべく大きくとったほうがいいと思う。 また、多くのメンバ関数がある可能性があるので、拡張の回数は少ないほうがいい。 よって3が答え?
答え: 3
大問3
DNAを表す文字列([tex:O(106)]の長さ)が二つ与えられた時、部分文字列の一致度合いを求める問題。 dnaseq.pyを編集する。
for文で実装すると、長いテキストをメモリに収める必要があり、非効率になってしまう。 これを回避するために、next()で1文字ずつ読み込む文字列シーケンスのクラスが与えられており、これを使って実装する。
詳細は略。
