Rychlost rozdílu polí

PHP pole interně ukládá jako hashmapu, takže podle klíče se dá prvek najít v konstantním čase nezávisle na velikosti pole. Naopak hledání podle hodnoty má lineární složitost – musí vždycky projít všechny prvky pole.

<?php
array_key_exists($key, $array); // O(1)
isset($array[$key]); // O(1)
in_array($key, $array); // O(n)
?>

S touto znalostí bych čekal, že funkce array_diff bude pomalá, protože pracuje s hodnotami. Pokud by vypadala nějak takhle, tak by skutečně pomalá byla:

<?php
function stupid_array_diff($array1, $array2) {
    $return = array();
    foreach ($array1 as $key => $val) {
        if (!in_array($val, $array2)) {
            $return[$key] = $val;
        }
    }
    return $return;
}
?>

Ale ona je chytřejší: Nejdřív si vytvoří pole hodnot, které ve výsledku budou chybět, a pak pracuje s ním:

<?php
function smart_array_diff($array1, $array2) {
    $exclude = array();
    foreach ($array2 as $val) {
        $exclude[$val] = null;
    }
    $return = array();
    foreach ($array1 as $key => $val) {
        if (!array_key_exists($val, $exclude)) {
            $return[$key] = $val;
        }
    }
    return $return;
}
?>

Samozřejmě je funkce array_diff trochu pomalejší a trochu paměťově náročnější než array_diff_key, která si tohle pole předpočítávat nemusí, ale asymptotickou složitost mají stejnou.

Jakub Vrána, Dobře míněné rady, 4.3.2025, diskuse: 0 (nové: 0)