[解決済み] PHPです。未定義の配列キーを処理する最速の方法

質問

非常にタイトなループの中で、数百万個の要素を含む配列の中の数万個の値にアクセスする必要があります。キーは未定義である可能性があります。その場合、エラーメッセージなしにNULLを返しても問題ありません。

配列のキーが存在する場合、その要素の値を返す。 配列のキーが存在しない場合：null を返す。

複数の解決策を知っています。

    if (isset($lookup_table[$key])) {
        return $lookup_table[$key];
    } else {
        return;
    }

または

@return $lookup_table[$key];

または

error_reporting(0);
$return = $lookup_table[$key];
error_reporting(E_ALL);
return $return;

すべての解決策は、最適とは程遠い。

• 最初のものは、B-TREEで2つのルックアップが必要です：1つは存在を確認するため、もう1つは値を取得するためです。これは事実上、実行時間を2倍にします。
• 2つ目は、エラー抑制演算子を使用しているため、その行に膨大なオーバーヘッドが発生します。
• 3つ目はエラーハンドラ（error_reportingの設定をチェックし、何も表示しない）を呼び出し、それによってオーバーヘッドを発生させるものです。

質問 は、私はエラー処理を回避し、まだ単一のBtreeルックアップで動作する方法を見逃すのですか？

いくつかの質問にお答えします。

配列は、複雑な計算の結果をキャッシュします。 何十億という値の中から、何百万という値だけが有効な結果となる。配列は、1234567 => 23457, 1234999 => 74361, ...のようになります。これを数メガバイトのPHPファイルに保存し、実行の始めにinclude_once-dします。初期ロード時間は関係ありません。 キーが見つからない場合、それは単にこの特定の値が有効な結果を返さないことを意味します。面倒なのは、これを1秒間に50k以上実行させることです。

結論

一度のルックアップで、エラー処理なしに値を取得する方法が見つからないので、一つの答えを受け入れるのは難しいです。その代わり、素晴らしい貢献にはすべてアップボートをしました。

最も貴重なご意見は、以下の通りです。

• array_key_exists を使用します。他の方法よりも高速です。
• PHPのQuickHashをチェックアウトする

PHP がどのように配列を処理するかについて、多くの混乱がありました。ソースコードを確認すると、すべての配列はバランスツリーであることがわかります。独自のルックアップ・メソッドを構築することは、CやC++では一般的ですが、 PHPのような高度なスクリプト言語ではパフォーマンス的に不利になります。

解決方法は？

更新情報

PHP 7 以降では、このようなことを行うには null coalesce演算子 :

return $table[$key] ?? null;

古い回答

まず、配列はB-treeとして実装されているのではなく、ハッシュテーブルです。（ハッシュ関数によってインデックスが付けられた）バケットの配列で、それぞれが実際の値のリンクリスト（ハッシュの衝突の場合）になっています。つまり、ハッシュ関数がバケット間の値をどれだけうまくquot;spread"したか、つまりハッシュの衝突の回数が重要な要素になるのです。

技術的には、この文が最も正しい。

return array_key_exists($key, $table) ? $table[$key] : null;

これは関数呼び出しを導入しているため 大いに は、最適化された isset() . どの程度？~2e3倍遅いです。

次は、2回目のルックアップを回避するために参照を使用します。

$tmp = &$lookup_table[$key];

return isset($tmp) ? $tmp : null;

残念ながら、この を変更します。 元の $lookup_table 配列への参照は PHP によって常に有効なものとされるからです。

残るは以下の方法ですが、これはあなたの方法とよく似ています。

return isset($lookup_table[$key]) ? $lookup_table[$key] : null;

リファレンスという副作用がない上に より速く を2回実行する場合であっても、実行時に

ルックアップにかかる時間を短縮する一つの方法として、配列を小さく分割することを検討してみてはいかがでしょうか。