[Php] Tetrisare un array


Answers

Caricalo in una struttura dati trie. A partire dal nodo genitore, vedi quale ha un numero di figli maggiore di uno. Una volta trovato quel nodo magico, basta smantellare la struttura del nodo genitore e avere il nodo corrente come root.

Question

Considera la seguente matrice:

/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

qual è il modo più breve ed elegante per individuare il percorso di base comune - in questo caso

/www/htdocs/1/sites/

e rimuoverlo da tutti gli elementi dell'array?

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



Ok, non sono sicuro che questo sia a prova di proiettile, ma penso che funzioni:

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;
});

Questo prenderà il primo valore dell'array come stringa di riferimento. Quindi eseguirà un iterazione sulla stringa di riferimento e confronterà ciascun carattere con il carattere della seconda stringa nella stessa posizione. Se un char non corrisponde, la stringa di riferimento verrà abbreviata nella posizione del char e la stringa successiva verrà confrontata. La funzione restituirà quindi la stringa di corrispondenza più breve.

Le prestazioni dipendono dalle stringhe fornite. Quanto prima la stringa di riferimento si accorcia, tanto più veloce sarà il codice. Non ho davvero idea di come metterlo in una formula però.

Ho scoperto che l'approccio di Artefacto per ordinare le stringhe aumenta le prestazioni. Aggiunta

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

prima che array_reduce aumenti significativamente le prestazioni.

Si noti inoltre che questo restituirà la sottostringa iniziale più lunga corrispondente , che è più versatile ma non ti darà il percorso comune . Devi correre

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

sul risultato. E poi puoi usare il risultato per rimuovere i valori

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

che dovrebbe dare:

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

Feedback benvenuto




Questo ha il vantaggio di non avere una complessità temporale lineare; tuttavia, per la maggior parte dei casi il tipo non sarà sicuramente l'operazione che richiede più tempo.

Fondamentalmente, la parte intelligente (almeno non ho trovato un difetto) qui è che dopo l'ordinamento dovrai solo confrontare il primo percorso con l'ultimo.

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);



Bene, ci sono già alcune soluzioni qui, ma solo perché è stato divertente:

$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 '</pre>';

Produzione:

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



Forse porting dell'algoritmo Gli usi os.path.commonprefix(m) Python funzionerebbero?

def commonprefix(m):
    "Given a list of pathnames, returns the longest common leading component"
    if not m: return ''
    s1 = min(m)
    s2 = max(m)
    n = min(len(s1), len(s2))
    for i in xrange(n):
        if s1[i] != s2[i]:
            return s1[:i]
    return s1[:n]

Cioè, uh ... qualcosa come

function commonprefix($m) {
  if(!$m) return "";
  $s1 = min($m);
  $s2 = max($m);
  $n = min(strlen($s1), strlen($s2));
  for($i=0;$i<$n;$i++) if($s1[$i] != $s2[$i]) return substr($s1, 0, $i);
  return substr($s1, 0, $n);
}

Dopodiché puoi solo substrare ogni elemento della lista originale con la lunghezza del prefisso comune come offset iniziale.




Probabilmente troppo ingenuo e noobish ma funziona. Ho usato questo algoritmo :

<?php

function strlcs($str1, $str2){
    $str1Len = strlen($str1);
    $str2Len = strlen($str2);
    $ret = array();

    if($str1Len == 0 || $str2Len == 0)
        return $ret; //no similarities

    $CSL = array(); //Common Sequence Length array
    $intLargestSize = 0;

    //initialize the CSL array to assume there are no similarities
    for($i=0; $i<$str1Len; $i++){
        $CSL[$i] = array();
        for($j=0; $j<$str2Len; $j++){
            $CSL[$i][$j] = 0;
        }
    }

    for($i=0; $i<$str1Len; $i++){
        for($j=0; $j<$str2Len; $j++){
            //check every combination of characters
            if( $str1[$i] == $str2[$j] ){
                //these are the same in both strings
                if($i == 0 || $j == 0)
                    //it's the first character, so it's clearly only 1 character long
                    $CSL[$i][$j] = 1; 
                else
                    //it's one character longer than the string from the previous character
                    $CSL[$i][$j] = $CSL[$i-1][$j-1] + 1; 

                if( $CSL[$i][$j] > $intLargestSize ){
                    //remember this as the largest
                    $intLargestSize = $CSL[$i][$j]; 
                    //wipe any previous results
                    $ret = array();
                    //and then fall through to remember this new value
                }
                if( $CSL[$i][$j] == $intLargestSize )
                    //remember the largest string(s)
                    $ret[] = substr($str1, $i-$intLargestSize+1, $intLargestSize);
            }
            //else, $CSL should be set to 0, which it was already initialized to
        }
    }
    //return the list of matches
    return $ret;
}


$arr = 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'
);

// find the common substring
$longestCommonSubstring = strlcs( $arr[0], $arr[1] );

// remvoe the common substring
foreach ($arr as $k => $v) {
    $arr[$k] = str_replace($longestCommonSubstring[0], '', $v);
}
var_dump($arr);

Produzione:

array(5) {
  [0]=>
  string(11) "lib/abcdedd"
  [1]=>
  string(8) "conf/xyz"
  [2]=>
  string(12) "conf/abc/def"
  [3]=>
  string(10) "htdocs/xyz"
  [4]=>
  string(12) "lib2/abcdedd"
}

:)




Bene, considerando che è possibile utilizzare XOR in questa situazione per trovare le parti comuni della stringa. Ogni volta che si superano due byte uguali, si ottiene un nullbyte come output. Quindi possiamo usarlo a nostro vantaggio:

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

Dopo questo ciclo singolo, la variabile $length sarà uguale al più lungo punto di partenza comune tra l'array di stringhe. Quindi, possiamo estrarre la parte comune dal primo elemento:

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

E il gioco è fatto. Come una funzione:

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);
}

Nota che usa più di una iterazione, ma quelle iterazioni sono fatte in librerie, quindi in linguaggi interpretati questo avrà un enorme guadagno di efficienza ...

Ora, se vuoi solo percorsi completi, dobbiamo troncare all'ultimo carattere / . Così:

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

Ora, può tagliare troppo due stringhe come /foo/bar e /foo/bar/baz sarà tagliato a /foo . Ma a parte l'aggiunta di un altro giro di iterazione per determinare se il prossimo carattere è / o alla fine della stringa, non riesco a vedere un modo per aggirare questo ...




explode i valori basati su / e quindi useremo array_intersect_assoc per rilevare gli elementi comuni e assicurarmi che abbiano l'indice corrispondente corretto nella matrice. La matrice risultante potrebbe essere ricombinata per produrre il percorso comune.

function getCommonPath($pathArray)
{
    $pathElements = array();

    foreach($pathArray as $path)
    {
        $pathElements[] = explode("/",$path);
    }

    $commonPath = $pathElements[0];

    for($i=1;$i<count($pathElements);$i++)
    {
        $commonPath = array_intersect_assoc($commonPath,$pathElements[$i]);
    }

    if(is_array($commonPath) return implode("/",$commonPath);
    else return null;
}

function removeCommonPath($pathArray)
{
    $commonPath = getCommonPath($pathArray());

    for($i=0;$i<count($pathArray);$i++)
    {
        $pathArray[$i] = substr($pathArray[$i],str_len($commonPath));
    }

    return $pathArray;
}

Questo non è verificato, ma l'idea è che l'array $commonPath contenga sempre gli elementi del percorso che sono stati contenuti in tutti gli array di percorsi che sono stati confrontati con esso. Quando il ciclo è completo, lo ricombiniamo semplicemente con / per ottenere il vero $commonPath

Aggiornamento Come sottolineato da Felix Kling, array_intersect non considera i percorsi che hanno elementi comuni ma in ordini diversi ... Per risolvere questo, ho usato array_intersect_assoc invece di array_intersect

Aggiorna codice aggiunto per rimuovere il percorso comune (o tetris!) Dall'array.