13

以下のような3つのソートされた配列があります 

[{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}]
[{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}]
[{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}]

これらの配列は、Array 内の各オブジェクトの name プロパティに基づいて並べ替えられます。これは、2つのソートされた配列をマージするために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;
}

これは、2 つの配列http://jsfiddle.net/euRn5/を使用した作業フィドルです。n個の配列で同じことを達成するための最良のアプローチは何ですか?私が現在考えているのは、1つずつ取り、最後のアイテムまで以前にマージしたものとマージすることです。これは最善のアプローチですか？

4

5 に答える 5

3

より高速で、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 remain only 1 array with unmerged 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()を使用すると効果的です。または、バイナリ ヒープを使用してnext.

于 2015-05-14T03:31:30.050 に答える
3

Update:

Seeing as it is current_year this would now be:

const mergeAll = (...arrays) => arrays.reduce(mergeSorted);

Original:

If you're feeling functional this is a perfect place to use reduce.

var mergeAll = function(){
    return Array.prototype.slice.call(arguments).reduce(mergeSorted);
};

example:

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/

于 2013-09-09T05:42:05.040 に答える
2

Exceptionそれを呼び出すことによって拡張された元のソリューションを反映するように編集mergeSorted(mergeSorted(a,b),c)されたのは、ここでの私のソリューションよりも高速です。

Javascript の組み込みソートは、すべての配列を連結して全体を一度にソートできるほど高速ではありません。Javascript は、下位レベルで行うべきことを再実装するのには適していません。

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"}]
于 2013-09-09T04:52:23.217 に答える