La manière la plus rapide de gérer une clé de tableau indéfinie

Question

Dans une boucle très serrée, je dois accéder à des dizaines de milliers de valeurs dans un tableau contenant des millions d'éléments. La clé peut être indéfinie: dans ce cas, il sera légal de retourner NULL sans aucun message d'erreur :

• La clé du tableau existe : retourner la valeur de l'élément.
• La clé du tableau n'existe pas : retourner null.

Je connais plusieurs solutions :

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

ou

@return $lookup_table[$key];

ou

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

Toutes les solutions sont loin d'être optimales :

• La première nécessite 2 recherches dans l'arbre B : une pour vérifier l'existence, une autre pour récupérer la valeur. Cela double effectivement le temps d'exécution.
• La deuxième utilise l'opérateur de suppression des erreurs, et crée ainsi une surcharge massive sur cette ligne.
• La troisième appelle le gestionnaire d'erreurs (qui vérifiera le paramètre error_reporting puis n'affichera rien) et crée ainsi une surcharge.

Aurais-je raté une façon d'éviter la gestion des erreurs et pourtant travailler avec une seule recherche dans l'arbre B ?

Pour répondre à quelques questions :

Le tableau met en cache les résultats d'un calcul complexe - trop complexe pour être fait en temps réel. Sur des milliards de valeurs possibles, seuls des millions produisent un résultat valide. Le tableau ressemble à 1234567 => 23457, 1234999 => 74361, .... Cela est enregistré dans un fichier PHP de plusieurs mégaoctets, et inclus au début de l'exécution avec include_once. Le temps de chargement initial n'a pas d'importance.

Si la clé n'est pas trouvée, cela signifie simplement que cette valeur spécifique ne renverra pas un résultat valide. Le problème est de réaliser cela 50k+ fois par seconde.

Answer 1

Juste une idée soudaine qui devrait être testée, mais avez-vous essayé d'utiliser array_intersect_key() pour obtenir les valeurs existantes et un array_merge pour remplir() le reste ? Cela supprimerait le besoin d'une boucle pour accéder aux données. Quelque chose comme ça :

$searched_keys = array ('key1' => null, 'key2' => null); // la liste des clés à trouver

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

Veuillez noter que je ne l'ai pas essayé en termes de performances.

Answer 2

Je préfère utiliser la fonction isset au lieu d'échapper à l'erreur. J'ai créé une fonction pour vérifier si la clé existe et si ce n'est pas le cas, renvoie une valeur par défaut, dans le cas des tableaux imbriqués, il suffit d'ajouter les autres clés dans l'ordre :

Recherche dans un tableau imbriqué :

/**
 * Recherche de la valeur du tableau.
 *
 * @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;
}

Exemple d'utilisation :

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

array_key_lookup($array, ['clé3', 'clé3a'], 'par défaut')
'value3a'

array_key_lookup($array, ['clé2', 'clé2a'], 'par défaut')
'défaut'

array_key_lookup($array, ['clé2'], 'par défaut')
'value2'

array_key_lookup($array, ['clé5'], 'par défaut')
'défaut'

Échapper à l'erreur :

$value = @$array[$clé1][$clé2] ?: $defaultValue;

Answer 3

Tout d'abord, réorganisez les données pour les performances en enregistrant un nouveau tableau où les données sont triées par les clés, mais le nouveau tableau contient un index numérique régulier.

Cette partie prendra du temps, mais ne sera effectuée qu'une seule fois.

 // d'abord trier le tableau par ses clés
 ksort($data);

 // créer ensuite un nouveau tableau avec un index numérique
 $tmp = new array();
 foreach($data as $key=>$value)
 {
    $tmp[] = array('key'=>$key,'value'=>$value);
 }
 // maintenant enregistrez et utilisez ces données à la place
 save_to_file($tmp);

Une fois cela fait, il devrait être rapide de trouver la clé en utilisant une recherche binaire. Plus tard, vous pouvez utiliser une fonction comme celle-ci.

  function findKey($key, $data, $start, $end)
  { 
    if($end < $start) 
    { 
        return null; 
    } 

    $mid = (int)(($end - $start) / 2) + $start; 

    if($data[$mid]['key'] > $key) 
    { 
        return findKey($key, $data, $start, $mid - 1); 
    } 
    else if($data[$mid]['key'] < $key) 
    { 
        return findKey($key, $data, $mid + 1, $end); 
    } 

    return $data[$mid]['value'];
 }

Pour effectuer une recherche de clé, vous feriez ceci.

 $result = findKey($key, $data, 0, count($data));
 if($result === null)
 {
      // clé non trouvée.
 }

Si le count($data) est fait tout le temps, alors vous pourriez mettre en cache cela dans le fichier où vous avez stocké les données du tableau.

Je pense que cette méthode sera beaucoup plus rapide en performances qu'une recherche linéaire régulière qui est répétée contre le $data. Je ne peux pas promettre que c'est plus rapide. Seul un octree serait plus rapide, mais le temps nécessaire pour construire l'octree pourrait annuler la performance de recherche (j'ai déjà vécu cela). Cela dépend de la quantité de recherches à effectuer dans les données.

Answer 4

Aucun isset n'est requis. Une solution simple est de vérifier si vous avez oublié l'attribut nom dans la balise input

J'ai rencontré une erreur lorsque je n'utilisais pas l'attribut name.