挿入順を覚えている連想配列

これは何？

Ruby の Hash には shift があることの紹介。
と思って調べたら、 Python3 の dict にも順序があるのがあったので、それも紹介。

Ruby の Hash

Ruby の Hash は挿入順を覚えている。
挿入順を利用して古いものから順に取り出せる。
以下のような感じ。

ruby

 h={foo:111,bar:22,hoge:3}
h[:bar]=44
h[:baz]=55
s=""
while ! h.empty? do
  s += h.shift.inspect
end
p s #=> "[:foo, 111][:bar, 44][:hoge, 3][:baz, 55]"

先頭の値を見る first と、先頭の値を撤去する shift はあるけど、末尾を扱う last と pop は無い。

ruby

{a:1}.first #=> [:a, 1]
{a:1}.last #=> NoMethodError: undefined method `last'
{a:1}.shift #=> [:a, 1]
{a:1}.pop #=> NoMethodError: undefined method `pop'

値の追加がないのはわかるけど、末尾の値が扱えないのは不思議。

あと、Hash の first は引数ありなし両方あるけど、shift は引数なし。

ruby

{a:1,b:2}.first(2) #=> => [[:a, 1], [:b, 2]]
{a:1,b:2}.shift(2) #=> ArgumentError: wrong number of arguments (given 1, expected 0)
[1,2].shift(2) #=> [1, 2]

これも対応してくれればいいのにと思う。

Hash 内には挿入順が記憶されているのに、 == での比較では挿入順が度外視されるので

ruby

x={a:1,b:2}
y={b:2,a:1}
p(x==y) #=> true
p([x.first, y.first]) #=> [[:a, 1], [:b, 2]]

このように、等値であるオブジェクトに同じメソッドを送っても違う結果になったりする。
歴史的経緯からまあそうするしかないかとも思うけどわかりにくいよね。

Hash が挿入順を覚えていて、古い順から取り出せるので、ある種の探索アルゴリズムで役に立つ。
見つかったものを Hash に挿入しつつ、先頭から取り出して消費するという流れとか。

Python3 の dict

この記事を書くにあたって調べて初めて知ったんだけど、Python3 の dict にも挿入順が入っている。

Python3

d = { "foo":111, "bar":22, "hoge":3 }
d["bar"] = 44
d["baz"] = 55
s=""
while d:
  s += repr(d.popitem())

print(s) #=> ('baz', 55)('hoge', 3)('bar', 44)('foo', 111)

この popitem() は、 3.7 で「LIFO 順序が保証されるようになりました。」 とのこと。そりゃ知らなかったわけだ。

collections.OrderedDict の popItem には引数があって、末尾から取るか先頭から取るかを選べるんだけど、普通の dict の popItem には引数がない。必ず末尾から。なぜなのか。しかも ruby と逆。

辞書に入っている先頭要素は

Python3

d = { "foo":111, "bar":22, "hoge":3 }
iter(d.items()).__next__() #=> ('foo', 111)

と、items() と iter() を使えば撤去せずに取得できるけど、もっと簡単な方法がありそうな気がする。

一方、popitem() で容易に 撤去＋取得 できる末尾の要素だが、これを撤去せずに取得する方法は

Python3

d = { "foo":111, "bar":22, "hoge":3 }
iter(reversed(d.items())).__next__() #=> ('hoge', 3)

と、むしろ面倒になる。これももっと簡単な方法がありそうな気がする。

まとめ

	ruby	Python3
先頭を撤去せずに取得	h.first	iter(d.items()).__next__()
先頭を撤去して取得	h.shift	表外下記
末尾を撤去せずに取得	不可能だと思う	iter(reversed(d.items())).__next__()
末尾を撤去して取得	不可能だと思う	d.popitem()

Python3 の「先頭を撤去して取得」は、

1. firstkey = iter(d).__next__() で、先頭のキーを取得
2. firstval = d[firstkey] で、先頭の値を取得
3. del[firstkey] で、先頭の要素を撤去

という三手で実施可能。