任意の所定の間隔でアレイ内の5つの最大値を見つける効率的方法

Question

設定間隔で5つの最大値を見つけようとしていますが、配列からこれらの値を削除しています。私は彼らのそれぞれの範囲でトップ候補をつかむ必要があります。その範囲は変わる可能性があり、照会する必要のある番号も変更することができます。これには効率的で優雅な解決策がありますか？優雅さとは、非効率なソートや、疎な配列や大規模な配列のパフォーマンスに寄与しないアクションを取り除く、アルゴリズム（好ましくはハッシュ）手法を意味します。

var arr = [101, 88, 267, 175, 154, 39, 74, 217, 31, 105, 235, 31, 14, 49, 226, 195, 134, 207, 222, 281, 
 
    262, 112, 133, 115, 0, 53, 128, 103, 88, 145, 238, 13, 204, 199, 100, 247, 292, 157, 141, 286, 
 
    72, 160, 85, 61, 57, 54, 263, 50, 125, 179, 243, 281, 39, 76, 151, 79, 1, 238, 200, 249, 35, 82, 
 
    204, 174, 293, 216, 84, 209, 170, 236, 3, 247, 25, 162, 25, 57, 49, 215, 8, 167, 180, 268, 
 
    204, 257, 134, 151, 191, 81, 77, 106, 85, 128, 52, 136, 46, 185, 229, 116, 145, 253, 258, 222, 
 
    269, 225, 101, 175, 265, 77, 32, 8, 72, 54, 111, 264, 292, 161, 91, 215, 139, 245, 73, 127, 297, 
 
    73, 258, 183, 232, 55, 199, 175, 31, 24, 21, 155, 231, 95, 40, 223, 222, 86, 115, 210, 134, 229, 
 
    211, 54, 294, 153, 52, 165, 168, 125,186, 185, 289, 188, 248, 61, 136, 15, 19, 92, 200, 80, 208, 
 
    195, 241, 85, 288, 279, 119, 247, 208, 11, 80, 111, 29, 292, 222, 289, 70, 11, 209, 25, 267, 233, 
 
    16, 289, 154, 141, 174, 30, 156, 40, 266, 139, 116, 241, 1, 101, 109, 61, 220, 265, 45, 178, 166, 
 
    102, 181, 193, 202, 133, 200, 266, 114, 222, 231, 89, 190, 29, 20, 64, 233, 261,213, 40, 161, 167, 
 
    100, 121, 288, 268, 50, 264, 78, 105, 21, 33, 79, 114, 5, 134, 56, 259, 124, 44, 134, 133, 74, 176, 
 
    65, 68, 34, 56, 2, 287, 63, 167, 299, 59, 290, 241, 104, 75, 76, 116, 225, 297, 208, 136, 265, 290, 
 
    170, 267, 10, 176, 141, 217, 195, 4, 173, 32, 150, 271, 238, 171, 195, 16, 282, 77, 62, 39, 44, 248, 
 
    270, 222, 295, 122, 190, 230]; 
 
function maxAtIntervals (intervalLength, select, xs) { 
 
    const comparator = (a, b, _) => a - b; 
 
    const temp = []; 
 
    for (var i = 0; i < xs.length; i += intervalLength) { 
 
     const interval = xs.slice(i, i + intervalLength); 
 
     temp.push(interval.sort(comparator).slice(-select)); 
 
    } 
 

 
    return temp; 
 
} 
 
console.log(maxAtIntervals(20, 5, arr));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 1

しかし私は、k最大/最小のアイテムまたはk番目の最大/最小のアイテムを見つけるle_mさんのコメント@読みましたO（n）の中に複雑な作業です。これは、配列の先頭から必要な配列をソートして取り込むのが最適です。

したがって、次のようにすることができます。私はV8で.map()よりもはるかに高速である.reduce()を使用するコードをrepharsedているV8のOPのパフォーマンス上の問題ごとに[OK]を

function segmentAndTakeMax(ar,sl,mc) { // array , segment length, max count 
 
    var tempar = Array.from({length: sl}); 
 
    return Array.from({length: Math.ceil(ar.length/sl)}) 
 
       .map((_,i) => tempar.map((_,j) => arr[i*sl+j]) 
 
            .sort((a,b) => b-a) 
 
            .slice(0,Math.min(arr.length-i*sl,mc))); 
 
} 
 

 
var arr = Array.from(new Array(203), _ => ~~(Math.random()*100)); 
 
console.log(arr); 
 
console.log(segmentAndTakeMax(arr,20,5));

.as-console-wrapper { max-height: 100% !important; top: 0; }

。ここに変更されたコードがあります。

function segmentAndTakeMax(arr, n, m) { 
 
    var li = arr.length-1; // last index 
 
    return arr.reduce((r,e,i,a) => i%n ? (r[r.length-1].push(e),             // if i%n != 0 then do these -> push e to last sub array 
 
             i == li && (r[r.length-1] = r[r.length-1].sort((a,b) => b-a).slice(0,m)), // short circuit for if i == last index then sort and slice the last sub array 
 
             r)                  // return r 
 
            : (i && (r[r.length-1] = r[r.length-1].sort((a,b) => b-a).slice(0,m)),  // if i%n == 0 then do these -> short circuit for if i != 0 then sort and slice the last sub array 
 
             r.push([e]),                // push [e] (a new sub array) to r 
 
             r), []);                 // return r 
 
} 
 

 
var arr = Array.from(new Array(203), _ => ~~(Math.random()*100)); 
 
console.log(arr); 
 
console.log(segmentAndTakeMax(arr,20,5));

.as-console-wrapper { max-height: 100% !important; top: 0; }