Beautiful codeは予想してたよりも二倍くらい分厚かった。あとエッセイ集なので、好きなところから読み始める事ができるし、ちょっとした時間があるときに暇つぶし代わりに読めたりしてよさげ。
とりあえず、最初の方と最後のほうの対談を読んで、29章のまつもとゆきひろさんの「エッセイのごときプログラム」を読んで、そのうちRubyもなんて思った。
ビューティフルコードさて、18章はpythonにおける辞書実装の話。
[アルゴリズム百選 - ハッシュを再発明する](アルゴリズム百選 - ハッシュを再発明する)はリストを使う方法で実装していて、これはchainingと呼ぶらしい。
pythonはopen addressingという往々で空きスロットを探しているらしい。線形探査でなくとびとびに探していくことでブロックの発生を抑える効能があるらしい。
イメージできないのでスロットを探していく順番を見てみた。32個のスロットでハッシュ値が8の場合はまずスロット8を探すけど埋まっている場合に次はどこを探すのか。
use strict;
use warnings;
use Perl6::Say;
my $ma_mask = 31;
my $hash = 8;
my $pertub = $hash;
my $slot = $hash;
for my $i (0..31) {
$slot = (5 * $slot) + 1 + $pertub;
$pertub >>= 5;
$slot %= 32;
say "[ $i ] slot:$slot, pertub:$pertub";
}
こんな感じ？
[ 0 ] slot:17, pertub:0
[ 1 ] slot:22, pertub:0
[ 2 ] slot:15, pertub:0
[ 3 ] slot:12, pertub:0
[ 4 ] slot:29, pertub:0
[ 5 ] slot:18, pertub:0
[ 6 ] slot:27, pertub:0
[ 7 ] slot:8, pertub:0
[ 8 ] slot:9, pertub:0
[ 9 ] slot:14, pertub:0
[ 10 ] slot:7, pertub:0
[ 11 ] slot:4, pertub:0
[ 12 ] slot:21, pertub:0
[ 13 ] slot:10, pertub:0
[ 14 ] slot:19, pertub:0
[ 15 ] slot:0, pertub:0
[ 16 ] slot:1, pertub:0
[ 17 ] slot:6, pertub:0
[ 18 ] slot:31, pertub:0
[ 19 ] slot:28, pertub:0
[ 20 ] slot:13, pertub:0
[ 21 ] slot:2, pertub:0
[ 22 ] slot:11, pertub:0
[ 23 ] slot:24, pertub:0
[ 24 ] slot:25, pertub:0
[ 25 ] slot:30, pertub:0
[ 26 ] slot:23, pertub:0
[ 27 ] slot:20, pertub:0
[ 28 ] slot:5, pertub:0
[ 29 ] slot:26, pertub:0
[ 30 ] slot:3, pertub:0
[ 31 ] slot:16, pertub:0