Efficient way to find an object in an array using a property

Question

well, having something like:

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

no matter how fast and efficient way to implement a method such as

function findObjectById ($ id) {}

which will return the object $ array [0] if I called:

 $obj = findObjectById('one') 

and will return false if I passed "four" as a parameter.

Answer 1

You can repeat these objects:

 function findObjectById($id){ $array = array( /* your array of objects */ ); foreach ( $array as $element ) { if ( $id == $element->id ) { return $element; } } return false; } 

Edit:

An accelerated way is to have an array with keys equal to the identifiers of the objects (if they are unique);

Then you can build your function as follows:

 function findObjectById($id){ $array = array( /* your array of objects with ids as keys */ ); if ( isset( $array[$id] ) ) { return $array[$id]; } return false; } 

Answer 2

Well, you would need to go through them and check the identifier comparison if your array is not sorted (by identifier), in which case you can implement a search algorithm like binary search or something like that to make it faster .

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

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

Answer 3

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

If you can create your own 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'; 

Search is the cheapest: $ one = $ array ['one];

UPDATE:

If you cannot change the structure of the array, you can create a separate array that maps identifiers to indices. Finding an object this way is not worth the time:

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

getObjectById() then first searches for the id index in the source array and, secondly, returns the right object:

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

Answer 4

Something that I like to do in these situations is to create a reference array, which avoids a duplicate copy of the object, but has the right to use the link 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 reference array:

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

Now we can simply check if the instance exists in the array and even use it as the original object if we want:

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

outputs:

 white 

If the identifier in question does not exist, isset () returns false, so there is no need to iterate the original object again and again in search of a value ... we just use the PHP function isset () and avoid using a separate function.

Note that when using the links you want to use, "&" is with the original array, not with an iterator, so using & $ row will not give you what you want.

Answer 5

You can use array_search php function like this

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

Answer 6

Here is what I use. Reusable functions that pass through an array of objects. The second method allows you to get one object directly from all matches (the first matches the 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 (); }; 

Answer 7

This is my favorite algorithm for quickly finding what I need in a very large array, quickly. This is an implementation of the binary search algorithm that I have created and widely use in my PHP code. It easily handles iterative search procedures. You can change it in many ways to suit your needs, but the basic algorithm remains the same.

To use it (this option), the array must be sorted by the index you want to find in descending 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 check this 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 CAN use this to find non-unique indexes; the array MUST still be sorted in ascending order. Then, when it finds an element that matches your criteria, you must go back through the array to find the first element, or move forward to find the last one. This will add a few “hops” to your search, but most likely it will still be faster than iterating a large array.

For STRING indices, you can change arithmetic comparisons (that is, ">" and "<") in quick_find () to the PHP function "strcasecmp ()". Just make sure that the STRING indices are sorted the same way (for an example implementation): alphabetically and ascending.

And if you want to have a version that can search in arrays of objects sorted in ORDER in ascending or descending 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); } }