WEB+DB Press Vol.91 データ構造の基礎知識 が良い

簡単なアルゴリズムの話かと思い、さらっと流そうかと思ったら、配列、連結リスト、ハッシュテーブルをRubyで実装し、B木/B+木にも言及した良記事でしたので、手を動かしなら、B+木の絵も手元で沢山書いて理解しながら熟読してしまいました。
計算量の違いの説明もあり図も充実しており、とてもよかったです。若い頃の自分に読ませてあげたい良特集です。

WEB+DB PRESS Vol.91

配列

配列と連結リストのアーキテクチャ、計算量の違いを unshift, push, each を実装することで理解できます。

ハッシュテーブル

ハッシュテーブルの仕組み（binやメモリ空間の説明）、rehash（要素数がbinを超えた時の再計算の仕組み）の説明があり、ハッシュテーブル、順序付きハッシュテーブルの実装することで計算量やメモリ使用量について理解できます。

余談

関連してRubyの実装上必要な Object#hash, Object#eql? がどのように定義されているかをコードリーディングで調べた記事です（本書で紹介されていました）。
こちらも面白かったです。
CRuby の hash.c を一部読んだ - 猫型の蓄音機は 1 分間に 45 回にゃあと鳴く

2分木、B木、B+木

2分探索木の説明、実装。そのあと、B木、B+木の説明があります。 「B+木」についてはちゃんと理解していなかったので勉強になりました。

B+木の特徴

• リーフノードを全て読むと、ツリー内の全てのデータを読むことができる
• リーフノードどうしが連結リストのように連結されている

これ何が嬉しいのかというと、Range指定の抽出が楽になります。
例えば、5から20のデータを抽出する場合、リーフノードの5を探せば、あとは連結されたデータを20まで読めば良いと。（言葉にするとわかりにくいので是非図付きの本書を読んでください。）

他には
MySQLのInnoDBがB+木を採用していることや、プライマリキー（クラスタ化インデックス）と通常のインデックスの違い、通常のインデックスの問題点、その回避策となるカバリングインデックスの仕組みについて説明があり、とてもためになりました。

ご参考

若干visualizationの仕方が異なりますが、B+Tree がどのようにバランスするのかを分かりやすく見れます。
B+ Tree Visualization

STRING PERMUTATIONS(CODEEVAL)

文字列の組み合わせをアルファベト順で並び替える問題。
今回も組み込みメソッドで対応。 instance method Array#permutation (Ruby 2.4.0)
Codeevalとかやると、かゆいところに手が届くrubyは非常に良いと実感できます。
（本来的にはこれを素で実装しろということなんでしょうが、まぁ便利だしいいよね。）

CHALLENGE DESCRIPTION:

Write a program which prints all the permutations of a string in alphabetical order. We consider that digits < upper case letters < lower case letters. The sorting should be performed in ascending order.

INPUT SAMPLE:

Your program should accept a file as its first argument. The file contains input strings, one per line.

hat
abc
Zu6

OUTPUT SAMPLE:

aht,ath,hat,hta,tah,tha
abc,acb,bac,bca,cab,cba
6Zu,6uZ,Z6u,Zu6,u6Z,uZ6

CONSTRAINTS:

1. The text is case-sensitive: ‘a’ and ‘A’ are different characters.
2. The input consists of 40 text lines.
3. The maximum size of the text is 10 KB.

My Code

#!/usr/bin/env ruby -w

def all_permutations(str)
  str.split("").permutation(str.size).map(&:join).sort.join(",")
end

ARGF.each_line do |line|
  puts all_permutations(line.chomp!)
end

簡易包丁研ぎが良い

貝印 関孫六 ダイヤモンド&セラミックシャープナー AP-0308

実は無印で 包丁を新しく買った のですが
古い包丁を捨てる前に一度研いでみようと思い、こちらのシャープナーを買ってみました。
（たまに料理した時に、手を怪我しなくて良いという理由から研いでませんでした。。）
　
研ぎ石でシャコシャコやるのも乙だと思ったのですが、Amazonでの評判が良いのと料金的にも安かったのでこちらを買って見ました。
使ってみた感想としては、簡単に研げる上に、すごく切れるようになったのでとても満足。