Объединить элементы массива на основе частичных ключей массива

Question

У меня есть заданный многомерный массив, например:

$givenArray = [
    'one__111__' => [ 'more' => '000'],
    'one__111__xyz' => [ 'more' => '000'],
    'hey__121__' => [ 'more' => '000'],
    'hey__121__abc' => [ 'more' => '000'],
    'zzz__212__' => [ 'more' => '000'],
    'zzz__212__b' => [ 'more' => '000'],
    'abc__3__' => [ 'more' => '000'],
];

Мне нужно сопоставить пары, если они начинаются с одинакового имени ключа. Так что one__111__ и one__111__xyz - это пара.

Результат должен выглядеть следующим образом:

[
    ['one__111__'] => [
        [0] => ['one__111__' => ['more' => '000']],
        [1] => ['one__111__xyz' => ['more' => '000']]
    ],
    ['hey__121__'] =>
        [0] => ['hey__121__' => ['more' => '000']],
        [1] => ['hey__121__abc' => ['more' => '000']]
    ]
    ['zzz__212__'] =>
        [0] => ['zzz__212__' => ['more' => '000']],
        [1] => ['zzz__212__b' => ['more' => '000']]
    ]
    ['abc__3__'] =>
        [0] => ['abc__3__' => ['more' => '000']]
    ]
]

Это то, что я пробовал. Я считаю, что это O (n2)

$result = [];

foreach($givenArray as $key => $value) {
    foreach($result as $resultItemKey => $resultItemValue) {
        if(substr($key, 0, strlen($resultItemKey)) === $resultItemKey)  {
            $result[$resultItemKey][] = [$key => $value];
            continue 2;
        }
    }
    $result[$key][] = [$key => $value];
}

Я искал функции фильтра / уменьшения / отображения массива, но не смог найти "правильную". Какую функцию массива следует использовать? Как я предполагаю, мне нужна функция массива, которая перебирает каждый элемент и позволяет мне передать вновь созданный массив. Есть ли такая функция в PHP?

PHP коде песочницы для игры с

Answer 1

Пока ключи отсортированы, как показано в примере данных, вам нужно только сравнить текущий ключ с последним ключом, который был вставлен в выходной массив:

$result = [];
$resultItemKey = '#';  // something that a key can't start with
foreach($givenArray as $key => $value) {
    if(substr($key, 0, strlen($resultItemKey)) === $resultItemKey)  {
        $result[$resultItemKey][] = [$key => $value];
    }
    else {
        $result[$key][] = [$key => $value];
        $resultItemKey = $key;
    }
}

Вывод слишком длинный показывать здесь, но по желанию.

Демонстрация на 3v4l.org

Обратите внимание, что если ключи не отсортированы, вы всегда можете использовать ksort чтобы отсортировать массив по ним.

Answer 2

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

Это должно уменьшить вас до O (n ㏒ n):

ksort($givenArray); // Or clone it first if you want to maintain the original array

$result = [];
for ($i=0;$i < count($givenArray);$i++) {
    $thisKey = array_keys($givenArray)[$i]; // O(1)
    $result[$thisKey] = [ $thisKey => [ $givenArray[$thisKey] ] ];
    while ($i < count($givenArray)-1 
          && substr(array_keys($givenArray)[$i+1], 0, strlen($thisKey)) === $thisKey) {
            $result[$thisKey][array_keys($givenArray)[$i+1]] = $givenArray[array_keys($givenArray)[$i+1]];
            $i++;
    }
}

Answer 3

Это должно работать -

$new = [];
$keys = [];
// Extract keys as per pattern
foreach ($givenArray as $key => $val) {
    preg_match('/[a-z]+\_+\d+\_+/', $key, $match);
    $keys[] = $match[0];
}
// filter array for each extracted keys
foreach ($keys as $key) {
    $new[$key] = array_filter($givenArray, function($k) use($key) {
        return strpos($k, $key) !== false;
    }, ARRAY_FILTER_USE_KEY);
}

Вывод

Array
(
    [one__111__] => Array
        (
            [one__111__] => Array
                (
                    [more] => 000
                )

            [one__111__xyz] => Array
                (
                    [more] => 000
                )

        )

    [hey__121__] => Array
        (
            [hey__121__] => Array
                (
                    [more] => 000
                )

            [hey__121__abc] => Array
                (
                    [more] => 000
                )

        )

    [zzz__212__] => Array
        (
            [zzz__212__] => Array
                (
                    [more] => 000
                )

            [zzz__212__b] => Array
                (
                    [more] => 000
                )

        )

    [abc__3__] => Array
        (
            [abc__3__] => Array
                (
                    [more] => 000
                )

        )

)

Answer 4

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

<?php

class Node{
    public $char,$data,$children,$end,$key;
    function __construct($char){
        $this->char = $char;
        $this->data = [];
        $this->children = [];
        $this->end = false;
    }
}

class Trie{
    private $root,$result;
    function __construct($data){
        $this->root = new Node('~');
        $this->result = [];
        foreach($data as $key => $value){
            $this->insert($key);
        }
        foreach($data as $key => $value){
            $this->add($key,$value);
        }
    }

    private function insert($key){
        $temp = $this->root;
        $len = strlen($key);
        for($i=0;$i<$len;++$i){
            if(!isset($temp->children[$key[$i]])){
                $temp->children[$key[$i]] = new Node($key[$i]);
            }
            $temp = $temp->children[$key[$i]];
            if($temp->end) break;
        }
        if(!$temp->end) $temp->key = $key;
        $temp->end = true;
    }

    private function add($key,$value){
        $temp = $this->root;
        $len = strlen($key);
        for($i=0;$i<$len;++$i){
            $temp = $temp->children[$key[$i]];
            if($temp->end) break;
        }
        $temp->data[] = [$key => [$value]];
    }

    public function getResult(){
        $this->getResultHelper($this->root);
        return $this->result;
    }

    private function getResultHelper(Node $root){
        if($root->end){
            $this->result[$root->key] = $root->data;
            return;
        }

        foreach($root->children as $key => $node){
            $this->getResultHelper($node);
        }
    }
}

print_r((new Trie($givenArray))->getResult());

Демонстрация: https://3v4l.org/ag5pF

В приведенном выше коде мы сначала строим Tr ie узлов ключей и отметьте end для соответствующих узлов (ключи, которые заканчиваются первыми) в insert(). Теперь, в методе add(), мы добавляем фактические данные пары ключ-значение для этих узлов Tr ie и, наконец, получаем результат с помощью getResult().

Сложность времени должна составлять почти ~ O(n), так как длина ключа, кажется, составляет максимум 10 прибл. Даже если это в среднем 100, это будет O (n * 100) ~ O (n).