js順序配列接続の問題_javascriptスキル

1. はじめに

昨日、順序付けされた配列の接続の問題を解決する方法に関する問題に遭遇しました。これは非常に一般的な問題です。ただし、接続される配列はすべて順序付けされており、これは非常に重要な前提条件であるため、ここではコードの効率を考慮する必要があります。

2. シンプルだが非効率なアルゴリズム

私が最初に考えたのは、組み込みの concat メソッドを使用して並べ替えることでした。このメソッドは、配列が順序付けされているという前提条件を考慮していません。コードは次のとおりです。

コードをコピー コードは次のとおりです。

function concatSort(arrA,arrB){
return arrA.concat(arrB).sort();
}

ソートにどのようなアルゴリズムが使用されているかを理解するために、特に V8 エンジン (

Connection) のアルゴリズムを調べました。これは、おそらく配列の長さが短い場合、挿入ソートが行われることを意味します。を使用する(InsertionSort)が、配列の長さが長い場合にはクイックソート(QuickSort)が使用されます。私は長い間、そのようなものはバブリングを使用すると思っていましたが、その誤解を正しました。

3. 小さな値を挿入する方法

一般的な考え方は、2 つの配列を同時に走査し、2 つのフラグ (i, j) を設定して走査位置を記録し、2 つの配列の小さい方の値を新しい配列に挿入してから、次へ進むフラグを設定することです。 1 つの位置を選択し、検索値が配列に挿入されるまで比較を繰り返します。初めてやったときは判定条件を間違って書いたために無限ループが発生し、自分のアルゴリズムの能力が露呈してしまいました。

コードをコピー コードは次のとおりです。

function con(arrA, arrB){
var i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA lenB,result = []
for(i=0,j=0,k =0; k if(i = lenB || arrA[i] result.push(arrA[i ]);
}else{
result.push(arrB[j]) [3,5,6,7,10]; //[1 、2、3、4、5、6、7、10]



このアルゴリズムのパフォーマンスを jsperf の上記の方法 1 と比較すると、2 番目のアルゴリズムの効率が最初のアルゴリズムよりも大幅に優れていることがわかりました。信じられない場合は、
ここ
をクリックしてください。

4. 問題をアップグレードします。結合する配列の数を増やします。

配列の数を増やすと、たとえば A = [1,5]、B = [2,6] になります。 、C = [ 3,4]....K = [....]、マージされた配列を見つけます。

この質問をされたときの第一印象は、「マージ アルゴリズム」によく似ているというものでしたが、マージ アルゴリズムを使用する場合、配列が順序付けされているという前提条件は必要ありません。そこでヒープソートやクイックソートなどのアルゴリズムを考えましたが、配列の順序付けという前提条件が有効に使えないことが分かり、結局諦めました。インタビューの後、私は長い間考えましたが、この問題を効率的に解決する方法がわかりませんでした。寮に戻ろうとしたとき、後輩が「また休みだ」と言って起こしてくれました。 コードは次のとおりです。

コードをコピー

コードは次のとおりです:

function conMore(){
var innerArr = [], i ,len = argument.length , result = [];
for(i = 0 ; i innerArr.push(arguments[i]);
}
if(result.length === 0){
result = innerArr[0];
}
for(i=1 ;i< len; i ){
result = con(result,outerArr[i]);
}
結果を返します。
}
function con(arrA,arrB){
var i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA lenB,result = [];
for(i=0,j=0,k =0; k if(i = lenB || arrA[i] result.push(arrA[i ]); 
}else{
result.push(arrB[j ]);
}
}
結果を返します。
}
var a = [1,4,7]、b = [2,5,8]、c = [3,6,9,10];
console.log(conMore(a,b,c));   //[1,2,3,4,5,6,7,8,9,10]

もう一度 jsperf 代のパフォーマンスを使用して検査分析を実行し、結果を猛击 里 .