押し出しファイリングの思想：LRUとMTF

◇「押し出しファイリング」とは
　「押し出しファイリング」は、拙著『「超」整理法』（中公新書、1993年）で提案した書類の整理法です。
　「資料を封筒に入れ、新しく作った封筒は左端に入れる。使った封筒は、もとの位置に戻すのではなく、左端に入れる」というものです。
　使わなかった封筒は、時間が経つにつれて次第に右に押し出されていきます。収納場所が一杯になったら、右端から捨てます（ただし、長時間使わなくても残しておきたい資料もあるので、チェックしてから捨てます）。

　「使った封筒をもとの位置に戻すのではなく、左端に入れる」というのは、最初は面倒だからそうしたのです（「もとの位置」が分からなくなる場合も多いため）。ところが、やっているうちに、これに重要な意味があることがすぐに分かりました。これは、「使っていないものを自動的に見いだす仕組み」なのです。

◇　超整理法は数学的に最適
　同じ頃、コンピュータサイエンティストも、コンピュータのキャッシュメモリ（高速で出し入れするメモリ）の設計に関して、同じ問題を考えていました。到達した結論も同じです。
　これについて、ブライアン・クリスチャン 、 トム・グリフィス『アルゴリズム思考術: 問題解決の最強ツール』（早川書房、2017年）が説明をしています。
　数年前、執筆中の著者から、メールと国際電話でインタビューを受けました。原著 Algorithms to Live By, The Computer Science and Human Decisions は、2016年に Henry Holt and Co.社から刊行されています。
　著者たちは、この本のなかで、「「超」整理法は、数学的に見て最適な方法である」と評価してくれました。これは大変嬉しいことです。
　もう少し詳しく言うと、「超」整理法は、コンピュータサイエンスにおけるLRUやMTFと同じものだ」というのです。では、LRU、MTFとは何でしょうか？

◇　LRU：何を捨てたらよいか？
　キャッシュメモリの設計で求められのは、キャッシュで置換するデータを決めるための方法です。「キャッシュ」とは、超高速で読み書きできるメモリ。容量はあまり大きくないので、優先度が高いデータを入れます。そのため、一杯になったらデータを捨てる必要があります。では、どのデータを捨てるべきでしょうか？
　LRU（ Least Recently Used：最長時間未使用の原理）がその答えです。直訳すれば「最近で最も使われなかったもの」ということですが、「最後に使われてから最も長い時間が経ったもの」という方が分かりやすいでしょう。それを捨てるのです。
　なお、「捨てる」といっても、廃棄するとは限りません。大容量で低速な記憶装置に保存するのです。
　超整理法は、まさにその方法をとっています。ファイルを押し出していくことによって、自動的にLRUを行なう方法になっています。
　この場合も、押し出されたファイルは必ずしも捨てるわけではありません。「長期間使わなかったが、記念のために残して置きたいもの」はあります。私は、それを「神様ファイル」と名付けました。これらは、倉庫に収納します。
　LRUは、コンピュータ以外でも広く使われています。図書館で用いられている「12年間一度も使われなかった本は倉庫に送る」というルールは、その例です。

◇　MTF：使った資料は元に戻さず、先頭に置く
　上で述べたのは、キャッシュからの捨て方です。もう一つは、「キャッシュに新しいデータを加えるとき、それをどこに入れるか？そして、使用したデータは、どこに戻せばよいか？」という問題です。
　正確に言うと、「同一の探索値で次回探索した時に最短時間で探索できるようにするには、キャッシュのデータをどのように配置換えすればよいか？」という問題です。これは、「自己組織化リスト」（Self-organizing list)の問題と呼ばれます。なお、この場合、探索は端から順に一つづつ調べることとします。
　この問題について、1970年代から80年代に、コンピュータ科学者が一連の研究を行ないました。
　もし要求されるデータの確率が知られているなら、確率の高さの順に、先頭から並べていけばよいのは明らかです。しかし、実際には、要求確率はわかりません。では、どうしたらよいでしょうか？
　『アルゴリズム思考術』によると、85年にダニエル・スリ―ターとロバート・タージャンが発表した論文が、この問題を解決しました。それによれば、使用したデータをリストの先頭に戻せばよいのです。これは、Move-to-Front (MTF)法 と呼ばれます。そうすれば、探索時間は、要求確率が分かっている場合の2倍以上にはならないことを、彼らは証明しました。

◇　「超」整理法はMTFそのもの
　前述のように、超整理法においても、使ったファイルは、元の場所に戻すのでなく、1番左に戻します。これはMTFそのものです。
　押し出しファイリングを使っているうちに、「探索の時間は、一定の範囲に収まる。しかも、当初予想していたより短い」ということが分かりました。「探索時間は、普通は数秒。暫く使わなかったファイルでも2，3分」と『「超」整理法』に書きました。
　これは経験からえた知識です。私は『「超」整理法』執筆時にスリ―ター＝タージャン論文は知らず、『アルゴリズム思考術』の著者から電話でインタビューを受けたときに、初めて教えられました。

　『アルゴリズム思考術』はつぎのように言いいます。
　”机の上に書類の山を積みあげ、探すときは上から順に探す。そして新しい書類と使った書類は一番上に戻す。これは、一見したところカオスだが、実は、この上もなく効率的な構造だ。整理は不要なのだ。なぜなら、「整理はすでにできていた」から。”

　このことも私は意識していました。そして、「世の中に『隠れ超整理派』は沢山いる。ただし、彼らは『このままではいけない』と考えている」と書きました。そして、「超整理法とは、縦のものを横にするだけのことだ」とインタビューなどで話していました。ただし、「縦を横にするだけで、絶大な効果が得られる」というのが重要な点なのです。

◇　世の中には、ノウハウにならないノウハウが多すぎる
　LRUは、「先入れ先出し法」（FIFO：First-in-first-out）と一見して似ていますが、異なるものです。しかし、両者の違いは、意識されないことが多いのです。
　実際、マーサ・スチュアート(アメリカの有名な家事・生活評論家)は矛盾したことを言っていると、『アルゴリズム思考術』は指摘しています。
　彼女は、何をとっておくべきかについて、「いつからある？」「最後に使ったのはいつ？」と問えと言っているのです。
　前者はFIFOであり、後者はLRUです。両者は相いれない提案であり、異なる方針を示しています。そして、後者が明らかに優れているのです。
　私は、『「超」整理法』を書いたとき、従来の整理法が、思いつきを書き並べたものに過ぎないことに、憤りを感じていました。本当は不合理なことや、実行不可能なことが、平気で提案されているのです。
　例えば、「要らないものを捨てましょう」とよく言われます。しかし、これは、トートロジー（同義語反復）に過ぎません。「何が要らないか？」が分からないから苦労しているのです。
　また、「整理は分類」と昔から言われてきました。しかし、資料の多くは、一義的な分類はできません。また、内容やファイル名は、適切な検索キーになりません。

　『アルゴリズム思考術』では、「図書館では、返却された本を完全にソートして書架に戻すという作業を行なっているが、これは、実は秩序を乱しているのだ」と指摘しています。返却された本がまず置かれる分別用の棚には、最後に利用されてから最も時間が短い本が集まっています。これらこそ最も重要な本なのだから、「そこから本が運び去られるというのは、犯罪行為に近い」としています。そのとおりです。
　『「超」整理法』は、内容別分類法の批判から出発しています。そして「LRUとMTFを基本的な原則とせよ」と主張したのです。

　　　　::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

AIの眼を駆使する「超」仕事法(目次）

ホーム

メタ・ナビゲーション（野口悠紀雄のnoteの総目次）

AI関連note記事　目次

Google Pixelを使う