本はばらばらに収納する方が効率的?【第99号】

ハッシュ法という驚異の片付け技法
金谷一朗(いち) 2022.10.14
誰でも

🎙️このレターには音声版があります (🍎Apple | 🎷Spotify | 🌳Amazon | 🌏Web)

【140字まとめ】皆さんは本をどのように収納していますか?探しやすいように五十音順?コンピューターは本のリストを格納するときに,五十音順ではなくあえてばらばらにします.その方が圧倒的に速く検索できるからなんです.今週はそんな「ハッシュ法」をご紹介します.

***

STEAM NEWS はメールで毎週届くニュースレターです.国内外のSTEAM分野(科学・技術・工学・アート・数学)に関するニュースを面白く解説するほか,今週の書籍,TEDトークもお届けします.芸術系や人文系の学生さんや教育関係者の方,古代エジプト好きな方にとくにおススメです.

***

いちです,おはようございます.

【第66号】「アメン神殿の塩が変える(かもしれない)エネルギーの未来」でご紹介した幻の植物「シルフィウム」が再発見されたかもしれないというニュースがありました.リンク先では,実際にシルフィウムを用いた古代ローマ料理を再現する試みも紹介されています.大変興味深いので,是非読んでみてくださいね.

僕のほうは無事アレクサンドリアとロンドンから戻って参りました.日本に戻ってきて驚いたのは,いきなり寒くなっていたこと.四季はいったいどこへ行ったのでしょうか.

Photo by Darwin Vegher on Unsplash
Photo by Darwin Vegher on Unsplash

さて,本号ではコンピューターがどうやって本を探しているのかについて,お話ししてみます.

部屋中に本を積み上げているのに,どこに何があるのかわかっている人っていますよね.コンピューターの内部も,少し似た仕組みを持っているのです.

【お知らせ】ツイッターで「STEAMコミュニティ」を運営しています.ときどき裏話をつぶやいています.ツイッターアカウントをお持ちの方は是非ご参加ください.

《目次》

  • 並んでいる本は探しやすい

  • ばら撒かれた本はもっと探しやすい

  • 今週の書籍

  • 今週のTEDトーク

  • Q&A

  • 一伍一什のはなし

並んでいる本は探しやすい

皆さんの手元にもし100冊の本があったとしたら,どのように本棚へ並べていきますか?

本の色や大きさで並べ替えたり,内容が関連する順番にしてみたり,タイトルや筆者の五十音順で並べたり,いろんな並べ方が考えられますね.

本の並びを考えるのは,目的の本を素早く見つけるためです.いや,中にはインテリアとしての本ということもあるでしょうが,今は実用性だけを考えましょう.

ここで問題を簡単にするため,本のタイトルから本の位置を見つけることだけを考えます.もし本がランダムに並んでいたとすると,目的の本は端から順番に探していくことになります.たとえば「ハリー・ポッターと賢者の石」を探すとすると,左端から「ハリー」「ハリー」と呪文を唱えながら本のタイトルを確認していく必要があります.

もし本が五十音順に並べられているとすると,ある程度「あたり」を付けることができますね.人間なら「ハリー(はりー)」だからこのあたりだろうと見当を付けて,その前後を探すことになります.これを計算機科学では「えいやっ」と言います.いや,これは僕の周囲の方言でしょう.

コンピューターなら,順番に並んでいる本のタイトルから棚の位置を見つけるには「二分探索(にぶんたんさく)」というアルゴリズムを使います.まず本棚の50番目の本のタイトルを調べます.本棚の中程なので,そうですね「な」から始まる本,たとえば「なーんだなんだ」があったとしましょう.コンピューターは次に「は」と「な」を比べて「は」は「な」よりも先にあることを知ります.本棚には100冊の本がありますから,次にコンピューターは50冊目と100冊目の中間,つまり75冊目を調べます.こうして,移動距離を半分ずつにして目的の本を探すのです.

そこそこ面倒くさいように感じられますが,これは非常に高速なアルゴリズムです.もし1,000冊の本が本棚に並んでいても,10回以内の探索でお目当ての本が見つかります.おもしろいことに,冊数を10,000冊にしても,14回以内の探索ですみます.

人間は本の並びをある程度は同時に見ることができますし,多少は「えいやっ」も効きますが,冊数が1,000冊にもなるともはや誤差の範囲です.

なので,本を並べ替えること,そして二分探索というアルゴリズムを使うことは,大変に理にかなったことなのです.

ただし,本棚に本を収納するには,実はもっと良い方法があるのです.その方法は意外にも,本を「ばら撒く」のです.

ばら撒かれた本はもっと探しやすい

「タイトルから本を探索する」ということを,うんと抽象化して考えると「タイトルから本の位置を求める」ことになります.つまり

(タイトル)→(本の位置)

という関係を求めていることになります.計算機科学者は,この関係に「h」という名前を付けて

という書き方をします.一方,同じ事を高校数学風に

(本の位置)=h(タイトル)

と書くこともあります.ここに書いた「h」のことを,数学者は「関数(かんすう)」と呼びます.関数は「函数(かんすう)」とも書きます.「函(はこ)の数」という意味になりますが,本当のところ函(はこ)とは関係がありません.

ここで大胆な想像をします.もし,もしも関係「h」があらかじめ決められていたなら,もう本を探索する必要がないのです.「ハリー・ポッターと賢者の石」が本棚のどこにあるかを知りたければ

h(ハリー・ポッターと賢者の石)

を計算すれば良いのです.その結果は,本棚の何番目という数値です.

そんな都合の良い関数「h」はあるのでしょうか.

もちろん,あるのです.

そのような関数を一般的に「ハッシュ関数」と呼びます.アメリカ料理「ハッシュブラウン (hash brown)」の「ハッシュ」です.ジャガイモを細切りにして混ぜて油で揚げたお料理ですね.

ハッシュブラウン (Image courtesy of McDonalds)
ハッシュブラウン (Image courtesy of McDonalds)

ハッシュ関数を使って「ハリー・ポッターと賢者の石」を本棚に収納することとしてみましょう.

「ハリー・ポッターと賢者の石」の1文字1文字を「文字コード」に置き換えます.「ハ」の文字コードは12495で,「リ」の文字コードは12522です.タイトルの文字をすべて並べると12495 12522 12540 12539 12509 12483 12479 12540 12392 36066 32773 12398 30707になります.これらの数字を全部足し合わせてしまうと「22万4,443」になります.

もし本棚の幅が無限にあれば「ハリー・ポッターと賢者の石」を22万4,443番目のスロットに収めれば良いのですが,今考えている本棚は100冊収納ですから,下2桁を使って,43番目のスロットに収納することとします.つまり「h(ハリー・ポッターと賢者の石)=43」なのです.この「h」がハッシュ関数(の一種)ですね.ハッシュ関数を使って本を収納することを「ハッシュ法」と呼びます.

ハッシュ法で本を収納するとき,本棚に隙間があるからといって詰めたりはしないでください.きっちり43番目の位置に「ハリー・ポッターと賢者の石」を置くのです.

計算機は人間よりもはるかに計算が得意ですから「ハリー・ポッターと賢者の石」と聞いた途端に「22万4,443」を計算できます.そして下2桁を使って,本棚の43番目のスロットを見に行きます.こうすれば,ただの一度も探し回ることなく,いきなり目的の本にたどり着けるのです.

こんな方法を使っていたら,いつかスロットの取り合いが起こるのではないかと思われるでしょう.しかし,我々は経験上,スロットの取り合いが起こりにくいことを知っています.たとえば「ハリー・ポッターと秘密の部屋」は6番目のスロット,「ハリー・ポッターとアズカバンの囚人」は95番目のスロットに入ります.「なーんだなんだ」は66番目のスロットです.

ハリー・ポッターを並べずにばら撒きます
ハリー・ポッターを並べずにばら撒きます

ハッシュ法を使って本を本棚に入れていくには,少し広めの本棚が必要になります.その代わり,本が何万冊になろうと,何億冊になろうと,一瞬で探し当てることができるのです.

それでも,万が一棚の取り合いが起こったらどうするんだと気になる方は,計算機科学の才能があります.ぜひ「衝突」を調べてみてください.

ハッシュ法はこのように,タイトルの文字を「切り刻んで」「混ぜこぜにして」数値化するので,ハッシュブラウンの「ハッシュ」なのです.

コンピューターにとっては,順番に並んだ本よりも,ハッシュ法を使ってばら撒かれた本のほうが見つけやすいというお話でした.

「部屋をわざと散らかしている」方はきっと,頭の中にハッシュ関数が入っているんですよ.

今週の書籍

累計1100万部超えの世界的ベストセラー.家の中を劇的に片づけると,人生も劇的に変わると話題のメソッド.一度片づけたら絶対に元に戻らない,著者の原点となる本の最新版.
Amazon

英語で「片付ける」を意味する「コンドー (kondo)」の語源となった,近藤麻理恵(こんまり)さんです.

僕はこんまりさんの本をまだ読んでいなかったのですが,このニュースレターを書くにあたってついに読み始めてみました.

散らかすことに関してはかなりの才能の持ち主を自認する僕ですが,ついに僕も片付けに成功するのでしょうか.まずは現状を記録することから始めたいと思います.(だから片付かない…)

今週のTEDトーク

コメディアンのアパルナ・ナンチェーラはゴミ捨てが大好きです.「CO2を出しまくるという現代の消費行動様式のもと,我々が際限なく,しばしば意味もなく買う物」つまり「ゴミ」についての愉快で鋭く考察したトークを通して,かつてないほど大量のゴミにあえぐ世界で,ゴミを減らす方法について話します.
TED

アメリカでは廃棄されたプラスチックの1割しかリサイクルされていないそうです.だから,リサイクルへ出す前にもう一度使えないか考えてみましょうというメッセージでした.

アメリカと日本では事情が違うでしょうが,それでもできるだけリユースを心がけたいものですね.

Q&A

匿名質問サイト「マシュマロ」および質問サイト「Quora」で質問を受け付けています.普段はツイッターでお返事を書いていますが「ニュースレター読んでます」と入れていただければ,こちらのニュースレターでより長めの回答を書かせていただきます.

今週はこちらのご質問から.

エジプトでは何を食べましたか?

最終日に数時間だけ空き時間ができましたので,古い仲間とエジプト料理を食べに行きました.

タヒーナ(胡麻ペースト),アエーシ(パン),モロヘイヤスープ,茄子のトマト煮込みなどなど…

相変わらず美味しかったです.

このレターの最後に匿名質問サイトへのリンクを貼っています.質問をお待ちしております.

一伍一什のはなし

STEAM NEWSも気がつけば【第99号】までやって来ました.ひとえにSTEAMボート乗客(読者)の皆様,乗組員(有料購読者)の皆様のおかげです.

とりわけ乗組員の皆様が支えて下さっているおかげで,資料収集や執筆にかかる費用の一部をまかなえています.本当にありがとうございます.

次号は【第100号】となるのですが,まだ心の準備ができてなくて…

皆様に感謝の気持ちをお伝えしたいのですが,どうしたら良いでしょう.音声ライブはいかがでしょうか?

このメールへの返信でも,匿名の質問箱でも,Twitterコミュニティでも結構ですので,ご意見をお寄せ頂けると嬉しいです.

🍓

今週も最後までお読みいただきありがとうございます.メールでお読み頂いた皆様は,よろしければボタンを押して行ってくださいませ.(ボタンは匿名化されています.集計したデータはこのニュースレターの内容改善以外には用いません.)

ここに配置されたボタンは、ニュースレター上でのみ押すことができます。

このニュースレターは下のボタンからSNSで共有できます.もし気に入っていただけたら,共有ボタンも押していってくださいませ.

では,また来週,お目にかかりましょう.

***

ニュースレター「STEAM NEWS」

金谷一朗(いち)

TEDxSaikaiファウンダー・パイナップルコンピューター代表・長崎大学情報データ科学部教授

バックナンバーはこちらから👉 https://steam.theletter.jp

匿名質問はこちらから👉 https://marshmallow-qa.com/kanaya

(ご意見,ご感想はこのメールに直接ご返信頂けます)

「STEAM NEWS」をメールで読みませんか?

無料で「STEAM NEWS」をメールでお届けします。
コンテンツを見逃さず、購読者限定記事も受け取れます。
ワールドカップの「1ミリメートルの奇跡」を支えた工学〈後編〉【第108...
読者限定
★ こんにゃくとテクノロジーのノート【第106号別冊】
有料限定
ワールドカップの「1ミリメートルの奇跡」を支えた工学〈前編〉【第107...
読者限定
こんにゃくとテクノロジー【第106号】
誰でも
★ ラプラスの悪魔のノート【第105号別冊】
有料限定
🌟 あなたに影の部分があるなら…
誰でも
ラプラスの悪魔【第105号】
誰でも
★ クレオパトラのノート【第104号別冊】
有料限定