PHP: Schnellster Weg, um mit undefinierten Array-Schlüsseln umzugehen

In einer sehr engen Schleife muss ich auf Zehntausende von Werten in einem Array zugreifen, das Millionen von Elementen enthält. Der Schlüssel kann undefiniert sein: In diesem Fall darf NULL ohne Fehlermeldung zurückgegeben werden:

Array-Schlüssel vorhanden: Rückgabewert des Elements. Array-Schlüssel existiert nicht: Null zurückgeben.

Ich kenne mehrere Lösungen:

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

oder

@return $lookup_table[$key];

oder

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

Alle Lösungen sind bei weitem nicht optimal:

• Der erste erfordert 2 Lookups im B-TREE: Einen, um das Vorhandensein zu prüfen, einen anderen, um den Wert abzurufen. Das verdoppelt effektiv die Laufzeit.
• Der zweite verwendet den Fehlerunterdrückungsoperator und erzeugt somit einen massiven Overhead auf dieser Leitung.
• Der dritte ruft den Fehlerhandler auf (der die Einstellung error_reporting überprüft und dann nichts anzeigt) und erzeugt dadurch einen Overhead.

Meine Frage ist, wenn ich eine Möglichkeit verpasse, die Fehlerbehandlung zu vermeiden und dennoch mit einer einzigen Btree-Suche zu arbeiten?

Um einige Fragen zu beantworten:

Das Array speichert die Ergebnisse einer komplexen Berechnung – zu komplex, um in Echtzeit ausgeführt zu werden. Von Milliarden möglicher Werte liefern nur Millionen ein gültiges Ergebnis. Das Array sieht aus wie 1234567 => 23457, 1234999 => 74361, …. Das wird in einer mehrere Megabyte großen PHP-Datei gespeichert und zu Beginn der Ausführung mit include_once-d versehen. Die anfängliche Ladezeit spielt keine Rolle. Wenn der Schlüssel nicht gefunden wird, bedeutet dies einfach, dass dieser bestimmte Wert kein gültiges Ergebnis zurückgibt. Das Problem besteht darin, dies mit 50.000+ pro Sekunde zu erledigen.

Fazit

Da es keine Möglichkeit gibt, den Wert mit einer einzigen Suche und ohne Fehlerbehandlung zu erhalten, habe ich Probleme, eine einzelne Antwort zu akzeptieren. Stattdessen habe ich alle großartigen Beiträge positiv bewertet.

Die wertvollsten Inputs wo:

• Verwenden Sie array_key_exists, da es schneller ist als Alternativen
• Schauen Sie sich QuickHash von PHP an

Es gab viel Verwirrung darüber, wie PHP mit Arrays umgeht. Wenn Sie den Quellcode überprüfen, werden Sie feststellen, dass alle Arrays ausgeglichene Bäume sind. Das Erstellen eigener Suchmethoden ist in C und C++ üblich, aber in höheren Skriptsprachen wie PHP nicht performant.

Aktualisieren

Seit PHP 7 können Sie dies mit dem erreichen Null-Koaleszenz-Operator:

return $table[$key] ?? null;

Alte Antwort

Zunächst einmal werden Arrays nicht als B-Baum implementiert, sondern als Hash-Tabelle. ein Array von Buckets (indiziert über eine Hash-Funktion), jeder mit einer verknüpften Liste von tatsächlichen Werten (im Falle von Hash-Kollisionen). Das bedeutet, dass Lookup-Zeiten davon abhängen, wie gut die Hash-Funktion die Werte über die Buckets „verteilt“ hat, dh die Anzahl der Hash-Kollisionen ist ein wichtiger Faktor.

Technisch gesehen ist diese Aussage die richtigste:

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

Dies führt einen Funktionsaufruf ein und ist daher viel langsamer als die optimierte isset(). Wie viel? ~2e3 mal langsamer.

Als nächstes wird eine Referenz verwendet, um die zweite Suche zu vermeiden:

$tmp = &$lookup_table[$key];

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

Leider dies modifiziert das Original $lookup_table array, wenn das Item nicht existiert, weil Referenzen immer von PHP gültig gemacht werden.

Damit bleibt die folgende Methode übrig, die Ihrer eigenen sehr ähnlich ist:

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

Abgesehen davon, dass es nicht den Nebeneffekt von Referenzen hat, ist es auch schneller in der Laufzeit, selbst wenn die Suche zweimal durchgeführt wird.

Sie könnten Ihre Arrays in kleinere Teile unterteilen, um lange Suchzeiten zu verringern.

Ich habe ein Benchmarking mit dem folgenden Code durchgeführt:

set_time_limit(100);

$count = 2500000;
$search_index_end = $count * 1.5;
$search_index_start = $count * .5;

$array = array();
for ($i = 0; $i < $count; $i++)
    $array[md5($i)] = $i;

$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = isset($array[$key]) ? $array[$key] : null;
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";

$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = array_key_exists($key, $array) ? $array[$key] : null;
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";


$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = @$array[$key];
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";

$error_reporting = error_reporting();
error_reporting(0);
$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = $array[$key];
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";
error_reporting($error_reporting);

$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $tmp = &$array[$key];
    $test = isset($tmp) ? $tmp : null;
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";

und ich fand heraus, dass der am schnellsten laufende Test derjenige war, der verwendet isset($array[$key]) ? $array[$key] : null dicht gefolgt von der Lösung, die nur die Fehlerberichterstattung deaktiviert.

Diese Arbeit für mich

{{ isset($array['key']) ? $array['key']: 'Default' }} 

aber das geht schnell

{{ $array['key'] or 'Default' }}

Dazu gibt es zwei typische Vorgehensweisen.

1. Definieren Sie Standardwerte für einen nicht definierten Schlüssel.
2. Auf undefinierten Schlüssel prüfen.

So führen Sie den ersten und so wenig Code wie möglich aus.

$data = array_merge(array($key=>false),$data);
return $data[$key];

So führen Sie die zweite aus.

return isset($data[$key]) ? $data[$key] : false;

Nur eine plötzliche Idee, die getestet werden müsste, aber haben Sie versucht, sie zu verwenden array_intersect_key() um die vorhandenen Werte und ein array_merge zu erhalten, um den Rest zu füllen? Es würde die Notwendigkeit einer Schleife für den Zugriff auf die Daten beseitigen. Sowas in der Art :

$searched_keys = array ('key1' => null, 'key2' => null); // the list of the keys to find

$exiting_values = array_intersect_key($lookup_table, $searched_keys);
$all_values = array_merge($searched_keys, $exiting_keys);

Bitte beachten Sie, dass ich es leistungsmäßig nicht ausprobiert habe.

Der @-Operator und die error_reporting-Methoden sind beide langsamer als die Verwendung von isset. Bei beiden Methoden wird die Fehlerberichtseinstellung für PHP geändert, aber der Fehlerhandler von PHP wird weiterhin aufgerufen. Der Fehlerhandler prüft die Einstellung error_reporting und beendet sich, ohne etwas zu melden, dies hat jedoch noch einige Zeit in Anspruch genommen.

Ich verwende am liebsten die isset Funktion, anstatt den Fehler zu umgehen. Ich habe eine Funktion erstellt, um zu überprüfen, ob der Schlüssel vorhanden ist, und wenn nicht, wird ein Standardwert zurückgegeben. Bei verschachtelten Arrays müssen Sie nur die anderen Schlüssel der Reihe nach hinzufügen:

Suche nach verschachtelten Arrays:

/**
 * Lookup array value.
 *
 * @param array $array
 * @param array $keys
 * @param $defaultValue
 */
public static function array_key_lookup($array, $keys, $defaultValue)
{
    $value = $array;
    foreach ($keys as $key) {
        if (isset($value[$key])) {
            $value = $value[$key];
        } else {
            $value = $defaultValue;
            break;
        }
    }

    return $value;
}

Anwendungsbeispiel:

$array = [
    'key1' => 'value1',
    'key2' => 'value2',
    'key3' => [
        'key3a' => 'value3a',
        'key3b' => 'value3b'
    ]
];

array_key_lookup($array, ['key3', 'key3a'], 'default')
'value3a'

array_key_lookup($array, ['key2', 'key2a'], 'default')
'default'

array_key_lookup($array, ['key2'], 'default')
'value2'

array_key_lookup($array, ['key5'], 'default')
'default'

Fehler umgehen:

$value = @$array[$key1][$key2] ?: $defaultValue;