La forma más eficiente de buscar un objeto en una matriz por el valor de una propiedad específica

11 minutos de lectura

Avatar de usuario de André Alçada Padez
André Alçada Pádez

¿Cuál sería la forma más rápida y eficiente de implementar un método de búsqueda que devuelva un objeto con una calificación? id?

Ejemplo de matriz de objetos:

$array = [
    (object) ['id' => 'one', 'color' => 'white'],
    (object) ['id' => 'two', 'color' => 'red'],
    (object) ['id' => 'three', 'color' => 'blue']
];

¿Qué escribo dentro de:

function findObjectById($id){

}

El resultado deseado devolvería el objeto en $array[0] si llamo:

$obj = findObjectById('one')

De lo contrario, volvería false si pasé ‘cuatro’ como parámetro.

Puedes iterar esos objetos:

function findObjectById($id){
    $array = array( /* your array of objects */ );

    foreach ( $array as $element ) {
        if ( $id == $element->id ) {
            return $element;
        }
    }

    return false;
}

Editar:

La forma más rápida es tener una matriz con claves iguales a las identificaciones de los objetos (si son únicas);

Entonces puedes construir tu función de la siguiente manera:

function findObjectById($id){
    $array = array( /* your array of objects with ids as keys */ );

    if ( isset( $array[$id] ) ) {
        return $array[$id];
    }

    return false;
}

  • ok, pensé en eso, pero creo que tal vez haya un método más rentable. Aceptaré su respuesta si no obtengo una “mejor” en una hora. Gracias

    – André Alçada Pádez

    18 de agosto de 2011 a las 11:40

  • gracias, no puedo garantizar que la propiedad id coincida con el índice nombrado de la matriz

    – André Alçada Pádez

    18 de agosto de 2011 a las 11:45

  • Entonces, en ese caso, no tiene otra solución que iterar toda la matriz y detenerse si la identificación del objeto coincide.

    – hsz

    18 de agosto de 2011 a las 11:46

  • Funciona de maravilla si recuerdas acceder a él usando $this->findObjectById($id) en una clase

    – frankfurt-laravel

    25 de abril de 2021 a las 17:36


avatar de usuario de hakre
hakré

Es una pregunta antigua, pero para la referencia canónica, ya que faltaba en forma pura:

$obj = array_column($array, null, 'id')['one'] ?? false;

los false es por el requisito de preguntas para devolver falso. Representa el valor no coincidente, por ejemplo, puede hacerlo null por ejemplo, como una sugerencia alternativa.

Esto funciona de forma transparente desde PHP 7.0. En caso de que (todavía) tenga una versión anterior, existen implementaciones en el espacio de usuario que se pueden usar como reemplazo directo.

Sin embargo array_column también significa copiar una matriz completa. Esto podría no ser deseado.

En cambio, podría usarse para índice la matriz y luego mapear con array_flip:

$index = array_column($array, 'id');
$map = array_flip($index);
$obj = $array[$map['one'] ?? null] ?? false;

En el índice, el problema de búsqueda podría seguir siendo el mismo, el mapa solo ofrece el índice en la matriz original, por lo que hay un sistema de referencia.

Tenga en cuenta que esto podría no ser necesario ya que PHP tiene copia en escritura. Entonces podría haber menos duplicación como se pensó intencionalmente. Así que esto es para mostrar algunas opciones.


Otra opción es revisar toda la matriz y, a menos que ya se encuentre el objeto, buscar una coincidencia. Una forma de hacer esto es con array_reduce:

$obj = array_reduce($array, static function ($carry, $item) {
    return $carry === false && $item->id === 'one' ? $item : $carry;
}, false);

Esta variante nuevamente está con el regreso false requisito para no-match.

Es un poco más directo con null:

$obj = array_reduce($array, static function ($carry, $item) {
    return $carry ?? ($item->id === 'one' ? $item : $carry);
}, null);

Y luego se puede agregar un requisito diferente de no coincidencia con $obj = ...) ?? false; por ejemplo.

Exponerse completamente a foreach dentro de una función propia incluso tiene el beneficio de salir directamente en el partido:

$result = null;
foreach ($array as $object) {
    if ($object->id === 'one') {
        $result = $object;
        break;
    }
}
unset($object);
$obj = $result ?? false;

Esta es efectivamente la respuesta original de hszque muestra cuán universalmente se puede aplicar.

  • Para aclarar a los investigadores: solo el fragmento final de esta respuesta será el más eficaz. Todas las demás técnicas realizan al menos un ciclo completo sobre la matriz.

    – mickmackusa

    hace 16 horas


  • @mickmackusa: Sí, esto es cierto, pero puede que no sea la historia completa si desea lidiar con ID/claves duplicadas como en la semántica de matriz de PHP donde gana la última. Luego, debe revisar toda la matriz (pero aún así, foreach() de PHP es muy rápido para tales iteraciones y comprobaciones). Entonces sí, para muchos propósitos, no descuide un enfoque foreach durante la implementación.

    – hakré

    hace 14 horas

Puedes usar la función array_search de php como este

$key=array_search("one", array_column(json_decode(json_encode($array),TRUE), 'color'));
var_dump($array[$key]);

  • tenga en cuenta array_column solo está disponible en PHP > 5.5.0

    – bg17aw

    18 de febrero de 2016 a las 15:07

  • La matriz con objetos solo está disponible en PHP> 7.0

    – AndreyP

    4 de abril de 2019 a las 12:16

  • La razón por la que este enfoque no será más eficiente es porque (ignorando las manipulaciones json innecesarias de extracción) array_column() estará atravesando toda la matriz, entonces array_search() estará atravesando hasta la matriz completa de nuevo. Hay técnicas más simples / más eficaces demostradas en esta página.

    – mickmackusa

    hace 16 horas


Avatar de usuario de Ammar Ismaeel
Ismael Ammar

i: es el índice del elemento en la matriz

1: es el valor de la propiedad que busca

$arr: Matriz mirando dentro

‘ID’: la clave de propiedad

$i = array_search(1, array_column($arr, 'ID'));
$element = ($i !== false ? $arr[$i] : null);

Bueno, tendría que recorrerlos y verificar comparar las ID a menos que su matriz esté ordenada (por ID), en cuyo caso puede implementar un algoritmo de búsqueda como búsqueda binaria o algo por el estilo para hacerlo más rápido.

Mi sugerencia sería ordenar primero las matrices utilizando un algoritmo de clasificación (clasificación binaria, clasificación por inserción o clasificación rápida) si la matriz aún no está ordenada. Luego, puede implementar un algoritmo de búsqueda que debería mejorar el rendimiento y creo que eso es lo mejor posible.

http://www.algolist.net/Algorithms/Binary_search

  • gracias, no tengo ninguna forma de garantizar que mi matriz esté ordenada por los identificadores de los objetos, o cualquier otra cosa. Probablemente usaré el bucle.

    – André Alçada Pádez

    18 de agosto de 2011 a las 11:44

  • Bueno, nunca tendrás una garantía a menos que hagas algo al respecto. Debe recorrer los elementos solo una vez al principio y ordenarlos (o si no desea cambiar la matriz), puede crear otra matriz que haga referencia a los objetos en la otra matriz en orden ascendente/descendente y de esa manera cada búsqueda a partir de entonces será rápido.

    – Saad Imran.

    18 de agosto de 2011 a las 11:53

Este es mi algoritmo favorito absoluto para encontrar rápidamente lo que necesito en una matriz muy grande, rápidamente. Es un Algoritmo de búsqueda binaria implementación que creé y uso ampliamente en mi código PHP. Es indiscutiblemente mejor que las rutinas de búsqueda iterativa directa. Puede variarlo de muchas maneras para satisfacer sus necesidades, pero el algoritmo básico sigue siendo el mismo.

Para usarlo (esta variación), la matriz debe ordenarse, por el índice que desea encontrar, en orden de menor a mayor.

function quick_find(&$array, $property, $value_to_find, &$first_index) {
    $l = 0;
    $r = count($array) - 1;
    $m = 0;
    while ($l <= $r) {
        $m = floor(($l + $r) / 2);
        if ($array[$m]->{$property} < $value_to_find) {
            $l = $m + 1;
        } else if ($array[$m]->{$property} > $value_to_find) {
            $r = $m - 1;
        } else {
            $first_index = $m;
            return $array[$m];
        }
    }
    return FALSE;
}

Y para probarlo:

/* Define a class to put into our array of objects */
class test_object {
    public $index;
    public $whatever_you_want;
    public function __construct( $index_to_assign ) {
        $this->index = $index_to_assign;
        $this->whatever_you_want = rand(1, 10000000);
    }
}

/* Initialize an empty array we will fill with our objects */
$my_array = array();

/* Get a random starting index to simulate data (possibly loaded from a database) */
$my_index = rand(1256, 30000);

/* Say we are needing to locate the record with this index */
$index_to_locate = $my_index + rand(200, 30234);

/* 
 * Fill "$my_array()" with ONE MILLION objects of type "test_object" 
 * 
 * 1,000,000 objects may take a little bit to generate.  If you don't
 * feel patient, you may lower the number!
 * 
 */
for ($i = 0; $i < 1000000; $i++) {
    $searchable_object = new test_object($my_index); // Create the object
    array_push($my_array, $searchable_object); // Add it to the "$my_array" array
    $my_index++; /* Increment our unique index */
}

echo "Searching array of ".count($my_array)." objects for index: " . $index_to_locate ."\n\n";

$index_found = -1; // Variable into which the array-index at which our object was found will be placed upon return of the function.

$object = quick_find($my_array, "index", $index_to_locate, $index_found);

if ($object == NULL) {
    echo "Index $index_to_locate was not contained in the array.\n";
} else {
    echo "Object found at index $index_found!\n";
    print_r($object);
}
echo "\n\n";

Ahora, algunas notas:

MAYO use esto para encontrar índices no únicos; la matriz aún DEBE ordenarse en orden ascendente. Luego, cuando encuentre un elemento que coincida con sus criterios, debe recorrer la matriz hacia atrás para encontrar el primer elemento o hacia adelante para encontrar el último. Agregará algunos “saltos” a su búsqueda, pero lo más probable es que sea más rápido que iterar una matriz grande.

Para los índices STRING, puede cambiar las comparaciones aritméticas (es decir, ” > ” y ”

Y si desea tener una versión que pueda buscar matrices de objetos ordenados en O ascendente O orden descendente:

function quick_find_a(&$array, $property, $value_to_find, &$first_index) {
    $l = 0;
    $r = count($array) - 1;
    $m = 0;
    while ($l <= $r) {
        $m = floor(($l + $r) / 2);
        if ($array[$m]->{$property} < $value_to_find) {
            $l = $m + 1;
        } else if ($array[$m]->{$property} > $value_to_find) {
            $r = $m - 1;
        } else {
            $first_index = $m;
            return $array[$m];
        }
    }
    return FALSE;
}

function quick_find_d(&$array, $property, $value_to_find, &$first_index) {
    $l = 0;
    $r = count($array) - 1;
    $m = 0;
    while ($l <= $r) {
        $m = floor(($l + $r) / 2);
        if ($value_to_find > $array[$m]->{$property}) {
            $r = $m - 1;
        } else if ($value_to_find < $array[$m]->{$property}) {
            $l = $m + 1;
        } else {
            $first_index = $m;
            return $array[$m];
        }
    }
    return FALSE;
}


function quick_find(&$array, $property, $value_to_find, &$first_index) {
    if ($array[0]->{$property} < $array[count($array)-1]->{$property}) {
        return quick_find_a($array, $property, $value_to_find, $first_index);
    } else {
        return quick_find_d($array, $property, $value_to_find, $first_index);
    }
}

  • gracias, no tengo ninguna forma de garantizar que mi matriz esté ordenada por los identificadores de los objetos, o cualquier otra cosa. Probablemente usaré el bucle.

    – André Alçada Pádez

    18 de agosto de 2011 a las 11:44

  • Bueno, nunca tendrás una garantía a menos que hagas algo al respecto. Debe recorrer los elementos solo una vez al principio y ordenarlos (o si no desea cambiar la matriz), puede crear otra matriz que haga referencia a los objetos en la otra matriz en orden ascendente/descendente y de esa manera cada búsqueda a partir de entonces será rápido.

    – Saad Imran.

    18 de agosto de 2011 a las 11:53

Lo que pasa con el rendimiento de las estructuras de datos no es solo cómo obtener, sino principalmente cómo almacenar mis datos.

Si tiene la libertad de diseñar su matriz, use una matriz asociativa:

$array['one']->id = 'one';
$array['one']->color="white";
$array['two']->id = 'two';
$array['two']->color="red";
$array['three']->id = 'three';
$array['three']->color="blue";

Encontrar es entonces lo más barato: $one = $array[‘one];

ACTUALIZAR:

Si no puede modificar la constitución de su matriz, puede crear una matriz separada que asigne identificadores a índices. Encontrar un objeto de esta manera no cuesta nada de tiempo:

$map['one'] = 0;
$map['two'] = 1;
$map['three'] = 2;
...

getObjectById() luego, primero busca el índice de la identificación dentro de la matriz original y, en segundo lugar, devuelve el objeto correcto:

$index = $map[$id];
return $array[$index];

  • gracias, pero realmente necesito mantener esto secuencialmente, y nada garantizaría que la propiedad id coincida con el índice nombrado de la matriz 🙂

    – André Alçada Pádez

    18 de agosto de 2011 a las 11:43

  • La creación de una copia de la matriz de objetos con claves de primer nivel con capacidad de búsqueda no será el enfoque más eficaz. Es mejor encontrar otro enfoque que implemente un enfoque temprano return/break.

    – mickmackusa

    hace 16 horas

¿Ha sido útil esta solución?