javascript - Parcurgerea unui array și eliminarea elementelor, fără a întrerupe bucla for

Am următorul for loop, și când folosesc splice() pentru a elimina un element, apoi primesc că 'seconds' este nedefinit. Aș putea verifica dacă este nedefinit, dar simt că probabil există o modalitate mai elegantă de a face acest lucru. Dorința este pur și simplu să șterg un element și să continui.

for (i = 0, len = Auction.auctions.length; i < len; i++) {
    auction = Auction.auctions[i];
    Auction.auctions[i]['seconds'] --;
    if (auction.seconds < 0) { 
        Auction.auctions.splice(i, 1);
    }           
}

Răspuns #1

Array-ul este reindexat atunci când folosiți un .splice(), ceea ce înseamnă că veți sări peste un index atunci când unul este eliminat, iar .length păstrat în cache este depășit.

Pentru a-l rezolva, ai nevoie fie să decrementezi i după un .splice(), fie să iterezi pur și simplu invers...

var i = Auction.auctions.length
while (i--) {
    ...
    if (...) { 
        Auction.auctions.splice(i, 1);
    } 
}

În acest fel, reindexarea nu afectează următorul element din iterație, deoarece indexarea afectează doar elementele de la punctul curent până la sfârșitul Array-ului, iar următorul element din iterație este mai mic decât punctul curent.

Răspunsul #2

Aceasta este o problemă destul de comună. Soluția este să buclați înapoi:

for (var i = Auction.auctions.length - 1; i >= 0; i--) {
    Auction.auctions[i].seconds--;
    if (Auction.auctions[i].seconds < 0) { 
        Auction.auctions.splice(i, 1);
    }
}

Nu contează dacă le scoți de la capăt, pentru că indicii vor fi păstrați pe măsură ce mergi înapoi.

Răspunsul #3

Recalculează lungimea de fiecare dată în buclă în loc să o faci doar la început, de exemplu:

for (i = 0; i < Auction.auctions.length; i++) {
      auction = Auction.auctions[i];
      Auction.auctions[i]['seconds'] --;
      if (auction.seconds < 0) { 
          Auction.auctions.splice(i, 1);
          i--; //decrement
      }
}

În felul acesta nu vei depăși limitele.

EDIT: am adăugat o decrementare în instrucțiunea if.

Răspunsul #4

Deși întrebarea ta este despre ștergerea elementelor din tabloul pe care se iterează și nu despre eliminarea elementelor (în plus față de alte procese) în mod eficient, cred că ar trebui să o reconsideri dacă te afli într-o situație similară.

Complexitatea algoritmică a acestei abordări este O(n^2), deoarece funcția splice și bucla for iteră ambele peste array (funcția splice mută toate elementele array-ului în cel mai rău caz). În schimb, poți doar să adaugi elementele necesare în noul array și apoi să atribui acel array variabilei dorite (care tocmai a fost parcursă).

var newArray = [];
for (var i = 0, len = Auction.auctions.length; i < len; i++) {
    auction = Auction.auctions[i];
    auction.seconds--;
    if (!auction.seconds < 0) { 
        newArray.push(auction);
    }
}
Auction.auctions = newArray;

De la ES2015 putem folosi Array.prototype.filter pentru a pune totul pe un singur rând:

Auction.auctions = Auction.auctions.filter(auction => --auction.seconds >= 0);

Răspunsul #5

Auction.auctions = Auction.auctions.filter(function(el) {
  return --el["seconds"] > 0;
});

Răspunsul #6

Dacă folosești ES6+ - de ce să nu folosești pur și simplu metoda Array.filter?

Auction.auctions = Auction.auctions.filter((auction) => {
  auction['seconds'] --;
  return (auction.seconds > 0)
})  

Rețineți că modificarea elementului din matrice în timpul iterării cu filter funcționează doar pentru obiecte și nu va funcționa pentru matricea de valori primitive.

Răspunsul #7

Iată o soluție simplă în timp liniar pentru această problemă simplă în timp liniar.

Când rulez acest fragment, cu n=1 milion, fiecare apel la filterInPlace() durează între 0,013 și 0,016 secunde. O soluție cvadratică (de exemplu, răspunsul acceptat) ar lua de un milion de ori mai mult, sau cam așa.

// Remove from array every item such that !condition(item).
function filterInPlace(array, condition) {
   var iOut = 0;
   for (var i = 0; i < array.length; i++)
     if (condition(array[i]))
       array[iOut++] = array[i];
   array.length = iOut;
}

// Try it out.  A quadratic solution would take a very long time.
var n = 1*1000*1000;
console.log("constructing array...");
var Auction = {auctions: []};
for (var i = 0; i < n; ++i) {
  Auction.auctions.push({seconds:1});
  Auction.auctions.push({seconds:2});
  Auction.auctions.push({seconds:0});
}
console.log("array length should be "+(3*n)+": ", Auction.auctions.length);
filterInPlace(Auction.auctions, auction => --auction.seconds >= 0);
console.log("array length should be "+(2*n)+": ", Auction.auctions.length);
filterInPlace(Auction.auctions, auction => --auction.seconds >= 0);
console.log("array length should be "+n+": ", Auction.auctions.length);
filterInPlace(Auction.auctions, auction => --auction.seconds >= 0);
console.log("array length should be 0: ", Auction.auctions.length);

Rețineți că aceasta modifică array-ul original pe loc, mai degrabă decât să creeze un array nou; a face asta pe loc poate fi avantajos, de exemplu în cazul în care array-ul este unicul blocaj de memorie al programului; în acel caz, nu doriți să creați un alt array de aceeași dimensiune, chiar și temporar.

Răspuns #8

Bucla for normală îmi este mai familiară, trebuie doar să decrement indicele de fiecare dată când elimin un element din array

//5 trues , 5 falses
var arr1 = [false, false, true, true, false, true, false, true, true, false];

//remove falses from array
for (var i = 0; i < arr1.length; i++){
    if (arr1[i] === false){
        arr1.splice(i, 1);
        i--;// decrement index if item is removed
    }
}
console.log(arr1);// should be 5 trues

Răspuns #9

O altă soluție simplă pentru a parcurge o dată elementele unui array:

while(Auction.auctions.length){
    // From first to last...
    var auction = Auction.auctions.shift();
    // From last to first...
    var auction = Auction.auctions.pop();

    // Do stuff with auction
}