コンパイラかく語りき

import { Fun } from 'programming'

配列よりもオブジェクトを使う局面があると学ぶ

競技プログラミングで初めて制限時間に引っかかりました。

対処法を考えているうちに、データ構造について1つ学びがあったのでメモします。

 

ちなみに、重くなった原因はユニーク判定の仕方でした。

 

最初に書いたコードがこちら。

gist9b15f1b88ba817838fc7

indexOfを使っているところが味噌ですね。

indexOfは指定した要素が配列の何番目にあるかを返します。もし指定した要素が配列の中に存在しない場合は、-1を返します。

この仕様を利用して、一意性(ユニークかどうか)を判定することができます。

 

そしてもし一意でなければ、配列に数値を新規追加します。

 

でも、indexOfってたぶん、配列の全要素を調べてると思うんですよね。それで遅くなっていたっぽいです。

 

それが上記のコードでした。

 

これを改変したのが次のコード。

gistfaa770bc104ae38971e0

 

改良後のコードでは、処理速度が圧倒的に速くなりました。こちらではオブジェクトに要素を新規追加しています。

なので、配列とは異なり、ある要素が存在するかどうかをダイレクトに尋ねることができます。

 

ここからは、得られた知見なのですが、オブジェクトってバカにできませんね。

今までは配列をベースのコードを書いてきたのですが、オブジェクトもけっこう便利!(何を今さらって感じですが)

 

特に、順序立てが重要ではない場合は、積極的にオブジェクトを使っていくべきかもしれません。

不要な場面で配列を使ってしまうと、不要なindex走査を行ってしまう恐れがあると、今回の件で学ぶことができました。