配列と連想配列 ~会津オンラインALDS1_4Cを通して~

What

会津オンラインの以下の問題を解きます。 onlinejudge.u-aizu.ac.jp

Solution

配列で書く方法を真っ先に思いついたので、それで実装してみました。

function main(lines) {
    const input = lines.split('\n').slice(1)
    const n = input.length
    
    let str = []
    for(let i=0; i<n; i++){    
        const judge = input[i].split(' ')
        if(judge[0] === 'insert'){
            str.push(judge[1])
        }        
        if(judge[0] === 'find'){
            console.log(str.includes(judge[1]) ? 'yes' : 'no')
        }
     }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

for文の代わりに、forEachメソッドを使うこともできます。

for(let i=0; i<n; i++){    
  const judge = input[i].split(' ')
}

input.forEach(function(element){
  const judge = element.split(' ')
}

ただ、上記の方法では処理に時間がかかるため、問題をクリアできません。 しかし連想配列で実装すると、処理速度が1.5倍速くなり、問題をクリアできます (処理時間はconsole.time, console.timeEndメソッドで簡単に調べています)。

function main(lines) {
    const input = lines.split('\n').slice(1)
    const n = input.length
    
    let obj = {}
    input.forEach(function(arr){
        const judge = arr.split(' ')

        if(judge[0] === 'insert'){
            obj[judge[1]]= true
        }
        if(judge[0] === 'find'){
            console.log(obj.hasOwnProperty(judge[1]) ? 'yes' : 'no')
        }
    })
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Why

なぜ、連想配列にすると処理速度が上がるのでしょうか。
連想配列と配列の違い、内部での処理について調べる必要がありそうです。
それはまた別の機会に調べて記事にします。

予想できるのは、DBにおけるインデックスと同じように、オブジェクト作成時に仕組みがあるのかもしれません。
実際、配列または連想配列に要素を追加するまでの処理時間では、配列の方が1.3倍程度速いです。