圧縮– tag –
-
コンピュータ科学 深掘り
文字列探索とKMP — grepは1文字ずつ見ていない
indexOf があるのに、なぜ探索アルゴリズムを知るのか。素朴な探索・KMP・Boyer-Moore・Rabin-Karp を全部自分で書いて、比較回数と時間を実測します。最悪ケースを自分で作って素朴な探索を19,990,100回まで膨らませ、KMPで33分の1にします。Boyer-Moore がパターンを長くするほど速くなることを、比較回数が半分ずつ減るところまで数えます。ハフマン符号は英文4MBの出現頻度から符号表を作り、gzip の実測圧縮率と並べます。最後に接尾辞配列で「何回引いたら作る価値があるか」の交差点を出します。 -
Linux 深掘り
tar・rsyncと「重い」の切り分け — オプションは3つでいい
tar のオプションを毎回ググっていました。そして「サーバーが重い」と言われたとき、何から見るか決まっていませんでした。この2つはどちらも「型を持っていない」だけです。tar は集めるだけで圧縮は別、覚えるのは作る・展開する・見るの3つ。重いときは uptime から journalctl まで順番を固定する。実際に負荷をかけて数字を動かしながら確かめます。
1