Тетрис-массив

Question

Рассмотрим следующий массив:

/www/htdocs/1/sites/lib/abcdedd
/www/htdocs/1/sites/conf/xyz
/www/htdocs/1/sites/conf/abc/def
/www/htdocs/1/sites/htdocs/xyz
/www/htdocs/1/sites/lib2/abcdedd

Какой самый короткий и самый элегантный способ определения общего базового пути - в данном случае

/www/htdocs/1/sites/

и удаление его из всех элементов массива?

lib/abcdedd
conf/xyz
conf/abc/def
htdocs/xyz
lib2/abcdedd

Answer 1

Напишите функцию longest_common_prefix, которая принимает две строки в качестве входных данных.Затем примените его к строкам в любом порядке, чтобы уменьшить их общий префикс.Поскольку он является ассоциативным и коммутативным, порядок не имеет значения для результата.

Это то же самое, что и для других двоичных операций, таких как, например, сложение или наибольший общий делитель.

Answer 2

Загрузите их в структуру данных Trie. Начиная с родительского узла, посмотрите, где число детей больше одного. Найдя этот магический узел, просто демонтируйте структуру родительского узла и выберите текущий узел в качестве корневого.

Answer 3

$common = PHP_INT_MAX;
foreach ($a as $item) {
        $common = min($common, str_common($a[0], $item, $common));
}

$result = array();
foreach ($a as $item) {
        $result[] = substr($item, $common);
}
print_r($result);

function str_common($a, $b, $max)
{
        $pos = 0;
        $last_slash = 0;
        $len = min(strlen($a), strlen($b), $max + 1);
        while ($pos < $len) {
                if ($a{$pos} != $b{$pos}) return $last_slash;
                if ($a{$pos} == '/') $last_slash = $pos;
                $pos++;
        }
        return $last_slash;
}

Answer 4

Ну, учитывая, что вы можете использовать XOR в этой ситуации, чтобы найти общие части строки.Каждый раз, когда вы записываете два одинаковых байта, в качестве выходных данных вы получаете нулевой байт.Таким образом, мы можем использовать это в наших интересах:

$first = $array[0];
$length = strlen($first);
$count = count($array);
for ($i = 1; $i < $count; $i++) {
    $length = min($length, strspn($array[$i] ^ $first, chr(0)));
}

После этого единственного цикла переменная $length будет равна самой длинной общей базовой части между массивом строк.Затем мы можем извлечь общую часть из первого элемента:

$common = substr($array[0], 0, $length);

И вот она у вас.Как функция:

function commonPrefix(array $strings) {
    $first = $strings[0];
    $length = strlen($first);
    $count = count($strings);
    for ($i = 1; $i < $count; $i++) {
        $length = min($length, strspn($strings[$i] ^ $first, chr(0)));
    }
    return substr($first, 0, $length);
}

Обратите внимание, что она использует более одной итерации, но эти итерации выполняются в библиотеках, поэтому в интерпретируемых языках это будет иметь огромное повышение эффективности ...

Теперь, если вам нужны только полные пути, нам нужно усечь до последнего / символа.Итак:

$prefix = preg_replace('#/[^/]*$', '', commonPrefix($paths));

Теперь он может чрезмерно обрезать две строки, такие как /foo/bar и /foo/bar/baz будет обрезано до /foo.Но если не добавить еще один цикл итерации, чтобы определить, является ли следующий символ / или концом строки, я не могу обойти это ...

Answer 5

Вы можете удалить префикс самым быстрым способом, читая каждый символ только один раз:

function findLongestWord($lines, $delim = "/")
{
    $max = 0;
    $len = strlen($lines[0]); 

    // read first string once
    for($i = 0; $i < $len; $i++) {
        for($n = 1; $n < count($lines); $n++) {
            if($lines[0][$i] != $lines[$n][$i]) {
                // we've found a difference between current token
                // stop search:
                return $max;
            }
        }
        if($lines[0][$i] == $delim) {
            // we've found a complete token:
            $max = $i + 1;
        }
    }
    return $max;
}

$max = findLongestWord($lines);
// cut prefix of len "max"
for($n = 0; $n < count($lines); $n++) {
    $lines[$n] = substr(lines[$n], $max, $len);
}

Answer 6

Хорошо, я не уверен, что это пуленепробиваемый, но я думаю, что это работает:

echo array_reduce($array, function($reducedValue, $arrayValue) {
    if($reducedValue === NULL) return $arrayValue;
    for($i = 0; $i < strlen($reducedValue); $i++) {
        if(!isset($arrayValue[$i]) || $arrayValue[$i] !== $reducedValue[$i]) {
            return substr($reducedValue, 0, $i);
        }
    }
    return $reducedValue;
});

Это будет принимать первое значение в массиве в качестве ссылочной строки. Затем он будет перебирать ссылочную строку и сравнивать каждый символ с символом второй строки в той же позиции. Если символ не совпадает, ссылочная строка будет сокращена до позиции символа и будет сравниваться следующая строка. Затем функция вернет самую короткую подходящую строку.

Производительность зависит от заданных строк. Чем раньше строка ссылки становится короче, тем быстрее завершится код. Я действительно понятия не имею, как выразить это в формуле.

Я обнаружил, что подход Artefacto к сортировке строк повышает производительность. Добавление

asort($array);
$array = array(array_shift($array), array_pop($array));

до array_reduce значительно увеличит производительность.

Также обратите внимание, что это вернет самую длинную подходящую исходную подстроку , которая более универсальна, но не даст вам общий путь . Вы должны запустить

substr($result, 0, strrpos($result, '/'));

на результат. И тогда вы можете использовать результат, чтобы удалить значения

print_r(array_map(function($v) use ($path){
    return str_replace($path, '', $v);
}, $array));

что должно дать:

[0] => /lib/abcdedd
[1] => /conf/xyz/
[2] => /conf/abc/def
[3] => /htdocs/xyz
[4] => /lib2/abcdedd

Обратная связь приветствуется.

Answer 7

Наивным подходом было бы взорвать пути на / и последовательно сравнивать каждый элемент в массивах.Например, первый элемент будет пустым во всех массивах, поэтому он будет удален, следующим элементом будет www, он одинаков во всех массивах, поэтому он будет удален и т. Д.

Что-то вроде( не проверено )

$exploded_paths = array();

foreach($paths as $path) {
    $exploded_paths[] = explode('/', $path);
}

$equal = true;
$ref = &$exploded_paths[0]; // compare against the first path for simplicity

while($equal) {   
    foreach($exploded_paths as $path_parts) {
        if($path_parts[0] !== $ref[0]) {
            $equal = false;
            break;
        }
    }
    if($equal) {
        foreach($exploded_paths as &$path_parts) {
            array_shift($path_parts); // remove the first element
        }
    }
}

После этого вам просто нужно снова взорвать элементы в $exploded_paths:

function impl($arr) {
    return '/' . implode('/', $arr);
}
$paths = array_map('impl', $exploded_paths);

Что дает мне:

Array
(
    [0] => /lib/abcdedd
    [1] => /conf/xyz
    [2] => /conf/abc/def
    [3] => /htdocs/xyz
    [4] => /conf/xyz
)

Это может плохо масштабироваться;)

Answer 8

Это имеет то преимущество, что не имеет линейной временной сложности; однако в большинстве случаев сортировка определенно не будет операцией, занимающей больше времени.

По сути, умная часть (по крайней мере, я не смог найти в ней ошибку) заключается в том, что после сортировки вам нужно будет только сравнить первый путь с последним.

sort($a);
$a = array_map(function ($el) { return explode("/", $el); }, $a);
$first = reset($a);
$last = end($a);
for ($eqdepth = 0; $first[$eqdepth] === $last[$eqdepth]; $eqdepth++) {}
array_walk($a,
    function (&$el) use ($eqdepth) {
        for ($i = 0; $i < $eqdepth; $i++) {
            array_shift($el);
        }
     });
$res = array_map(function ($el) { return implode("/", $el); }, $a);

Answer 9

<code>$values = array('/www/htdocs/1/sites/lib/abcdedd',
                '/www/htdocs/1/sites/conf/xyz',
                '/www/htdocs/1/sites/conf/abc/def',
                '/www/htdocs/1/sites/htdocs/xyz',
                '/www/htdocs/1/sites/lib2/abcdedd'
);


function splitArrayValues($r) {
    return explode('/',$r);
}

function stripCommon($values) {
    $testValues = array_map('splitArrayValues',$values);

    $i = 0;
    foreach($testValues[0] as $key => $value) {
        foreach($testValues as $arraySetValues) {
            if ($arraySetValues[$key] != $value) break 2;
        }
        $i++;
    }

    $returnArray = array();
    foreach($testValues as $value) {
        $returnArray[] = implode('/',array_slice($value,$i));
    }

    return $returnArray;
}


$newValues = stripCommon($values);

echo '<pre>';
var_dump($newValues);
echo '

';

РЕДАКТИРОВАТЬ Вариант моего оригинального метода с использованием array_walk для перестройки массива

<code>$values = array('/www/htdocs/1/sites/lib/abcdedd',
                '/www/htdocs/1/sites/conf/xyz',
                '/www/htdocs/1/sites/conf/abc/def',
                '/www/htdocs/1/sites/htdocs/xyz',
                '/www/htdocs/1/sites/lib2/abcdedd'
);


function splitArrayValues($r) {
    return explode('/',$r);
}

function rejoinArrayValues(&$r,$d,$i) {
    $r = implode('/',array_slice($r,$i));
}

function stripCommon($values) {
    $testValues = array_map('splitArrayValues',$values);

    $i = 0;
    foreach($testValues[0] as $key => $value) {
        foreach($testValues as $arraySetValues) {
            if ($arraySetValues[$key] != $value) break 2;
        }
        $i++;
    }

    array_walk($testValues, 'rejoinArrayValues', $i);

    return $testValues;
}


$newValues = stripCommon($values);

echo '<pre>';
var_dump($newValues);
echo '

';

EDIT

Наиболее эффективный и элегантный ответ, вероятно, будет включать в себя использование функций и методов из каждого из предоставленных ответов

Answer 10

Ну, здесь уже есть некоторые решения, но только потому, что это было весело:

<code>$values = array(
    '/www/htdocs/1/sites/lib/abcdedd',
    '/www/htdocs/1/sites/conf/xyz',
    '/www/htdocs/1/sites/conf/abc/def', 
    '/www/htdocs/1/sites/htdocs/xyz',
    '/www/htdocs/1/sites/lib2/abcdedd' 
);

function findCommon($values){
    $common = false;
    foreach($values as &$p){
        $p = explode('/', $p);
        if(!$common){
            $common = $p;
        } else {
            $common = array_intersect_assoc($common, $p);
        }
    }
    return $common;
}
function removeCommon($values, $common){
    foreach($values as &$p){
        $p = explode('/', $p);
        $p = array_diff_assoc($p, $common);
        $p = implode('/', $p);
    }

    return $values;
}

echo '<pre>';
print_r(removeCommon($values, findCommon($values)));
echo '

';

Выход:

Array
(
    [0] => lib/abcdedd
    [1] => conf/xyz
    [2] => conf/abc/def
    [3] => htdocs/xyz
    [4] => lib2/abcdedd
)