Как объединить отсортированные массивы в JavaScript
У меня есть три отсортированных массива, например ниже
[{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}]
[{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}]
[{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}]
Эти массивы сортируются на основе свойства имени каждого объекта в массиве. Вот метод, который я преобразовал из Java, чтобы объединить два отсортированных массива
function mergeSorted(a, b) {
var answer = new Array(a.length + b.length), i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
if (a[i].name < b[j].name) {
answer[k] = a[i];
i++;
}else {
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length) {
answer[k] = a[i];
i++;
k++;
}
while (j < b.length) {
answer[k] = b[j];
j++;
k++;
}
return answer;
}
Вот рабочая скрипка с двумя массивами http://jsfiddle.net/euRn5/. Каков наилучший подход для достижения такого же числа с n количеством массивов, мысль, которую я имею в виду в настоящее время, берет один за другим, объединять ее с ранее объединенным до последнего элемента, например n + = i. Это лучший подход?
Ответы
Ответ 1
Обновление:
Увидев, что это current_year, теперь это будет:
const mergeAll = (...arrays) => arrays.reduce(mergeSorted);
Оригинал:
Если вы чувствуете себя функционально, это идеальное место для использования сокращения.
var mergeAll = function(){
return Array.prototype.slice.call(arguments).reduce(mergeSorted);
};
Пример:
var a = [{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}];
var b = [{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}];
var c = [{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}];
console.log(mergeAll(a,b,c).map(function(x){return x.name;}));
jsfiddle: http://jsfiddle.net/FeT6m/
Ответ 2
Стандартный и самый понятный код, который я считаю.
function mergeArray(arr1, arr2) {
var new_array = [];
var i = 0,
j = 0,
index = 0;
while (new_array.length != (arr1.length + arr2.length) - 1) {
if (arr1[i] < arr2[j]) {
new_array.push(arr1[i]);
i++;
} else {
new_array.push(arr2[j]);
j++;
}
}
return new_array;
}
Вызов функции:
var merged_array = mergeArray([1,6,9,95], [2,7,10,11,14,18]);
Ответ 3
Отредактировано, чтобы отразить это оригинальное решение Exception, расширенное, называя его как mergeSorted(mergeSorted(a,b),c) быстрее, чем мое решение здесь.
Javascript builtin sort [недостаточно], чтобы вы могли просто объединить все массивы вместе и отсортировать всю вещь за один раз. Javascript not хорош для повторной реализации вещей, которые должны выполняться на более низком уровне.
var a1 = [{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}]
var a2 = [{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}]
var a3 = [{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}]
a1.concat(a2,a3).sort(function(a,b){return (a.name>b.name)-(a.name<b.name)})
// [{name:"a"}, {name:"a"}, {name:"b"}, {name:"e"}, {name:"h"}, {name:"i"}, {name:"g"}, {name:"m"}, {name:"m"}, {name:"n"}, {name:"o"}, {name:"x"}]
Ответ 4
Нативные реализации не всегда бывают самыми быстрыми (как вы могли заметить), и исторически они были несколько вялыми из-за обширной проверки ошибок. Тем не менее, в будущем могут быть улучшения производительности благодаря более надежной интеграции с аппаратными средствами или программами, специально созданными для оптимизации определенных задач. Если вы напишете свой собственный код, ваше приложение не сможет воспользоваться преимуществами повышения производительности после их реализации. Вам решать, где лежат преимущества и каковы риски.
Во всяком случае, я написал более красивую версию вашего оптимизированного кода для funsies:
function mergeSorted(a,b){
var alen = a.length
, blen = b.length
, i, j, k = j = i = 0
, answer = new Array(alen + blen)
;//var
while(i < alen && j < blen)
answer[k++] = a[i].name < b[j].name ? a[i++] : b[j++];
while(i < alen) answer[k++] = a[i++];
while(j < blen) answer[k++] = b[j++];
return answer;
}
Ответ 5
Быстрее, слияния всего за 1 проход, с большей гибкостью (keepDuplicates, пользовательский компаратор):
/* mergeSortedArrays(arrays[, keepDuplicates[, comparator[, thisArg]]])
Merges multiple sorted arrays into a new sorted array.
Arguments:
- arrays: array of sorted arrays to be merged
- keepDuplicates (optional): (true/false) whether to keep duplicate values
Default: false
- comparator (optional): function used to compare values
Default: sort numbers in ascending order
Example comparator: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
- thisArg (optional): comparator is bound to thisArg when invoked
Returns: a new sorted array containing all the values from the arrays
*/
function mergeSortedArrays(arrays, keepDuplicates, comparator, thisArg) {
// Coerce to boolean to speed up testings in some javascript engines:
keepDuplicates = !!keepDuplicates;
// By default, sort numbers in ascending order:
if(!comparator) comparator = function(a, b) { return a - b; };
var nb = arrays.length, // Number of arrays to be merged
iter = new Array(nb), // Current position of iteration of each array
next = [], // Keep each array sorted by the value of their next element
length = 0; // The combined length of all arrays
// Populate iter and next:
for(var i = 0, arr; i < nb; i++) {
arr = arrays[i];
iter[i] = 0;
if(arr.length > 0) {
insertNextIndex(next, i, arr[0], comparator, thisArg);
}
length += arr.length;
}
// Insert index of array into next:
function insertNextIndex(next, index, val, comparator, thisArg) {
var i = next.length;
while(i--) { // Reverse loop...
var j = next[i];
if(comparator.call(thisArg, arrays[j][iter[j]], val) >= 0) { // ...until we find a greater value
break;
}
}
next.splice(i + 1, 0, index);
}
var merged = keepDuplicates ? new Array(length) : [],
k = 0, // Iterate over merged
min, val, lastVal;
// First iteration to get a value for lastVal (for duplicate checks):
if(!keepDuplicates && next.length > 0) {
min = next.pop();
arr = arrays[min];
i = iter[min]++;
val = arr[i];
merged[k++] = val;
lastVal = val;
if(++i < arr.length) { // If available, insert next value in next:
insertNextIndex(next, min, arr[i], comparator, thisArg);
}
}
// Merge multiple arrays:
while(next.length > 1) { // While there is still multiple arrays to be merged
min = next.pop();
arr = arrays[min];
i = iter[min]++;
val = arr[i];
if(keepDuplicates || comparator.call(thisArg, lastVal, val) !== 0) {
merged[k++] = val;
lastVal = val;
}
if(++i < arr.length) { // If available, insert next value in next:
insertNextIndex(next, min, arr[i], comparator, thisArg);
}
}
// When there is only 1 array left with values, use a faster loop:
if(next.length > 0) {
arr = arrays[next[0]];
i = iter[next[0]];
length = arr.length;
while(i < length) { // To the end
val = arr[i++];
if(keepDuplicates || comparator.call(thisArg, lastVal, val) !== 0) {
merged[k++] = val;
lastVal = val;
}
}
}
return merged;
}
Слияние за 1 проход устраняет создание промежуточных массивов, требующих времени и памяти. Кроме того, количество сравнений красиво уменьшается путем сохранения отсортированного списка следующего элемента из каждого массива (см. Массив next). И когда размеры массива известны, они предварительно выделены для предотвращения динамических перераспределений (хотя это будет зависеть от вашего механизма javascript).
В вашем случае я бы назвал это следующим образом:
mergeSortedArrays(arrays, true, function(a, b) {
return a.name < b.name ? -1 : 1;
});
Примечание. Если у вас есть большое количество массивов, вы можете использовать двоичный поиск вместо линейного поиска в insertNextIndex(). Или использовать Binary Heap для next.
