2
\$\begingroup\$

I have an array whose members are arrays containing strings. Each array has 5 elements, some of which may be empty but always at the end of the array. The order of the strings matters because their hierarchical labels—call them catLists. I need all the longest unique lists, ie. some of the shorter catLists are contained within longer ones, and for my purposes the shorter ones are redundant.

Here's a sample of the data:

// in fact my $catLists array is hundreds of elements long and changing weekly     
$catLists = array( 
                    0 => array('500ml', '750ml', '', '', '')
                    1 => array('sml', 'med', 'lrg', 'xlg', 'xxl'),
                    2 => array('big', 'bigger', 'biggest', '', ''),
                    3 => array('sml', 'med', 'lrg', '', ''),
                    4 => array('big', '', '', '', ''),
                    5 => array('300ml', '500ml', '750ml', '1L', '')
                    6 => array('1L', '750ml', '', '', ''));

// but if this were the list, then my desired output would be
$reducedCatLists = array( 
                      0 => array('sml', 'med', 'lrg', 'xlg', 'xxl'),
                      1 => array('big', 'bigger', 'biggest'),
                      2 => array('300ml', '500ml', '750ml', '1L'),
                      3 => array('1L', '750ml'));

Although sequence matters, position doesn't, which is why, for my purposes, $catLists[0] would be considered contained within $catLists[5] but $catLists[6] wouldn't.

I've no idea how to do this efficiently; right now I'm reducing every array to a string and then comparing substrings, but it's not clear to me that this is a good way to do this (self-taught programmer who leans toward design rather than math—no CS here at all).

$catList_strings = array();
        $reduced_catLists = array();
        foreach ($catLists as $i => $catList) {
            $stringified = implode("",$catList);
            $contained = false;
            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) $contained = true;
            }
            if (!$contained) {
                $catList_strings[] = $stringified;
                $reduced_catLists[] = array_filter($catList);
            }
        }

When this goes live I'd really like it not to be a burden to the server.

\$\endgroup\$
2
\$\begingroup\$

Bug

Try the following input:

$catLists = array( 
                    0 => array('sml', 'med', 'lrg', 'xlg', 'xxl'),
                    1 => array('smlmed', 'lrg', '', '', ''));

I think that this will produce just one row of output, although it should produce two (these arrays are distinct). To avoid this, you should check the arrays after finding matching strings or use some character that would never appear in the strings to join them. If you change the join character, note that you may have to trim out the empty portion before generating the string.

For example, the colon (:) would work in your example:

$stringified = ':' . implode(':', $catList) . ':';

but would produce strings like :big::::: when you probably just want :big:.

Avoid unnecessary variables

            $contained = false;
            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) $contained = true;
            }
            if (!$contained) {
                $catList_strings[] = $stringified;
                $reduced_catLists[] = array_filter($catList);
            }

You can just say

            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) {
                    $catList_strings[] = $stringified;
                    $reduced_catLists[] = array_filter($catList);
                    break;
                }
            }

This is also more performant, as it stops as soon as it finds a match. The original code tried to generate more.

Consider using an associative array

You can make this more direct. Something like:

function array_contains($base, $candidate, $start = 0) {
    if (count($base) < count($candidate) - $start) {
        return false;
    }

    foreach ($base as $v) {
        if ($v != $candidate[$start]) {
            return false;
        }
    }

    return true;
}

$indexesOf = array();
foreach ($catLists as $i => $catList) {
    $trimmedList = array_filter($catList);
    foreach ($trimmedList as $j => $cat) {
        if (isset($indexesOf[$cat]) {
            if (0 == $j) {
                foreach ($indexesOf[$cat] as $index => $start ) {
                    if (array_contains($catList, $catLists[$index], $start)) {
                        break 2;
                    }
                }
            }
        } else {
            $indexesOf[$cat] = array();
        }

        $indexesOf[$cat][$i] = $j;
        $reducedCatLists[] = $trimmedList;
    }
}

This uses a dictionary lookup to search for arrays that could potentially contain the current one.

Bug 2

Perhaps this isn't an issue, but the array order matters here. You only check arrays that you've already seen. I do this as well. Not sure how much it matters, but

$catLists = array( 
                    0 => array('500ml', '750ml', '', '', ''),
                    1 => array('300ml', '500ml', '750ml', '1L', ''));

and

$catLists = array( 
                    0 => array('300ml', '500ml', '750ml', '1L', ''),
                    1 => array('500ml', '750ml', '', '', ''));

will return different results.

If you want to get the same result from both inputs, then you have to loop through the array twice. The first time, you build the lookup array. The second time, you build the reduced list.

Test

If you have historically accurate values for $catList run a test where you time how long it takes to process either way.

Note that if it only changes weekly, it may be reasonable to save $reducedCatList when it first appears. That would be unlikely to cause significant load to the server, as you can choose to do it at a time when most legitimate users don't use the server. Something like 3 AM is great, but even a time like 3 PM might work. I don't know what patterns your customers follow.

\$\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.