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

В теории есть 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
  • Вопрос задан
  • 2462 просмотра
Решения вопроса 2
Tyranron
@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 размер второго массива, лишних аллокаций нет.
Ответ написан
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
Как-то так?
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
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@Sali_cat
ну ладно, нет так нет.
Ответ написан
Комментировать
KorsaR-ZN
@KorsaR-ZN
Вы не как массив не смержити без повторной сортировки, т.к после слития, вам на выходе нужен будет опять отсортированный.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы