comparing values in a multidimensional array

Question

I have two arrays of arrays that have the keys 'menu_title' and 'id'.

I want to go through the two arrays and store in a third array the id of any arrays in the first array that shares a 'menu_title' with an array in the second array.

I know I can do it like so:

$collision = [];
foreach($children as $child)
    foreach($siblings as $sibling)
        if($child['menu_title'] == $sibling['menu_title'])
            $collision[] = $child['id'];

But that means I am looping over the second array for every single item in the first.

Perhaps this would be better?

$collision = [];
foreach($siblings as &$sibling)
        $sibling = $sibling['menu_title'];

    foreach($children as $child)
        if(in_array($child['menu_title'], $siblings))
            $collision[] = $child['id'];

But I still think there must be a better way?

update

The arrays are populated by sql, basically if I delete a category then I move the children categories up to the same level as the category I am deleting.

But If any of the children have the same menu_title as one of the deleting categories siblings then I need to rename the menu_title of the child to "whatever-1" e.g. "computers-1"

So I am building an array of id's I need to update and then I will do an sql update on those ID's possibly there is an enhancement to be made to how I am approaching this?

Update

So, in the end I ended up with:

$id = 4;
$category = $this->categoryeditormodel->getCategory($id);
$children = $this->categoryeditormodel->getChildCategories($id);
$siblings = $this->categoryeditormodel->getSiblingCategories($id);

foreach($siblings as &$sibling)
    $sibling = $sibling['menu_title'];

foreach($children as &$child){
    $child['parent_id'] = $category['parent_id'];
    if(in_array($child['menu_title'], $siblings)){
        $i = 0;
        while(in_array(($name = ($child['menu_title'].'-'.++$i)), $siblings));
        $child['menu_title'] = $name;
    }
}
$this->categoryeditormodel->update_batch($children);

The three functions at the top do what they say, but they are cheap as the categories are already loaded into a cache so it is not another sql query.

and update_batch is simply a shortcut to Code Igniters update_batch function but it passes through the table name and the id key.

any thoughts?

Thx for clarifying, but nested sets does my head in I always go into a loop then fry my brain. The extra data might evoke an sql solution from someone, but not me. Sorry. — Cups
– Cups, Commented Aug 22, 2012 at 10:50

bchurchill · Accepted Answer · 2012-08-22 10:33:39Z

2

Inherently this is O(m*n) where m and n are the sizes of your two arrays -- so you can't do that much better. In the end, you need to look at each (sibling, child) pair, and unless you can be more specific about how these arrays are populated, there's not much room for improvement.

There may be some tweaks to optimize this, but none immediately occur to me, and there probably isn't anything that would make a dramatic difference.

Edit: if you sort both arrays, which is O(n*log n + m*log m) first, then you could probably make some asymptotic improvement depending on what's actually in the arrays. This probably wouldn't be useful unless the arrays are rather large.

answered Aug 22, 2012 at 10:33

bchurchill

1,4209 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

LSerni · Accepted Answer · 2012-08-22 10:54:14Z

You might do this in SQL directly.

I assume that the category table is something like (I have indented the titles to show the original hierarchy):

id    parent title
1     0      computers
2     1         laptop
3     1         desktop
4     1         *servers*     <--
5     0      *servers*        <--
6     0      printers

and you want to delete 'computers' with id 1 which I'll call DEL_ID. You do this by:

retrieving information on row DEL_ID, especially the parent category id PAR_ID
updating all rows where parent is DEL_ID so that their parent becomes PAR_ID
removing the row with id DEL_ID.

When doing this, you need to check that no row with a parent of DEL_ID has the same title as any row with parent PAR_ID. When they do, you update their names.

So in SQL:

UPDATE table SET title = CONCAT(title, '-1') FROM table
    JOIN table AS check ON (
        table.parent = DEL_ID
        AND check.parent = PAR_ID
        AND table.title = check.title);

UPDATE table SET parent = PAR_ID WHERE parent = DEL_ID;
DELETE FROM table WHERE id = DEL_ID;

The problem may arise where you already have, for some reason, 'title' and 'title-1' among the siblings of victimCategory, and one of its children is again 'title'. In that case renaming 'title' to 'title-1' will cause a conflict (the same problem you had in your PHP implementation).

You can detect this situation by turning the first UPDATE into a SELECT and retrieving the "old" and "proposed" titles for the categories, then running a new SELECT to verify that there are no duplicates were you to accept the "proposed" name; and repeat incrementing the -1, -2, etc. suffix until the check select returns no conflicting rows. Or you could retrieve all titles LIKE your old "title%" in one fell swoop, and if there are any (meaning you would have a conflict) select the one numerically, not lexicographically, greater - i.e., title-11 is > title-2 -, increment by one its number and use that for the new update, which would now have to be on a one-by-one basis. It /is/ expensive, but I guess it would happen pretty rarely.

futuregeek · Accepted Answer · 2012-08-22 10:37:14Z

0

$collision = array_intersect($children, $siblings);

That should get you the array with repeating values. Check array_intersect

answered Aug 22, 2012 at 10:37

futuregeek

2842 silver badges8 bronze badges

Comments

PiTheNumber · Accepted Answer · 2012-08-22 10:39:33Z

0

I don't think there is a better way to do this. If you want to compare two arrays you have to walk over them in a loop. You may create an index like in a database but if you arrays do not contain >1000? elements that is not worth it.

Anyway, to create an index:

$index = array();
foreach($siblings as $sibling)
{
  $index[$sibling['menu_title']] = true;
}
foreach($children as $child)
{
  if (isset($index[$child['menu_title']])) $collision[] = $child['id'];
}

edited Aug 22, 2012 at 10:39

answered Aug 22, 2012 at 10:34

PiTheNumber

23.7k17 gold badges115 silver badges191 bronze badges

Collectives™ on Stack Overflow

comparing values in a multidimensional array

update

Update

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

update

Update

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related