Как объединить массивы?

Question

[Максим]

В теории есть 2 очень больших массива, точно известно, что они уже отсортированы. Нужно получить с этих двух массивов один, также отсортированный. Для более ясного примера какой нужен результат:

$a = [1,3,6,8,12]
$b = [1,6,7,9,10,12,16]
$res = [1,1,3,6,6,7,8,9,10,12,12,16]

Вариант со встроенными функциями примером из PHP не предлагать (аля array_merge и sort), т.к. это будет работать дольше при очень больших входных данных.

Вот что сварганил на php:

$a = [1,3,5,6,7,8,9];
$b = [2,4,6,8,9,12];
$i = $j =0;
$res = [];
$c_a = count($a);
$c_b = count($b);

while ($i < $c_a && $j < $c_b )

{
  if( $a[$i] < $b[$j]){
      $res[] = $a[$i];
      $i++;    
  }elseif ($a[$i] > $b[$j]) {
      $res[] = $b[$j];
      $j++;
  }else {
      $res[] = $a[$i];
      $res[] = $a[$i];
      $i++;
      $j++;
  }
}

Но как учитывать длину, пока не допер

0 => int 1
  1 => int 2
  2 => int 3
  3 => int 4
  4 => int 5
  5 => int 6
  6 => int 6
  7 => int 7
  8 => int 8
  9 => int 8
  10 => int 9
  11 => int 9

Answer 1

[Tyranron]

Пока писал, Вы двигались в том же направлении =) .
Вот такой велосипед:

function array_merge_sorted($first, $second)
{
    $out = [];
    for (
        $f = 0, $s = 0,
        $firstLength = count($first),
        $secondLength = count($second);
        $f < $firstLength || $s < $secondLength;
    ) {
        if (!isset($first[$f])) {
            $out[] = $second[$s];
            ++$s;
        } elseif (!isset($second[$s])) {
            $out[] = $first[$f];
            ++$f;
        } elseif ($first[$f] > $second[$s]) {
            $out[] = $second[$s];
            ++$s;
        } else {
            $out[] = $first[$f];
            ++$f;
        }
    }
    return $out;
}

По времени: 1 проход по первому масиву + 1 проход по второму массиву.
По памяти: 1 размер первого массива + 1 размер второго массива, лишних аллокаций нет.

Comments

[Максим]

@Tyranron велосипед засчитан)

[Tyranron]

@maxloyko, д, хорошо, что упомянули, пример может быть на 4 строки короче, если пост-инкремент вписать прямо в индекс...аля $first[$f++]
Я просто привык по дефолту юзать пре-инкремент, и чего-то сразу не подумал.

[Сергей Протько]

@Tyranron а append к массиву не считается за реаллокацию?

[Tyranron]

@Fesor, считается. Под "лишними" я имел в виду аллокации для промежуточных вычислений, которые потом никак не используются в результате.

Answer 2

[Сергей Протько]

Как-то так?

function merge_ordered(array $a, array $b) {
   $aLen = count($a);
   $bLen = count($b);
   $resultLen = $aLen + $bLen;
   $result = new SplFixedArray($resultLen);
   for(
      $i = 0, $aIdx=0, $bIdx=0;
      $i < $resultLen;
      $i++
   ) {
      if ($aIdx === $aLen || ($bIdx < $bLen && $a[$aIdx] > $b[$bIdx])) {
         $result[$i] = $b[$bIdx++];
      } else {
         $result[$i] = $a[$aIdx++];
      }
   }

   return $result; // Ахтунг SplFixedArray вместо array!
}

На самом деле профит от этого имеется только когда массивы имеют размеры под миллион. Скажем на входных массивах в 100К элементов выигрывает таки array_merge + sort. А вот на 2 миллионах элементах в результирующем массиве выигрывает уже наша реализация.

Подумал... а может SplFixedArray и не нужен... сделал простенький бенчмарк, $a и $b по ~500К элементов. Попробовал отказаться от toArray в результате. По сути он не особо нужен... тут вам решать. Так же добавил решение @Tyranron.

https://gist.github.com/fesor/7511dd6c775b36a47226

Comments

[Максим]

Попробуйте решение @Tyranron, у меня в синтетике у него побыстрее чем ваше, не в обиду

[Максим]

array_merge + sort вообще дохнет на 100к+ в 2 масивах

[Сергей Протько]

@maxloyko можете дать ваш бенчмарк?

https://gist.github.com/fesor/7511dd6c775b36a47226

Answer 3

[Sali_cat]

ну ладно, нет так нет.

Answer 4

[KorsaR-ZN]

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

Если не хотите сортировку (но по ресурсам выйдет так же):
Сделать проход по массивам, и вставлять значения одно после нужных значений второго, при этом постоянно запоминать индекс значения в другой массив, чтобы пропускать не нужные итерации поиска позиции вставки. Я думаю идея понятно.

Правильное решение это применить алгоритм "Сортировка слиянием"

Comments

[Sali_cat]

На что надо куча оперативки и это на долго) Ему это не надо. Я уже написал вариант на js, он отказался. Привет, пора спать)

[Максим]

@KorsaR-ZN
так покажи нам алгоритм "Сортировка слиянием", в образовательных целях

[KorsaR-ZN]

@maxloyko Не вопрос, чуть позже пришлю, сюда...

[KorsaR-ZN]

@maxloyko Держите...

function mergeSort(Array $arr)
{
    $count = count($arr);

    if ($count < 2.) {
        return $arr;
    } else {

        $mIndex = ceil($count / 2.);
        return mergeAfterSort(mergeSort(array_slice($arr, 0, $mIndex)), mergeSort(array_slice($arr, $mIndex)));
    }
}

function mergeAfterSort(Array $left, Array $right)
{
    $result = [];

    while (($cLeft = count($left)) | ($cRight = count($right))) {

        if (!$cLeft) {
            $result = array_merge($result, $right);
            break;
        }

        if (!$cRight) {
            $result = array_merge($result, $left);
            break;
        }

        if ($left[0] < $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }

    }

    return $result;
}

P.S т.к у Вас уже два отсортированных массива, то можно часть алгоритма пропустить, и сразу приступить к слиянию "mergeAfterSort()"

[KorsaR-ZN]

@maxloyko Вот мой вариант оптимизированный, без вызовов array_merge, и убрал передачу по ссылки и проверку по типу, они кушают время...

Average execution time: 234 ms
Min execution time: 219 ms
Max execution time: 270 ms

function mergeAfterSort($left, $right)
{
    $result = [];

    $rightIndex = 0;
    $leftIndex  = 0;

    $cLeft  = count($left);
    $cRight = count($right);

    while ($leftIndex < $cLeft && $rightIndex < $cRight) {

        if ($left[$leftIndex] < $right[$rightIndex]) {
            $result[] = $left[$leftIndex];
            $leftIndex++;
        } else {
            $result[] = $right[$rightIndex];
            $rightIndex++;
        }
    }

    for (; $leftIndex < $cLeft; $leftIndex++) {
        $result[] = $left[$leftIndex];
    }

    for (; $rightIndex < $cRight; $rightIndex++) {
        $result[] = $right[$rightIndex];
    }

    return $result;
}