キャッシュを使いサンタさんの仕事量を減らせる（二重forの計算量を減らせる）か試してみる

◼️TechCommit Advent Calendar 2020
https://qiita.com/advent-calendar/2020/tech-commit
の17日を担当させていただきますnaokiと申します！

最近Techcommitの推奨教材となったRecursionを学習しています。
https://prtimes.jp/main/html/rd/p/000000006.000062466.html

Recurstonとは？

CS、コンピューターサイエンスを学べるWebサービスです。
基本的な各種言語の文法を最初に学び、色々な問題をアウトプット中心にときながらデータの扱い、計算アルゴリズムなどを学んでいくサービスです。
どんどん問題を解くことで、データの扱いの考え方などを身につける訓練になる感じがあります！
サービスの概要は詳しくは前述の記事やこちらの記事もご参考を。
https://note.com/shinya_recursion/n/n180db20428a0

ハッシュマップキャッシング

この中で「キャッシュ」を使うことで計算量を減らす、という方法があり、印象に強く残りました。
キャッシュとは・・・
CPUのバスやネットワークなど様々な情報伝達経路において、ある領域から他の領域へ情報を転送する際、その転送遅延を極力隠蔽し転送効率を向上するために考案された記憶階層の実現手段である
from wiki https://ja.wikipedia.org/wiki/キャッシュ_(コンピュータシステム)

要は、一度記憶を刻み付けることで次回以降にその情報を使うときに、記憶を参照するのでデータへのアクセスのスピードをアップする方法、という感じです。
わかりやすい例では「ブラウザにキャッシュをすることで過去に見たページをブラウザで再度見るときに表示までの速度を速くする」するといった部分でしょうか。

javascriptの場合は、連想配列（jsではオブジェクト）を使い、
配列とは別にキャッシュデータを作ることで、スムーズに計算を行うことができるケースがあります。
アドベントカレンダーということで、キャッシュを使いサンタさんの仕事の効率を上げることができるかを数字も含め動作を見てみようと思います。

サンタの仕事

サンタさんがプレゼントを複数の人の家に届けるとします。
家にはナンバーが振られています。情報化社会。だがサンタさんといえど万能ではないので一度に運べるプレゼントの数には限りがあります。

妖精から、プレゼントを配りに行く子供の家の名前が配列で記述されているリストA（homeList）、
また届ける相手のプレゼントが袋に入っているリストB（presentList）を受け取ります。
リストをもとにサンタさんは町に繰り出し、リストA、B両方に含まれる数字の家にプレゼントを配っては、おもちゃ工場に戻りプレゼントをまた受け取り、、、そんな単純作業を一晩中このコロナの時代に繰り返します。心配ですね。
（※でも、一応サンタさんは免疫あるみたいです。　https://www3.nhk.or.jp/news/html/20201215/k10012765591000.html）

サンタの活動

さて、サンタさんがリストA、Bを受け取ってまちにおもちゃ配りに出かけた際に、配ることができたプレゼントを配列で返す関数を作る。とします。
どうやってそんな関数を作る？と考えた時、最初は二重のfor文が浮かびます。

二重forとは？

そのまんま、forの中にforがある記述です。

    console.log("開始");

    for(let i = 0; i < 4; i++){
        console.log(i + "番目のiのループ");
        for(let j = 0; j < 4; j++){
            console.log(j);
        }
    }

forの計算が二つあります。
一つ目のfor、つまりiの数字を0.1.2.3と表示する処理があり、
さらにjの表示を0.1.2.3とする処理が書かれています。
この記述の場合、結果はこのようになります。

4つのjの数字を吐き出す処理を、4つのiが行っているので、jの処理を16回行なっているようなイメージですね。
※この辺りのことを計算量の呼び方として二乗時間というようですが、自身もまだあんまり把握できてないし、細かい話は置いておきます。

ではさっきのサンタさんの仕事を考えてみましょう。

◼️家のリストA
◼️プレゼントのリストB
があるとします。

リストAを1-10000
リストBが1-100
とします。

この中から、両方のリストで「重複した数字」を「配れたリスト」に詰め込む処理を作ります。

コード1：二重forでやってみよう

let homeList = [...Array(10000).keys()];//1-10000の配列を作成
let presentList = [...Array(100).keys()];//同様に1-100の配列を作成
let doneList = [];//配れたリスト。

const startTime = performance.now(); // 開始時間

for(let i = 0; i < homeList.length; i++){
    for(j = 0; j < presentList.length; j++){
        if(homeList[i] == presentList[j]){
            doneList.push(homeList[i]);
        }
    }
}


const endTime = performance.now(); // 終了時間
console.log(endTime - startTime); // 何ミリ秒かかったかを表示する
console.log("配れたリスト" + doneList);

開始時間、終了時間の[performance.now()]とは、そのドキュメントの開始からの経過時間をはかります。
開始時間と終了時間を比較することで、どれだけの時間がかかったかを大体で出すことが可能です。
このコードだとこんな結果となりました。

配れたリストにはちゃんと0-99（すみません、0から始めちゃいましたが、、、100個配ってます！）が入ってますね。そして18ミリ秒かかっています。
何度か実行したところ、おおよそ15~20msって感じでした。

では次に、この処理をキャッシュを使ってやってみます。

コード2：キャッシュでやってみよう

let homeList = [...Array(10000).keys()];//1-10000の配列を作成
let presentList = [...Array(100).keys()];//同様に1-100の配列を作成
let doneList = [];//プレゼント配れたリスト。

const startTime = performance.now(); // 開始時間

//まずはhomeListのキャッシュを作る。オブジェクト作成
let cache = {};

for (let i = 0; i < homeList.length; i++ ){
//もし、キャッシュの[i]番目がundefinedなら、1を入れる。
    if(cache[homeList[i]] == undefined){ 
        cache[homeList[i]] = 1;
    }else{
//もし、すでに数字が入ってるなら、さらに値を1ふやす
        cache[homeList[i]]++;　
    }
}

homeListをもとに、オブジェクトを作りました。
「cache」をconsole.logすると1万行あるのでちょっと固まりましたが、下記が出力されました。

中略

こんな感じで1-10000までのキー、中身は全て1のハッシュができました。
ちなみに、1-10000というわかりやすい配列ですが、
例えばhomeListが[1,5,9,30]とかだとこうなります。

値がないところはそもそもオブジェクト自体が未設定（undefined）なので表示自体されません。

では、キャッシュを使って、重複部分を洗い出してみましょう。
presentlstをfor文で回します。

for(let j = 0; j < presentList.length; j++){
    //homeListのcacheのなかの値が「presentList[j]」のものが、
    //値1以上（つまりundefinedではない）なら、プレゼント配ったリストに詰め込む。
    if(cache[presentList[j]] !== undefined){
        doneList.push(presentList[j]);
    }
}

まとめると、こういうコードになります。

let homeList = [...Array(10000).keys()];
let presentList = [...Array(100).keys()];
let doneList = [];
const startTime = performance.now(); // 開始時間


//まずはhomeListのキャッシュを作る。オブジェクト作成
let cache = {};

for ( let i = 0; i < homeList.length; i++ ){
    if(cache[homeList[i]] == undefined){ //もし、キャッシュの[i]番目がundefinedなら、1を入れる。
        cache[homeList[i]] = 1;
    }else{
        cache[homeList[i]]++ ;　//もし、すでに数字が入ってるなら、さらに値を1ふやす
    }
}

for(let j = 0; j < presentList.length; j++){
    //homeListのcacheのなかの値が「presentList[j]」のものが、
    //値1以上（つまり存在している）なら、プレゼント配ったリストに詰め込む。
    if(cache[presentList[j]] !== undefined){
        doneList.push(presentList[j]);
    }
}


const endTime = performance.now(); // 終了時間
console.log(endTime - startTime); // 何ミリ秒かかったかを表示する
console.log("配れたリスト" + doneList);

このコードを実施してみました！

2ミリ秒です！ぐっと速くなりました。
何度か試しましたが、0から2ミリ秒って感じです。

何が違うのか？

コードBでは、最初に配る人リスト（homeList）をキャッシュにするため、forを10000回、回してます。

次に、100個のプレゼントリスト（presentList）を回しています。presentListを回しながらキャッシュを参照しているので、配る人リスト（homeList）をforで回す必要がありません。

具体的には、
コードAだと1万*100の100万回forを回してますが、
コードBだと10100回しか回してないので、ぐっと計算量が少ないです。

今回のリストはサンプルとして連番で作ったので、人間の目で見れば、重複しているのは1-100だな、とすぐわかります。
が、リストAとリストBの数字が連番ではなかったり、それぞれの配列が文字列だったりすると、かつ膨大なリストだと重複部分は洗い出すのは大変です。

さらに数字が大きくなればなるほど、コードA：二重forだと処理数が増えてしまいますが、コードBだと計算量の肥大化を抑えられます。
※試しにhomeListを100000回にすると、計算にかかる時間はコードAだと140ミリ秒、コードBだと6ミリ秒ほどでした！

サンタさんありがとう

サンタの仕事の負担が少しでも減って余興時間を作れると嬉しいですね。

まとめ

長文になりすぎてすみませんでした！
実務の中で素の言語でこんなことをやるケースはあるのか？というとわかりませんが、シンプルに面白かったし、勉強になりました。
ここまで読んでいただいた方、ありがとうございます！