◼️TechCommit Advent Calendar 2020
https://qiita.com/advent-calendar/2020/tech-commit
의 17일, 나는 naoki!
요즘은 테크커밋 추천 교재인 Recursion을 공부하고 있습니다.
https://prtimes.jp/main/html/rd/p/000000006.000062466.html

Recurston이란?

CS, 컴퓨터 과학을 배울 수 있는 웹 서비스입니다.
먼저 기본적인 각종 언어의 문법을 배우고 출력을 중심으로 데이터를 처리하면서 계산 알고리즘 등 서비스를 배운다.
끊임없는 해답을 통해 데이터 처리 방법을 파악하는 훈련임을 느낄 수 있다!
서비스의 개요는 앞의 보도와 이쪽의 보도를 참고하십시오.
https://note.com/shinya_recursion/n/n180db20428a0

해싱 맵 캐시

그중에는'현금'을 사용해 계산량을 줄이는 방법이 있어 인상적이었다.
현금.
CPU의 버스, 네트워크 등 각종 정보 전송 경로에서 정보를 특정한 구역에서 다른 구역으로 전송할 때 이 전송 지연을 극력 숨기는 것은 전송 효율을 높이기 위해 설계된 저장층의 실현 단원이다
from wiki https://ja.wikipedia.org/wiki/캐시(컴퓨터 시스템)
중요한 것은 일단 기억을 기록하면 다음 번에 이 정보를 사용할 때 기억을 참조해야 하기 때문에 데이터에 접근하는 속도를 높이는 방법이다.
간단명료하고 알기 쉬운 예로는'브라우저에 캐시를 해서 브라우저에서 과거에 보았던 페이지를 다시 볼 때 표시의 속도를 높여라'는 부분이다.
자바스크립트의 경우 연상 배열 사용하기 (js에서 대상)
어떤 경우에는 배열과 다른 고속 캐시 데이터를 만들어서 순조롭게 계산할 수 있다.
advent 달력이기 때문에 산타클로스의 업무 효율을 높일 수 있는지, 숫자를 포함한 동작을 현금으로 보고 싶습니다.

산타클로스의 일

산타클로스는 많은 사람들의 집에 선물을 보낼 것이다.
집에 번호가 배정되었다.정보화 사회.하지만 산타클로스라고 해서 만능은 아니기 때문에 한꺼번에 휴대할 수 있는 선물 수는 제한적이다.
요정이 선물해준 아이의 집 이름을 줄줄이 적어놓은 리스트 A(homeList),
상대방의 선물을 봉투에 넣은 리스트 B(present List)를 받는다.
리스트를 토대로 산타클로스가 거리로 나가 리스트 A, B 두 숫자의 집에 선물을 나눠주고 장난감 공장으로 돌아가 또 선물을 받는 간단한 작업이 밤새 일관의 시대에 반복됐다.걱정된다.
(※ 하지만 산타클로스는 면역이 있는 것 같다.https://www3.nhk.or.jp/news/html/20201215/k10012765591000.html）

산타클로스의 활동

그러면 산타클로스는 리스트 A, B를 받은 뒤 거리로 나가 장난감을 나눠줄 때 나눠준 선물을 차례대로 반납하는 함수를 만든다..
어떻게 그런 함수를 세웁니까?이렇게 생각할 때 처음에는 이중 포문이 떠올랐다.

이중 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.3으로 표시하는 처리가 있습니다
이 밖에 j의 표시는 0.1.3의 처리라고 쓰여 있다.
이 기술의 경우 결과는 다음과 같다.

4개의 i가 4개의 j 숫자를 토해내는 처리를 하기 때문에 16번의 j 처리를 한 것처럼 인상적이다.
※ 이 근방의 일은 계산량을 제곱시간이라고 하는데, 자신도 잘 모르기 때문에 미리 세부사항을 이야기한다.
그럼 방금 산타클로스의 일을 생각해 봅시다.
◼️집 목록 A
◼️선물 리스트 B
가령 있다.
목록 A-10000
목록 B는 1-10
.
이 두 목록에서 '중복된 숫자' 를 '분배된 목록' 에 채우는 처리를 만듭니다.

코드 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]]++;　
    }
}

홈리스트를 기반으로 객체를 제작했다.
“cache”console.로그면 1만 줄이 있어서 살짝 굳었지만 출력은 다음과 같습니다.

중략

이런 느낌으로 1-100의 열쇠, 내용 전부 1의 산열이 완성되었습니다.
그나저나 1-10000이라는 알기 쉬운 배열이지만
예를 들어 홈리스트가 [1,5,9,30]이면 그렇다.

값이 없는 곳은 원래 대상 자체가 설정되지 않았기 때문에 표시되지 않습니다.
그럼 현금으로 중복된 부분을 알아봅시다.
for 문장으로presentlst를 회전합니다.

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);

이 인코딩을 실시해 봤습니다!

2ms!훨씬 빠르다.
몇 번 해봤는데 0~2밀리초인 것 같아요.

뭐가 달라요?

코드 B에서 첫 번째로 나누어 준 사람의 목록을 캐시로 하기 위해 10000번의 for를 반복합니다.
이어서 나는 100개의 선물 명세서를 돌리고 있다.presentList를 돌리면서 캐시를 참조하기 때문에 for로 나누어 주는 사람 명단(home List)을 돌릴 필요가 없다.
구체적으로 말하면
코드 A면 1만*100의 100만 번 for입니다.
코드 B라면 10100번밖에 안 돌았는데 계산량이 뚝 떨어졌어요.
이번 리스트는 샘플로 연속으로 만들어졌으며, 사람의 눈에는 1-10이 중복된 것으로 금방 알 수 있었다.
그러나 리스트 A와 리스트 B의 숫자가 일련 번호가 아니고 각각의 배열이 문자열인 경우, 그리고 방대한 리스트라면 중복된 부분은 알아내기 어렵다.
숫자가 클수록 코드 A: 이중 for는 처리수가 많고 코드 B는 계산량의 증가를 억제한다.
※ 홈리스트를 100000회로 설정해보면, 계산에 걸리는 시간은 코드 A의 140ms, 코드 B의 경우 6ms 정도!

감사합니다, 산타 할아버지.

산타클로스의 업무 부담이 조금 줄어들고 여유가 있다면 나는 매우 기쁠 것이다.

총결산

맞아, 너무 길게 썼어!
실제 업무 중에 보통 언어로 이런 일을 한 적이 있습니까?몰라도 간단히 재미있게 많이 배웠어요.
여기까지 읽어주신 여러분, 감사합니다!