Skip to content

Prestazioni degli insiemi e degli array in Javascript

Vi diamo la risposta a questo problema, almeno lo speriamo. Se hai ancora domande, diccelo, senza pensarci

Soluzione:

Ok, ho testato l'aggiunta, l'iterazione e la rimozione di elementi da un array e da un insieme. Ho eseguito un test "piccolo", utilizzando 10 000 elementi e un test "grande", utilizzando 100 000 elementi. Ecco i risultati.

Aggiunta di elementi a un insieme

Sembrerebbe che l'elemento .push sia circa 4 volte più veloce del metodo .add indipendentemente dal numero di elementi aggiunti.

Iterazione e modifica degli elementi di una collezione

Per questa parte del test ho utilizzato un metodo for per iterare sull'array e un ciclo for of per iterare sull'insieme. Anche in questo caso, l'iterazione sull'array è stata più veloce. Questa volta sembra che lo sia in modo esponenziale, poiché ha richiesto il doppio del tempo durante i test "piccoli" e quasi il quadruplo durante i test "grandi".

Rimozione di elementi da un insieme

Qui il discorso si fa interessante. Ho usato una combinazione di elementi for e .splice per rimuovere alcuni elementi dall'array e ho usato for of e .delete per rimuovere alcuni elementi dall'insieme. Per i test "piccoli", la rimozione degli elementi dall'insieme è stata circa tre volte più veloce (2,6 ms contro 7,1 ms), ma le cose sono cambiate drasticamente per il test "grande", dove sono stati necessari 1955,1 ms per rimuovere gli elementi dall'array, mentre sono stati necessari solo 83,6 ms per rimuoverli dall'insieme, 23 volte più velocemente.

Conclusioni

Con 10k elementi, entrambi i test hanno avuto tempi comparabili (array: 16,6 ms, set: 20,7 ms), ma quando si è trattato di 100k elementi, il set è stato il chiaro vincitore (array: 1974,8 ms, set: 83,6 ms), ma solo a causa dell'operazione di rimozione. Per il resto, l'array era più veloce. Non saprei dire esattamente perché.

Ho giocato con alcuni scenari ibridi in cui un array veniva creato e popolato e poi convertito in un set in cui alcuni elementi venivano rimossi, il set veniva poi riconvertito in un array. Anche se questa operazione offre prestazioni molto migliori rispetto alla rimozione degli elementi dell'array, il tempo di elaborazione aggiuntivo necessario per il trasferimento da e verso un set supera i vantaggi del popolamento di un array invece che di un set. Alla fine, è più veloce gestire solo un insieme. Tuttavia, è un'idea interessante: se si sceglie di utilizzare un array come raccolta dati per alcuni grandi dati che non hanno duplicati, potrebbe essere vantaggioso in termini di prestazioni, se mai ci fosse la necessità di rimuovere molti elementi in un'unica operazione, convertire l'array in un insieme, eseguire l'operazione di rimozione e convertire nuovamente l'insieme in un array.

Codice della matrice:

var timer = function(name) {
  var start = new Date();
  return {
    stop: function() {
      var end = new Date();
      var time = end.getTime() - start.getTime();
      console.log('Timer:', name, 'finished in', time, 'ms');
    }
  }
};

var getRandom = function(min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH', 'JOHNSON', 'WILLIAMS', 'JONES', 'BROWN', 'DAVIS', 'MILLER', 'WILSON', 'MOORE', 'TAYLOR', 'ANDERSON', 'THOMAS'];

var genLastName = function() {
  var index = Math.round(getRandom(0, lastNames.length - 1));
  return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
  var index = Math.round(getRandom(0, sex.length - 1));
  return sex[index];
};

var Person = function() {
  this.name = genLastName();
  this.age = Math.round(getRandom(0, 100))
  this.sex = "Male"
};

var genPersons = function() {
  for (var i = 0; i < 100000; i++)
    personArray.push(new Person());
};

var changeSex = function() {
  for (var i = 0; i < personArray.length; i++) {
    personArray[i].sex = genSex();
  }
};

var deleteMale = function() {
  for (var i = 0; i < personArray.length; i++) {
    if (personArray[i].sex === "Male") {
      personArray.splice(i, 1)
      i--
    }
  }
};

var t = timer("Array");

var personArray = [];

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personArray.length + " persons.")

Codice dell'insieme:

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

var getRandom = function (min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH','JOHNSON','WILLIAMS','JONES','BROWN','DAVIS','MILLER','WILSON','MOORE','TAYLOR','ANDERSON','THOMAS'];

var genLastName = function() {
    var index = Math.round(getRandom(0, lastNames.length - 1));
    return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
    var index = Math.round(getRandom(0, sex.length - 1));
    return sex[index];
};

var Person = function() {
	this.name = genLastName();
	this.age = Math.round(getRandom(0,100))
	this.sex = "Male"
};

var genPersons = function() {
for (var i = 0; i < 100000; i++)
	personSet.add(new Person());
};

var changeSex = function() {
	for (var key of personSet) {
		key.sex = genSex();
	}
};

var deleteMale = function() {
	for (var key of personSet) {
		if (key.sex === "Male") {
			personSet.delete(key)
		}
	}
};

var t = timer("Set");

var personSet = new Set();

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personSet.size + " persons.")

OSSERVAZIONI:

  • Le operazioni di set possono essere intese come istantanee all'interno del flusso di esecuzione.
  • Non siamo di fronte a un sostituto definitivo.
  • Gli elementi di un Classe di insiemi non hanno indici accessibili.
  • Imposta classe è un classe Array utile in quegli scenari in cui è necessario memorizzare un insieme su cui applicare l'addizione di base,
    cancellazione, controllo e iterazione.

Condivido alcuni test sulle prestazioni. Provate ad aprire la vostra console e a copiare il codice qui sotto.

Creazione di un array (125000)

var n = 125000;
var arr = Array.apply( null, Array( n ) ).map( ( x, i ) => i );
console.info( arr.length ); // 125000

1. Individuazione di un indice

Abbiamo confrontato il metodo has di Set con Array indexOf:

Array/indexOf (0,281ms) | Imposta/ha (0,053 ms)

// Helpers
var checkArr = ( arr, item ) => arr.indexOf( item ) !== -1;
var checkSet = ( set, item ) => set.has( item );

// Vars
var set, result;

console.time( 'timeTest' );
result = checkArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
checkSet( set, 123123 );
console.timeEnd( 'timeTest' );

2. Aggiunta di un nuovo elemento

Confrontiamo i metodi add e push degli oggetti Set e Array rispettivamente:

Array/push (1,612ms) | Set/aggiungere (0,006ms)

console.time( 'timeTest' );
arr.push( n + 1 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.add( n + 1 );
console.timeEnd( 'timeTest' );

console.info( arr.length ); // 125001
console.info( set.size ); // 125001

3. Eliminazione di un elemento

Quando si eliminano elementi, occorre tenere presente che Array e Set non partono in condizioni uguali. Array non ha un metodo nativo, quindi è necessaria una funzione esterna.

Array/deleteFromArr (0,356ms) | Set/rimuovere (0,019 ms)

var deleteFromArr = ( arr, item ) => {
    var i = arr.indexOf( item );
    i !== -1 && arr.splice( i, 1 );
};

console.time( 'timeTest' );
deleteFromArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.delete( 123123 );
console.timeEnd( 'timeTest' );

Leggete l'articolo completo qui

La mia osservazione è che un set è sempre meglio, tenendo conto di due insidie per gli array di grandi dimensioni:

a) La creazione di insiemi da array deve essere fatta in un ambiente for con una lunghezza precostituita.

lento (ad esempio 18 ms)new Set(largeArray)

veloce (ad es. 6 ms)const SET = new Set();
const L = largeArray.length;
for(var i = 0; i

b) L'iterazione potrebbe essere eseguita allo stesso modo, perché è anche più veloce di un metodo for of ciclo ...

Vedere https://jsfiddle.net/0j2gkae7/5/

per un confronto reale con
difference(), intersection(), union() e uniq() ( + i loro compagni di iterazione, ecc.) con 40.000 elementi

Apprezziamo che tu voglia stimolare la nostra occupazione pubblicando un commento e valutandolo, ti saremo eternamente grati.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.