Какой самый быстрый способ поиска по массиву из тысячи неизвестных объектов

Question

Какой самый быстрый способ поиска по массиву из тысячи неизвестных объектов

Я работаю над системой поиска товаров для приложения электронной коммерции, где здесь мои объекты товаров хранятся в массиве. Теперь я хочу иметь возможность искать среди этих продуктов и найти все продукты, которые принадлежат к определенной категории.
Я попытался использовать цикл foreach, но он не кажется достаточно эффективным, учитывая время выполнения и количество продуктов, через которые он должен пройти. Какой лучший способ сделать это?
Вот что я сделал:

public function sortByCategory( $category )
{
foreach ( $this->products as $product ) {
if ( $category == $product->getCategory() ) {
$this->result[] = $product;
}
}
}

1

arrays dataset php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Поиск неструктурированной / неупорядоченной коллекции всегда будет по крайней мере O(n) так как каждый элемент должен быть посещен. Если он как-то уже отсортирован, возможно, вы сможете найти более оптимальный алгоритм, но, пытаясь сначала отсортировать код вручную, вы уже будете в O(n log n) время, прежде чем даже делать поиск!

Однако вы должны искать любые приемы, которые вы можете сделать, чтобы снизить накладные расходы при последующих поисках / доступе.

Учитесь, любите и используйте магию хеш-таблиц (в php это ассоциативный массив) !!!! Они помогут вам решить многие проблемы в вашей карьере программиста!

Просто выполните итерации по продуктам и сохраните их в ассоциативном массиве массивов по имени категории:

  $grouped = [];

foreach ( $products as $product ) {
$cat = $product->getCategory();
!empty($grouped[$cat])?:$grouped[$cat] = [];
$grouped[$cat][] = $product;
}

Затем вы получаете определенную категорию по имени:

  $result = $grouped['SomeCategoryName'];

Поскольку продукты являются объектами, подмассив в $grouped Ассоциативные массивы — это просто массивы ссылок, а не дубликаты, поэтому, скорее всего, не возникнет значительного попадания в пространство.

Наконец, это только O(n) чтобы выполнить эту группировку, вы выполняете ее только один раз, и с этого момента производится поиск O(1),

0