大量のデータ（最大10万）から値を検索 指定要素の検索 (query)

はじめに

Paiza問題集の問題です。問題は以下のものです。
指定要素の検索 (query)

※注意：内容の正しさに関しては保証できないので参考程度に

問題

Dランク問題であるため、実装内容自体はかなりシンプルなものですがデータ量が各10万まであるという問題です。レートは2000くらい。

〇問題文
長さ N の重複した要素の無い数列 A と Q 個の整数 K_1 ... K_Q が与えられるので、
各 K_i について、 A に K_i が含まれていれば "YES" を、そうでなければ "NO" を出力してください。

入力される値

N Q
A_1
...
A_N
K_1
...
K_Q

・1 行目では、配列 A の要素数 N と検索する値の個数 Q が半角スペース区切りで与えられます。
・続く N 行では、配列 A の要素が先頭から順に与えられます。
・続く Q 行では、検索する値 K_1 .. K_Q が順に与えられます

〇期待する出力
・Q 行出力してください。i 行目には A に K_i が含まれていれば "YES" を、そうでなければ "NO" を出力してください。
・また、出力の末尾には改行を入れてください。

条件は以下の通り。この問題の最大のポイントは、データ量が多いこと。

〇条件
・1 ≦ N , Q ≦ 100,000
・0 ≦ A_i ≦ 1,000,000 (1 ≦ i ≦ N)
・0 ≦ K_i ≦ 1,000,000 (1 ≦ i ≦ Q)

実装

失敗例

失敗例コード

とりあえず何も考えず実装した例が以下の通りコード。
配列に入れて、in_array()を用いて配列内に対象の数値があるかどうか判別している。

list($N, $Q) = explode(' ', trim(fgets(STDIN)));
$array = [];
for ($i = 0; $i < $N; $i++) {
    $value = trim(fgets(STDIN));
    $array[] = $value;
}

for ($i = 0; $i < $Q; $i++) {
    $value = trim(fgets(STDIN));
    if (in_array($value, $array)) {
        echo "YES";
    } else {
        echo "NO";
    }
    echo "\n";
}

失敗例結果

75点でした。多分、テスト4に関しては、データ量がかなり多く指定時間内には処理しきれなかったのかと思います。

このように、配列を用いてデータを受け取り、繰返しin_array()で判定するとプログラム全体で
Q×N回ループを回す必要がある。この問題の条件を見ると、NとQは最大10万ものデータがあるため、最大100億となってしまう。
解説によると、順序付き配列を使うとよいとのことでC++で説明してありました。
PHPで順序付き配列なるものがあるのかわからなかったため別の方法で取り組みました。

成功例

成功例コード

list($N, $Q) = explode(' ', trim(fgets(STDIN)));
$array = [];
for ($i = 0; $i < $N; $i++) {
    $value = trim(fgets(STDIN));
    $array[$value] = $value;
}

for ($i = 0; $i < $Q; $i++) {
    $value = trim(fgets(STDIN));
    if (isset($array[$value])) {
        echo "YES";
    } else {
        echo "NO";
    }
    echo "\n";
}

成功例結果

結果を見て分かるように、実行時間が短縮され無事クリアできました。
チケットを使わないとどんなデータを使っていたか確認できないためしていませんが、テスト4に関しては16秒以上かかってしまっていたものがおよそ0.36秒まで短縮できていました。

参考サイトを調べてみる

以下の記事を見つけました。
PHPの連想配列は常にin_arrayより速いのか

このの記事では、配列と連想配列で「辞書データの構築時間と検索時間の和」を比較した内容についてまとめてあります。

検索回数が多くなるほど、連想配列のほうが有利という結果となっていました。

また、このような点でisset()とin_array()で速度の差が生じたぽいです。
参考：Php: 何が速いですか：in_arrayまたはisset？

・isset()の場合は、キーに対してO(1)で検索するが、in_array()の場合一致するものが見つかるまですべての値をチェックする必要があるためデータが多くなるほど時間がかかる。

・isset()はオペコード（opcode）であるため、組み込み関数であるin_array()を呼び出すよりもオーバーヘッドが少なくなる。

単語について調べる

オペコード

オペコード (operation code, opcode) とは、機械語の1個の命令の部分で、実行する操作 (operation) の種類を指定する部分のこと、およびそのコード（符号）のことである。数式における演算子に相当する。
参考：オペコード - Wikipedi

オーバーヘッド

ITの分野では、コンピュータで何らかの処理を行う際に、その処理を行うために必要となる付加的、間接的な処理や手続きのことや、そのために機器やシステムへかかる負荷、余分に費やされる処理時間などのことをオーバーヘッドということが多い。
参考：オーバーヘッド（overhead）とは - IT用語辞典 e-Words

PHPのソースコードが実行されるまでの流れを踏まえて考える

PHPはインタプリタ言語で、その都度ソースコードを機械語に変換しながら実行している。
その流れが以下の通り。

字句解析→構文解析→オペコードにコンパイル→実行

isset()はオペコードであるため、上記流れの「字句解析」や「構文解析」を行わないためそれらを行うin_array()よりも処理時間が短いということなんだろう（多分）

参考

・PHPの連想配列は常にin_arrayより速いのか
・Php: 何が速いですか：in_arrayまたはisset？
・【書評】PHPはどのように動くのか〜PHPコアから読み解く仕組みと定石〜
・PHPのソースコードが実行されるまでの流れ

まとめ

今回は、データ量が多いときの値検索について調べてみた。
PHPのコードが実際にどんな流れで実行されているかといった根本の部分を意識するいい機会となった。正直まだ、ただ調べてまとめただけで理解が浅いため間違った理解をしていることもあると思うので今後引き続き調べていきたい。