Реализация сортировка слиянием, ликвидация ломтик()


У меня возникли проблемы придумывать альтернативное решение моей сортировка слиянием. Я думаю, что с помощью слайс-дорогостоящая операция. У меня есть две реализации, рекурсивные и итерационные.

function mergeSortRecursive(arr) {
// base case
if (arr.length <= 1) {
 return arr;
}

var leftArr =  arr.slice(0, arr.length/2);
var rightArr = arr.slice(arr.length/2);
var leftSorted = mergeSortRecursive(leftArr);
var rightSorted = mergeSortRecursive(rightArr);
// merge subarrays
return merge(leftSorted, rightSorted);
}

mergeSortRecursive([1,4,5,245,7, 3,3,6,31]);

function merge(left, right) {
var result = [];
var indexLeft = 0;
var indexRight = 0;
// while result is not fully populated
while(result.length < (left.length + right.length)) {
  // if all elements in left have been added, then add remaining 
right elements
  if (indexLeft === left.length) {
    result = result.concat(right.slice(indexRight));
  }
  // if all elements in right have been added, then add remaining left elements
  else if (indexRight === right.length) {
   result = result.concat(left.slice(indexLeft));
  }
  // compare elements in subarrays and add lower of the two to result
  else if (left[indexLeft] <= right[indexRight]) {
  result.push(left[indexLeft++]);
  } else {
    result.push(right[indexRight++]);
  }
 }
return result;
}



function mergeSortIterative(arr) {
// create an array of subarrays with each element
var splitArr = arr.map(function(element) {
  return [element];
});
// while there is more than one subarray
while (splitArr.length > 1) {
  var result = [];
  // merge adjacent;
  for (var i = 0; i < splitArr.length; i+=2) {
    // for pairs merge
    if (splitArr[i + 1]) result.push(merge(splitArr[i], 
 splitArr[i+1]));
    // for last odd element, just add to results
    else result.push(splitArr[i]);
  }
  // overwrite old splitArr
  splitArr = result;
  }
  return splitArr[0];
}


300
0
задан 16 февраля 2018 в 03:02 Источник Поделиться
Комментарии
1 ответ

Альтернатива ?

Не уверен, что вы подразумеваете под альтернативным решением. Слиянием сортировка слиянием сортировка и вам нужно создать массивы, через срез, вручную, или даже создание буфера и управления виртуальными массивами все понести некоторые расходы.

Ваш код.

Если вы хотите улучшить производительность, то есть много комнаты для улучшения альтернативой вашего кода.

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

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


Рекурсия, прославленный стека.

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

Рекурсия-это в действительности просто способ реализации стека. Каждая рекурсия помещает текущее состояние выполнения в стек и создать новый. Каждое возвращение располагает современное состояние и поп предыдущие одном из вершины стека.

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

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

Аннотированный код, чтобы показать, что я имею в виду


function mergeSortRecursive(arr) {

// the exit from recursion one step too deep
if (arr.length <= 1) {
return arr;
}

var leftArr = arr.slice(0, arr.length/2);
var rightArr = arr.slice(arr.length/2);

// You know at this point if both recursions are going exit early
// because the array lengths are <= 1. You should just skip the
// recursion here rather than inside the next two calls
var leftSorted = mergeSortRecursive(leftArr);
var rightSorted = mergeSortRecursive(rightArr);

return merge(leftSorted, rightSorted);
}



Функция merge

Внутри цикла while функции слияния вы делаете слишком много. Каждый 2 значения, которые должны быть по сравнению имеют накладные из двух операторов if. Они истинны только тогда, когда петля уже готова к выходу. Цикл должен заниматься только сравнение двух значений и после цикла можно очистить, добавив оставшееся содержимое массива в результате.

Улучшение слияния

Удалить ненужные, если заявления и поставить их после цикла.

function merge(left, right) {
const result = [];
while (left.length && right.length) {
result.push((left[0] <= right[0] ? left : right).shift());
}

if(left.length + right.length){
result.push(...(left.length > 0 ? left : right));
}
return result;
}


Шаг в сторону слияния.

Я вам проверять выполнение кода и массив размеров merge сливает вы заметите, что 50% из слияния двух массивов, каждый длины 1. Фактически вы используете функцию сложного слияния для сортировки двух чисел.

Вы можете подножка с функцией слияния для размеров массива 1 С следующую

Рекурсивное изменение

function mergeSort(arr) {
var len = arr.length / 2;
if (len < 1) { return arr }

// the following avoids stepping one too deep into the recursion as well
if (len === 1) { // if array sizes 1 then skip the merge
return arr[0] < arr[1] ? [arr[0], arr[1]] : [arr[1],arr[0]];
}

return merge(mergeSort(arr.slice(0, len)), mergeSort(arr.slice(len)));
}

Для итерационную функцию можно сопоставить предварительно объединены значения

var split = [];;
for(var i = 0; i < arr.length-1; i+= 2){
split.push(arr[i] < arr[i+1] ? [arr[i],arr[i+1]] : [arr[i+1],arr[i]] )
}
if(arr.length % 2) { splitArr.push([arr[arr.length -1]]) }


Реализация итерационного стека.

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

В splitArr заменяет вызов стека и кучи, и проводит объединенные массивы. Когда нет больше элементов, чтобы объединить в splitArr работа будет завершена.

Обратите внимание, оказывается, очередь быстрее, чем стек в данном случае, но идея та же

function mergeSortIterative(arr) {
const stack = [];
for (var i = 0; i < arr.length - 1; i+= 2) {
const ii = i + 1;
stack.push(arr[i] < arr[ii] ? [arr[i], arr[ii]] : [arr[ii], arr[i]] )
}
if (arr.length % 2) { stack.push([arr[arr.length -1]]) }

// the loop replaces the recursive function
while (stack.length > 1){
stack.push(merge(stack.shift(), stack.shift()));
}
return stack[0];
}

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

2
ответ дан 16 февраля 2018 в 10:02 Источник Поделиться