Effizienteste Methode zum Suchen nach Objekten in einem Array anhand des Werts einer bestimmten Eigenschaft

Question 1

Was wäre der schnellste und effizienteste Weg, um eine Suchmethode zu implementieren, die ein Objekt mit einer Qualifizierung zurückgibt id?

Beispiel-Objekt-Array:

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

Was schreibe ich hinein in:

function findObjectById($id){

}

Das gewünschte Ergebnis würde das Objekt at zurückgeben $array[0] wenn ich anrufe:

$obj = findObjectById('one')

Andernfalls würde es zurückkehren false wenn ich als Parameter “vier” übergebe.

Question 2

Sie können diese Objekte iterieren:

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

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

    return false;
}

Bearbeiten:

Ein schnellerer Weg ist ein Array mit Schlüsseln, die den IDs der Objekte entsprechen (falls eindeutig);

Dann können Sie Ihre Funktion wie folgt aufbauen:

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

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

    return false;
}

Question 3

Es ist eine alte Frage, aber für die kanonische Referenz, da sie in der reinen Form fehlte:

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

Das false ist gemäß der Anforderung der Fragen, „false“ zurückzugeben. Es stellt den nicht übereinstimmenden Wert dar, dh Sie können es schaffen null zum Beispiel als Alternativvorschlag.

Dies funktioniert transparent seit PHP 7.0. Falls Sie (noch) eine ältere Version haben, gibt es User-Space-Implementierungen davon, die als Drop-In-Ersatz verwendet werden können.

Jedoch array_column bedeutet auch, ein ganzes Array zu kopieren. Das ist vielleicht nicht gewollt.

Stattdessen könnte es verwendet werden Index das Array und dann map over with array_flip:

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

Auf dem Index ist das Suchproblem möglicherweise immer noch dasselbe, die Karte bietet nur den Index im ursprünglichen Array an, sodass ein Referenzsystem vorhanden ist.

Denken Sie daran, dass dies möglicherweise nicht erforderlich ist, da PHP über Copy-on-Write verfügt. Es könnte also weniger Duplizierung geben als absichtlich angenommen. Dies soll also einige Optionen zeigen.

Eine andere Möglichkeit besteht darin, das gesamte Array zu durchlaufen und auf eine Übereinstimmung zu prüfen, es sei denn, das Objekt wurde bereits gefunden. Eine Möglichkeit, dies zu tun, ist mit array_reduce:

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

Diese Variante ist wieder beim Zurückkehren false Voraussetzung für No-Match.

Es ist ein bisschen direkter mit null:

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

Und eine andere No-Match-Anforderung kann dann mit hinzugefügt werden $obj = ...) ?? false; zum Beispiel.

Vollständig ausgesetzt foreach innerhalb einer eigenen Funktion hat sogar den Vorteil, bei Übereinstimmung direkt zu beenden:

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

Dies ist praktisch die ursprüngliche Antwort von hszwas zeigt, wie universell es einsetzbar ist.

Question 4

Sie können die Funktion verwenden array_search von php so

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

Question 5

i: ist der Index des Elements im Array

1: ist der Eigenschaftswert, nach dem gesucht wird

$arr: Array, das nach innen schaut

‘ID’: der Eigenschaftsschlüssel

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

Question 6

Nun, Sie müssten sie durchlaufen und die IDs vergleichen, es sei denn, Ihr Array ist (nach ID) sortiert. In diesem Fall können Sie einen Suchalgorithmus wie eine binäre Suche oder etwas Ähnliches implementieren, um es schneller zu machen.

Mein Vorschlag wäre, die Arrays zuerst mit einem Sortieralgorithmus (binäre Sortierung, Einfügungssortierung oder schnelle Sortierung) zu sortieren, wenn das Array noch nicht sortiert ist. Dann können Sie einen Suchalgorithmus implementieren, der die Leistung verbessern sollte, und ich denke, das ist so gut wie es nur geht.

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

Question 7

Dies ist mein absoluter Lieblingsalgorithmus, um sehr schnell das zu finden, was ich in einem sehr großen Array brauche. Es ist ein Binärer Suchalgorithmus Implementierung, die ich erstellt habe und ausgiebig in meinem PHP-Code verwende. Es schlägt einfache iterative Suchroutinen zweifellos. Sie können es auf vielfältige Weise an Ihre Bedürfnisse anpassen, aber der grundlegende Algorithmus bleibt derselbe.

Um es zu verwenden (diese Variante), muss das Array nach dem Index, den Sie finden möchten, in der Reihenfolge vom niedrigsten zum höchsten sortiert werden.

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

Und um es auszuprobieren:

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

Nun ein paar Anmerkungen:

Du KANN Verwenden Sie dies, um nicht eindeutige Indizes zu finden. das Array MUSS noch in aufsteigender Reihenfolge sortiert werden. Wenn es dann ein Element findet, das Ihren Kriterien entspricht, müssen Sie das Array rückwärts durchlaufen, um das erste Element zu finden, oder vorwärts, um das letzte zu finden. Es wird Ihrer Suche ein paar “Hops” hinzufügen, aber es wird höchstwahrscheinlich immer noch schneller sein als das Iterieren eines großen Arrays.

Für STRING-Indizes können Sie die arithmetischen Vergleiche (dh ” > ” und ” < " ) in quick_find() auf die PHP-Funktion "strcasecmp()" ändern. Stellen Sie einfach sicher, dass die STRING-Indizes auf die gleiche Weise sortiert sind (für die Beispielimplementierung): Alphabetisch und aufsteigend.

Und wenn Sie eine Version haben möchten, die Arrays von sortierten Objekten durchsuchen kann ENTWEDER aufsteigend ODER absteigende Reihenfolge:

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

Question 8

Die Sache mit der Leistung von Datenstrukturen ist nicht nur, wie ich meine Daten bekomme, sondern vor allem, wie ich sie speichere.

Wenn Sie Ihr Array frei gestalten können, verwenden Sie ein assoziatives 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";

Finden ist dann am billigsten: $one = $array[‘one];

AKTUALISIEREN:

Wenn Sie Ihren Array-Aufbau nicht ändern können, könnten Sie ein separates Array erstellen, das IDs Indizes zuordnet. Ein Objekt auf diese Weise zu finden kostet keine Zeit:

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

getObjectById() sucht dann zuerst den Index der ID innerhalb des ursprünglichen Arrays und gibt zweitens das richtige Objekt zurück:

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