Effiziente Weise, die 5 größten Zahlen in einem Array in einem beliebigen Intervall zu finden

Question

Ich versuche, die fünf größten Zahlen in festgelegten Abständen zu finden, während auch diese Werte aus dem Array entfernen. Ich muss die Top-Kandidaten in ihrer jeweiligen Reichweite schnappen. Dieser Bereich kann sich ändern, und die Anzahl, die ich abfragen muss, kann sich ebenfalls ändern. Gibt es dafür eine effiziente und vorzugsweise elegante Lösung? Mit Eleganz meine ich einen algorithmischen (vorzugsweise Hashed) Ansatz, der ineffiziente Sortierungen oder Aktionen entfernt, die nicht zur Leistung auf spärlichen und großen Arrays beitragen.

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

I @ Kommentar jedoch le_m des gelesen habe, die k größten/kleinsten Gegenstände oder die k viertgrößte/kleinstes Element zu finden, ist eine komplizierte Aufgabe in O (n). Es wird am besten in die Sortierung und Aufnahme der notwendigen vom Anfang des Arrays implementiert.

Dementsprechend können Sie wie folgt vorgehen;

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; }

Ok wie pro Leistung Bedenken des OP auf V8 ich den Code repharsed haben .reduce() die V8 viel schneller zu bedienen als .map(). Hier ist der modifizierte Code.

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; }