通过特定属性的值在数组中搜索对象的最有效方法

Question

如何实现一个搜索方法，以最快、最有效的方式返回具有符合条件的 id 的对象？

示例对象数组：

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

我该在里面写什么：

function findObjectById($id){

}

如果我调用：

$array[0]

期望的结果将返回数组中的对象。

$obj = findObjectById('one')

否则，如果我将'four'作为参数传递，它将返回false。

- André Alçada Padez

Answer 1

对于规范参考：

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

根据问题要求，false表示不匹配的值，例如你可以将其设置为null作为替代建议。

自PHP 7.0版本以来，这个功能已经透明地工作。如果你（仍然）使用较旧的版本，可以使用用户空间实现的替代方案。

然而，array_column也意味着复制整个数组。这可能不是想要的。

相反，可以使用它来对数组进行索引，然后再使用array_flip进行映射：

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

在索引上，搜索问题可能仍然是相同的，地图只是提供了原始数组中的索引，因此存在一个参考系统。

请记住，PHP具有写时复制功能，所以可能会减少意外的重复。因此，这只是为了展示一些选项。

---

另一种选择是遍历整个数组，除非已经找到对象，否则检查是否存在匹配项。一种方法是使用array_reduce函数：

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

这个变体再次要求返回false以表示无匹配。

对于null，它更加直接。

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

然后可以使用$obj = ...) ?? false;来添加一个不同的不匹配要求，例如。

在自己的函数中完全暴露给foreach甚至有直接退出匹配的好处：

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

这实际上是hsz的原始答案, 它展示了它可以被普遍应用的方式。

- hakre

---

为了向研究人员澄清：只有此答案中的最终代码片段才是最高效的。所有其他技术都会对数组执行至少一个完整的循环。 - mickmackusa

@mickmackusa：是的，这是正确的，但如果您想处理重复的ID/键，就可能不是全部内容，就像在PHP数组语义中最后一个获胜一样。然后，您需要遍历整个数组（但仍然PHP的foreach()对于此类迭代和检查非常快）。因此，是的，在许多情况下，在实现时不要忽略foreach方法。 - hakre

Answer 2

您可以迭代这些对象：

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

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

    return false;
}

编辑：

更快的方法是使用一个键为对象 ID 的数组（如果 ID 是唯一的）；

然后，您可以按以下方式构建函数：

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

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

    return false;
}

- hsz

---

好的，我考虑过那个方法，但我认为可能有更加经济高效的方式。如果在一小时内没有得到“更好”的答案，我会接受你的回答。谢谢。 - André Alçada Padez

谢谢，我不能保证id属性与数组的命名索引匹配。 - André Alçada Padez

那么在这种情况下，您没有其他解决方案，只能迭代整个数组，并在对象的ID匹配时停止。 - hsz

如果你在类中使用 $this->findObjectById($id) 访问它，它就能像魔法一样工作。 - frankfurt-laravel

在我的情况下，我需要更像这样的东西：if ( $value == $element['term'] ) { return $element['id']; } - Ben in CA

Answer 3

您可以像这样使用php的函数array_search array_search

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

- chunime

---

请注意，array_column 仅适用于 PHP > 5.5.0。 - bg17aw

数组对象仅在 PHP > 7.0 版本中可用。 - AndreyP

这种方法不是最有效的原因是，（忽略提取不必要的JSON操作）array_column()将遍历整个数组，然后array_search()将再次遍历整个数组。此页面演示了更简单/更高效的技术。 - mickmackusa

Answer 4

i: 数组中项的索引

1: 要查找的属性值

$arr: 要查找的数组

'ID': 属性键

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

- Ammar Ismaeel

---

short and clear - Tadas V.

这种方法不是最有效的原因是，array_column()将遍历整个数组，然后array_search()将再次遍历整个数组。此页面演示了更简单/更高效的技术。 - mickmackusa

Answer 5

这是我最喜欢的算法之一，用于在非常大的数组中快速查找所需内容。它是我创建并广泛使用于 PHP 代码中的 二分查找算法 实现。它绝对比直接迭代搜索例程更有效。您可以以多种方式变化它以适应您的需要，但基本算法保持不变。

要使用它（这个变体），数组必须按照您想要查找的索引进行排序，按从低到高的顺序。

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

并进行测试：

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

现在，有几点需要注意：

您可以使用此方法查找非唯一索引；但是数组必须按升序排序。然后，当它找到符合您条件的元素时，您必须向后遍历数组以找到第一个元素，或向前遍历以找到最后一个元素。这将增加一些搜索的时间，但仍然比迭代大型数组要快。

对于字符串索引，您可以将quick_find()中的算术比较（即“>”和“<”）更改为PHP的函数“strcasecmp()”。只需确保字符串索引按照相同方式排序（例如实现示例）：按字母顺序和升序排列。

如果您想要一个版本，可以搜索按升序或降序排序的对象数组：

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

- Justin Jack

Answer 6

好的，你需要循环遍历数组并比较ID，除非你的数组已经按照ID排序，否则你需要实现一种搜索算法，如二分查找或类似的算法来加快速度。

我的建议是，如果数组没有排序，首先使用排序算法（二进制排序、插入排序或快速排序）对数组进行排序。然后，您可以实现一个搜索算法，这应该会提高性能，我认为这就是最好的方法。 http://www.algolist.net/Algorithms/Binary_search

- Saad Imran.

---

谢谢，我没有任何办法来保证我的数组按对象的ID或其他任何方式排序。我可能会使用循环。 - André Alçada Padez

除非你采取行动，否则你永远不会有保证。你应该在开始时只循环一次项目并对它们进行排序（或者如果你不想改变数组），你可以创建另一个数组，按升序/降序引用其他数组中的对象，这样以后每次搜索都会很快。 - Saad Imran.

Answer 7

数据结构的性能问题不仅在于如何获取数据，而更多地在于如何存储数据。

如果您可以自由设计数组，建议使用关联数组：

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

最便宜的方法是使用查找：$one = $array['one'];

更新：

如果您无法修改数组结构，可以创建一个将ID映射到索引的单独数组。这种方式查找对象不需要任何时间成本：

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

getObjectById()函数首先查找原始数组中id的索引，然后返回正确的对象：

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

- Kaken Bok

---

谢谢，但我真的需要保持这个顺序，而且没有什么能保证id属性会匹配数组的命名索引 :) - André Alçada Padez

创建一个具有可搜索的第一级键的对象数组的副本不是最高效的方法。最好找到另一种实现早期return/break的方法。 - mickmackusa

@mickmackusa 这要看情况。仅为了执行一次搜索而创建副本肯定不值得，但在某些情况下（例如多次搜索、长时间运行的进程），在启动时将数据摄取一次以提供高效的搜索API是有意义的。 - Tom Raganowicz

Answer 8

在这种情况下，我喜欢做的一件事是创建一个引用数组，这样就避免了重新复制对象，但可以像对象本身一样使用对它的引用。

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

然后我们可以创建一个简单的引用数组：

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

现在我们可以简单地测试数组中是否存在实例，甚至可以像原始对象一样使用它（如果需要的话）：

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

将输出：

white

如果所查询的id不存在，isset()会返回false，因此无需一遍又一遍地迭代原始对象查找值...我们只需使用PHP的isset()函数，避免完全使用单独的函数。

请注意，在使用引用时，您需要使用"&"与原始数组而不是迭代器，因此使用&$row将不会给您想要的结果。

- KoZm0kNoT

---

引用变量并不是一个优势。这个答案在搜索关键字之前不必要地填充了输入数据的完整副本。这不会是最有效的方法，因为它没有实现早期返回。 - mickmackusa

Answer 9

这是我使用的内容：可重复使用的函数，它可以循环遍历对象数组。第二个函数允许您直接从所有匹配项中检索单个对象（第一个符合条件的对象）。

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

- lacroixca

Answer 10

这绝对不是高效的，时间复杂度为O(N)。但它看起来很性感：

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

补充说明： 我看到hakre已经发布了类似的内容。

- jvndev

---

提问者并不是在寻求“性感”的解决方案。他们要求的是一种高效的方法。这个答案并不是最有效的，因为它没有能力执行早期的return。 - mickmackusa