0
\$\begingroup\$

There are 2 arrays. One that consists of Categories and one of Products. Each product pertains to its specific category. I want to join each product to its right category (a category can have multiple products). Each product that 'finds' its category will go in this category's products array.

for ($i = 0; $i < count($prods); $i++)
{
    for ($u = 0; $u < count($cats); $u++)
    {
        if ($prods[$i]['category_code'] === $cats[$u]['category_style_code'])
        {
            if ( !isset($cats[$u]['products']) )
            {
                $cats[$u]['products'] = array();
            }
            array_push($cats[$u]['products'], $prods[$i]);
        }
    }
}

It results in something like:

Array
(
    [0] => Array
        (
            [id] => 1
            [category_style_code] => GA
            [products] => Array
                (
                    [0] => Array
                        (
                            [id] => 1
                            [default_price] => 37.50
                            [category_code] => GA
                        )

                    [1] => Array
                        (
                            [id] => 2
                            [default_price] => 15.00
                            [category_code] => GA
                        )
                )
        )
)

Let's say there are many categories and many products. How would you optimize this code (or do it differently)?

\$\endgroup\$
  • 2
    \$\begingroup\$ Where do the $prods and $cats come from? How many of them do you want to be able to handle? Do they come from a database query or something? Also, if this is a programming-challenge question, could you please link to the page where the challenge is presented? \$\endgroup\$ – 200_success Jan 29 '15 at 9:00
2
\$\begingroup\$

Tweaks

for ($i = 0; $i < count($prods); $i++)
{
    for ($u = 0; $u < count($cats); $u++)
    {

I'd avoid calling count on each iteration of the loop. Save the value at initialization time instead.

for ( $i = 0, $n = count($prods); $i < $n; $i++ ) {
    for ( $u = 0, $m = count($cats); $u < $m; $u++ ) {

I'd flip these around.

foreach ( $cats as &$category ) {
    foreach ( $prods as $product ) {

The switch to foreach means that you aren't having to muck with the count. It will handle that in the background.

            array_push($cats[$u]['products'], $prods[$i]);

When adding a single value, []= is more efficient than array_push.

            $category['products'][] = $product;

When you use the reference version of foreach, you should explicitly break the reference using unset when done.

unset($category);

Note that if $cats were the inner loop, we'd need to do this for every iteration of the outer loop.

So in whole, that gives us

foreach ( $cats as &$category ) {
    foreach ( $prods as $product ) {
        if ( $product['category_code'] === $category['category_style_code'] ) {
            if ( ! isset($category['products']) ) {
                $category['products'] = array();
            }

            $category['products'][] = $product;
        }
    }
}

unset($category);

New Algorithm

But we can do even better. Note that this runs count($cats) times count($prods) iterations. But we don't actually have to check every category against every product. We just need a way to look up the category for a given code.

    $category_of = array();
    foreach ( $cats as &$category ) {
        $category_of[$category['category_style_code']] = &$category;
    }
    unset($category);

Now our $prods loop can just look up the category.

    foreach ( $prods as $product ) {
        if ( isset($category_of[$product['category_code']]) ) {
            if ( ! isset($category_of[$product['category_code']]['products']) ) {
                $category_of[$product['category_code']]['products'] = array();
            }

            $category_of[$product['category_code']]['products'][] = $product;
        }
    }

If we don't mind having empty products arrays in a category, we can speed up the second loop by moving the check into the first loop.

    $category_of = array();
    foreach ( $cats as &$category ) {
        $category_of[$category['category_style_code']] = &$category;

        if ( ! isset($category['products']) ) {
            $category['products'] = array();
        }
    }
    unset($category);

Now each $category['products'] is guaranteed to be set, so we only do this check once per category not once per product. Note that we may not need to do the check. if we know that $category['products'] is not set until we do this, we can just do the assignment.

Currently we check that a given category exists before assigning. If this will always be true, then we can remove the check and just assign:

    foreach ( $prods as $product ) {
        $category_of[$product['category_code']]['products'][] = $product;
    }

Now we iterate count($cats) plus count($prods) times. This sum should be smaller than the product in most cases. The exceptions would be single element cases (only one product or one category or both). This will use more memory (for the $category_of array), but hopefully you aren't right up against the memory limit anyway.

Final Version

    $category_of = array();
    foreach ( $cats as &$category ) {
        $category_of[$category['category_style_code']] = &$category;

        $category['products'] = array();
    }
    unset($category);

    foreach ( $prods as $product ) {
        $category_of[$product['category_code']]['products'][] = $product;
    }

Another advantage of this version is that it is the first loop that does more work. Since there are more products than categories (because there are multiple products per category but only one category per product in this model), this should speed things up.

Remember our assumptions though. If they don't hold true, then the code should change:

  • $category['products'] is not set with data we need for any category prior to this code.
  • There is always a category for every $product['category_code'].

The original code did not make these assumptions. It's unclear if that is because they don't hold as it needed the checks for other purposes. Additional context might have made this clearer.

An advantage of this version is that it will throw an error if the second assumption does not hold. The original code would just leave things in an inconsistent state.

\$\endgroup\$
  • \$\begingroup\$ For what it's worth, $x = array() has more overhead (of calling a function) than initializing the array with $x = [], as shown here: ideone.com/qKEgm9. Though its not a large margin. \$\endgroup\$ – jsanc623 Jan 29 '15 at 16:46
  • 1
    \$\begingroup\$ @jsanc623 I still find myself working on PHP compilers that do not support the [] notation, so I tend not to recommend it. \$\endgroup\$ – Brythan Jan 30 '15 at 1:33
  • 1
    \$\begingroup\$ @jsanc623 I had more time and checked out your ideone link. Try reversing the order. I.e. instead of doing the [] and then the array(), try doing the array() and then the []. When running it repeatedly, there's no consistent pattern after the first two. I tried to make a better test, but it doesn't do any better at giving consistent results. \$\endgroup\$ – Brythan Jan 30 '15 at 11:19
  • \$\begingroup\$ very interesting! I wonder why that is though - cleanup/allocation? I'll have to look into the opcode \$\endgroup\$ – jsanc623 Jan 30 '15 at 16:47
1
\$\begingroup\$

To convert $cats into a lookup array, you merely need to assign new 1st level keys using each subarray's category_style_code value. array_column() allows this nifty trick.

Once your lookup array is prepared, then you only need to loop through the $prods data. When finished (and if necessary for your project) re-index the output array to remove the temporary/associative keys.

Code: (Demo)

$associative_cats = array_column($cats, null, 'category_style_code');
foreach ($prods as $row) {
    if (isset($associative_cats[$row['category_code']])) {
        $associative_cats[$row['category_code']]['products'][] = $row;
    }
}
var_export(array_values($associative_cats));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.