PHP
June 20, 2010
PHP has functions that can compute the difference between two arrays built in. The comments sections for those functions are filled with people trying to figure out the best way to do the same thing with multidimensional arrays, and almost all of them are recursive diffing functions that try to walk the tree and do a diff at each level.
The problem with this approach are 1) they are unreliable as they usually don’t account for all data types at each level, and 2) they’re slow, due to multiple calls to array_diff at each level of the tree.
A better approach, I think, is to flatten a multidimensional array into a single dimension, make a single call to array_diff, then (if needed) expand it back out if you really need the resulting diff to be multidimensional.
Lets look at some code. The following recursive function flattens a multidimensional array into a single dimension.
<?php
function flatten($arr, $base = "", $divider_char = "/") {
$ret = array();
if(is_array($arr)) {
foreach($arr as $k = $v) {
if(is_array($v)) {
$tmp_array = flatten($v, $base.$k.$divider_char, $divider_char);
$ret = array_merge($ret, $tmp_array);
} else {
$ret[$base.$k] = $v;
}
}
}
return $ret;
}
?>
The following function (based on this function found here) reinflates the array back up after it’s been deflated.
<?php
function inflate($arr, $divider_char = "/") {
if(!is_array($arr)) {
return false;
}
$split = '/' . preg_quote($divider_char, '/') . '/';
$ret = array();
foreach ($arr as $key = $val) {
$parts = preg_split($split, $key, -1, PREG_SPLIT_NO_EMPTY);
$leafpart = array_pop($parts);
$parent = &$ret;
foreach ($parts as $part) {
if (!isset($parent[$part])) {
$parent[$part] = array();
} elseif (!is_array($parent[$part])) {
$parent[$part] = array();
}
$parent = &$parent[$part];
}
if (empty($parent[$leafpart])) {
$parent[$leafpart] = $val;
}
}
return $ret;
}
?>
Now, with arrays in flat form, it’s easy to use the built-in functions to diff:
<?php
$arr1_flat = array();
$arr2_flat = array();
$arr1_flat = flatten($arr1);
$arr2_flat = flatten($arr2);
$ret = array_diff_assoc($arr1_flat, $arr2_flat);
$diff = inflate($ret);
?>
Read More
