Most efficient way to search for object in an array by a specific property's value

Question

What would be the fastest, most efficient way to implement a search method that will return an object with a qualifying id?

Sample object array:

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

What do I write inside of:

function findObjectById($id){

}

The desired result would return the object at $array[0] if I called:

$obj = findObjectById('one')

Otherwise, it would return false if I passed 'four' as the parameter.

Brisket

Answer 1

You can iterate that objects:

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

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

    return false;
}

Faster way is to have an array with keys equals to objects' ids (if unique);

Then you can build your function as follow:

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

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

    return false;
}

Ruano

ok, i thought of that, but i think that there maybe a more cost efficient method. I will accept your answer if i don't get a "better" one in one hour. thanks – Mailemailed

thanks, i cannot guarantee that the id property would match the named index of the array – Mailemailed

So in that case you have no other solution than iterate whole array and stop if object's id matches. – Ruano

Works like a charm if you remember to access it using $this->findObjectById($id) in a class. – Fordo

In my case I needed something more like: if ( $value == $element['term'] ) { return $element['id']; } – Shockproof

Answer 2

For the canonical reference:

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

The false is per the questions requirement to return false. It represents the non-matching value, e.g. you can make it null for example as an alternative suggestion.

This works transparently since PHP 7.0. In case you (still) have an older version, there are user-space implementations of it that can be used as a drop-in replacement.

However array_column also means to copy a whole array. This might not be wanted.

Instead it could be used to index the array and then map over with array_flip:

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

On the index the search problem might still be the same, the map just offers the index in the original array so there is a reference system.

Keep in mind thought that this might not be necessary as PHP has copy-on-write. So there might be less duplication as intentionally thought. So this is to show some options.

---

Another option is to go through the whole array and unless the object is already found, check for a match. One way to do this is with array_reduce:

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

This variant again is with the returning false requirement for no-match.

It is a bit more straight forward with null:

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

And a different no-match requirement can then be added with $obj = ...) ?? false; for example.

Fully exposing to foreach within a function of its own even has the benefit to directly exit on match:

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

This is effectively the original answer by hsz, which shows how universally it can be applied.

Dail

To clarify for researchers: Only the final snippet in this answer will be most performant. All other techniques are performing at least one full cycle over the array. – Deipnosophist

@mickmackusa: Yes, this is true but it might not be the full story if you want to cope with duplicate IDs/keys as in PHP array semantics where the last one wins. Then you need to go over the whole array (but still PHPs foreach() is very fast for such iterations and checks). So yes, for many purposes, don't neglect a foreach approach while implementing. – Dail

Answer 3

You can use the function array_search of php like this

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

Microgamete

Please note array_column is only available in PHP > 5.5.0 – Voroshilovsk

array with objects is only available in PHP > 7.0 – Luciennelucier

The reason this approach will not be most efficient is because, (ignoring the extract unnecessary json manipulations) array_column() will be traversing the whole array, then array_search() will be traversing upto the full array again. There are simpler / more performant techniques demonstrated on this page. – Deipnosophist

Answer 4

i: is the index of item in array

1: is the property value looking for

$arr: Array looking inside

'ID': the property key

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

Marcelo

The reason this approach will not be most efficient is because, array_column() will be traversing the whole array, then array_search() will be traversing upto the full array again. There are simpler / more performant techniques demonstrated on this page. – Deipnosophist

Answer 5

Well, you would would have to loop through them and check compare the ID's unless your array is sorted (by ID) in which case you can implement a searching algorithm like binary search or something of that sort to make it quicker.

My suggestion would be to first sort the arrays using a sorting algorithm (binary sort, insertion sort or quick sort) if the array is not sorted already. Then you can implement a search algorithm which should improve performance and I think that's as good as it gets.

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

Lakes

thanks, i don't have any way to guarantee that my array is sorted by the objects' ids, or a anything else. I will probably use the loop. – Mailemailed

Well you will never have a guarantee unless you do something about it. You should loop through the items only once at the beginning and sort them (or if you don't want to change the array) you can create another array that references objects in the other array in a ascending/descending order and that way every search thereafter will be fast. – Lakes

Answer 6

This is my absolute favorite algorithm for very quickly finding what I need in a very large array, quickly. It is a Binary Search Algorithm implementation I created and use extensively in my PHP code. It hands-down beats straight-forward iterative search routines. You can vary it a multitude of ways to fit your need, but the basic algorithm remains the same.

To use it (this variation), the array must be sorted, by the index you want to find, in lowest-to-highest order.

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;
}

And to test it out:

/* 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";

Now, a few notes:

You MAY use this to find non-unique indexes; the array MUST still be sorted in ascending order. Then, when it finds an element matching your criteria, you must walk the array backwards to find the first element, or forward to find the last. It will add a few "hops" to your search, but it will still most likely be faster than iterating a large array.

For STRING indexes, you can change the arithmetic comparisons (i.e. " > " and " < " ) in quick_find() to PHP's function "strcasecmp()". Just make sure the STRING indexes are sorted the same way (for the example implementation): Alphabetically and Ascending.

And if you want to have a version that can search arrays of objects sorted in EITHER ascending OR decending order:

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);
    }
}

Crocoite

Answer 7

The thing with performance of data structures is not only how to get but mostly how to store my data.

If you are free to design your array, use an associative array:

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

Finding is then the most cheap: $one = $array['one];

UPDATE:

If you cannot modify your array constitution, you could create a separate array which maps ids to indexes. Finding an object this way does not cost any time:

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

getObjectById() then first lookups the index of the id within the original array and secondly returns the right object:

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

Amaryl

thanks, but i really need to keep this sequentially, and nothing would guarantee that the id property would match the named index of the array :) – Mailemailed

Creating a copy of the object array with searchable first level keys will not be the most performant approach. Better to find another approach that implements an early return/break. – Deipnosophist

@Deipnosophist It depends. It's definitely not worth to create a copy only to perform a single search, but in some cases (e.g. multiple searches, long-running processes) it makes sense to ingest data once at the startup in order to expose efficient search API. – Graniah

Answer 8

Something I like to do in these situations is to create a referential array, thus avoiding having to re-copy the object but having the power to use the reference to it like the object itself.

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

Then we can create a simple referential array:

$ref = array();
foreach ( $array as $row )
    $ref[$row->id] = &$array[$row->id];

Now we can simply test if an instance exists in the array and even use it like the original object if we wanted:

if ( isset( $ref['one'] ) )
    echo $ref['one']->color;

would output:

white

If the id in question did not exist, the isset() would return false, so there's no need to iterate the original object over and over looking for a value...we just use PHP's isset() function and avoid using a separate function altogether.

Please note when using references that you want use the "&" with the original array and not the iterator, so using &$row would not give you what you want.

Grownup

The reference variable is not advantageous. This answer is unnecessarily populating a full copy of the input data before searching by key. This is not going to be the most performant approach because it does not implement an early return. – Deipnosophist

Answer 9

Here is what I use. Reusable functions that loop through an array of objects. The second one allows you to retrieve a single object directly out of all matches (the first one to match criteria).

function get_objects_where($match, $objects) {
    if ($match == '' || !is_array($match)) return array ();
    $wanted_objects = array ();
    foreach ($objects as $object) {
        $wanted = false;
        foreach ($match as $k => $v) {
            if (is_object($object) && isset($object->$k) && $object->$k == $v) {
                $wanted = true;
            } else {
                $wanted = false;
                break;
            };
        };
        if ($wanted) $wanted_objects[] = $object;
    };
    return $wanted_objects;
};

function get_object_where($match, $objects) {
    if ($match == '' || !is_array($match)) return (object) array ();
    $wanted_objects = get_objects_where($match, $objects);
    return count($wanted_objects) > 0 ? $wanted_objects[0] : (object) array ();
};

Ilailaire

Answer 10

This is definitely not efficient, O(N). But it looks sexy:

 $result = array_reduce($array, function ($found, $obj) use ($id) {
     return $obj['id'] == $id ? $obj : $found;
 }, null);

addendum: I see hakre already posted something akin to this.

Bujumbura

The asker is not seeking "sexy". They asked for an efficient approach. This answer will not be most efficient because it does not have the ability to perform an early return. – Deipnosophist

Answer 11

I'm wondering, why nobody already mentioned array_filter. I don't know how bad the performance may be, but for normal usage, it seems to be a very comfortable way for me. This is my solutions I actually use all the time.

$foundItem = array_values(
   array_filter($someArray, fn($item) => $item->someProperty() == 'desiredValue')
);
$foundItem = $foundItem[0] ?? null;

I came here to find an even shorter way, but everything else seems to be much less intuitive with much more lines of code for me.

Seasick