Optimización: Escoger un elemento aleatorio de un array no escogido ya

[derkenuke]

Hola alvlin, gracias por responder.

En IE también me da fallo, creo que es por no definir el indexOf para arrays. En FF no me ha dado ningún error O_o, no sabía que estuviera implementado...

Bueno, lo he definido así con tu permiso:

Código PHP:

  Array.prototype.indexOf = function(x) {
    for(var i=0, l=this.length; i<l; i++)
        if( x === this[i] ) return true;
    return -1;
} 
   

Dime si lo definirías más eficientemente.

Mi forma bruta sería algo parecida. Tendría un número de escogidos (tu equivalente a yaElegidos.length) y un array de la misma longitud que miArray, que sólo almacenaría 1 en la posición i en caso de haber escogido ya la posición i en el original miArray.

Por otra parte he hecho miArray unas cuantas veces más largo... He utilizado este ejemplo (con medida de tiempo incluída):

Código PHP:

  var miArray = ['flgo', 20, 'pgre', 22, 13, 8, 16, 'frkiysoj', 9, Infinity, 11, 14, true, 'bstuhcv', 'bhatnck', 7, 17, 'nusfgcvd', 19, 21, 'gmwp', 'incauo', 'hqu', { color: "rojo", forma: "cuadrado" }, 'kficoprn', 'qofxpdsn', 'ugdoebq', 'kxmhs', 3, 'bfce', 'neduh', 15, 'ueifchsj', 'kgdmj', 'ojk', 'vfqoyhli', 'buno', 18, 'nrkmf', 12, 6, 23, 'hnvroupj', 'gkdtnhq', document.body, 10, 'qghsfpdr', 24, 1, window.screen, undefined, null, 0, 'ewgmq', NaN, 4, function () { }, 2, 5, window.onload, void(0), -Infinity];
for(var i=0; i<5; i++)
    miArray = miArray.concat(miArray);
var largo = miArray.length;
Array.prototype.yaEscogido = new Array();
Array.prototype.escogidos = 0;
 
Array.prototype.elemNoEscogido = function() {
    if( this.escogidos < largo ) {
        var iAleat;
        do {
            iAleat = Math.floor( Math.random()*largo );
        } while( this.yaEscogido[iAleat] === 1 );
        this.yaEscogido[iAleat] = 1;
        this.escogidos++;
        return this[iAleat];
    }
    else {
        //reiniciando
        this.yaEscogido = new Array();
        this.escogidos = 0;
        return false;
    }
} 
// hago la medicion de tiempo 10 veces para hacer una media:
var tiempos = [];
for(var t=0; t<10; t++) {
    var ini = new Date().getTime();
    do {
        var elem = miArray.elemNoEscogido();
    } while(elem!==false);
    var fin = (new Date().getTime()-ini);
    tiempos.push(fin);
}
// hago la media de tiempos:
var tardanza = eval( "("+tiempos.join("+")+") / "+ tiempos.length )
document.write("Tiempos: "+tiempos+" --> Tiempo medio: "+tardanza); 
   

Bajo win y FF me da unos tiempos, por ejemplo, de
Tiempos: 170,281,120,250,251,140,260,130,251,290 --> Tiempo medio: 214.3

He intentado hacer una prueba similar con tu código:

Código PHP:

  var miArray = ['flgo', 20, 'pgre', 22, 13, 8, 16, 'frkiysoj', 9, Infinity, 11, 14, true, 'bstuhcv', 'bhatnck', 7, 17, 'nusfgcvd', 19, 21, 'gmwp', 'incauo', 'hqu', { color: "rojo", forma: "cuadrado" }, 'kficoprn', 'qofxpdsn', 'ugdoebq', 'kxmhs', 3, 'bfce', 'neduh', 15, 'ueifchsj', 'kgdmj', 'ojk', 'vfqoyhli', 'buno', 18, 'nrkmf', 12, 6, 23, 'hnvroupj', 'gkdtnhq', document.body, 10, 'qghsfpdr', 24, 1, window.screen, undefined, null, 0, 'ewgmq', NaN, 4, function () { }, 2, 5, window.onload, void(0), -Infinity];
for(var i=0; i<4; i++)
    miArray = miArray.concat(miArray);
var yaElegidos = []; 
var largo = miArray.length;
 
Array.prototype.indexOf = function(x) {
    for(var i=0, l=this.length; i<l; i++)
        if( x === this[i] ) return true;
    return -1;
}
 
function dameElemento() {
    largoElegidos = yaElegidos.length;
    if ( largoElegidos < largo ) {
        // termina con 'indice' siendo un índice de la matriz que todavía no fue elegido.
        while ( yaElegidos.indexOf(indice = Math.floor( Math.random() * largo )) !== -1 );
        yaElegidos[largoElegidos] = indice;
        return miArray[indice];
    }
    else {
        //reiniciando
        yaElegidos = new Array();
        return false;
    }
} 
 
 
// hago la medicion de tiempo 10 veces para hacer una media:
var tiempos = [];
for(var t=0; t<3; t++) {
    var ini = new Date().getTime();
    do {
        var elem = dameElemento();
    } while(elem!==false);
    var fin = (new Date().getTime()-ini);
    tiempos.push(fin);
}
// hago la media de tiempos:
var tardanza = eval( "("+tiempos.join("+")+") / "+ tiempos.length )
document.write("Tiempos: "+tiempos+" --> Tiempo medio: "+tardanza); 
   

Y, teniendo en cuenta que el array ha sido multiplicado por 4 en vez de por 5 que yo puse, la salida que he obtenido en las mismas condiciones es:
Tiempos: 3465,2744,3295 --> Tiempo medio: 3168



Así que no sé si lo estoy haciendo bien... pero la intuición me dice que sí (hay un for dentro de un while y...)



Ya tengo preparada la siguiente idea, pero a ver si a alguien se le ocurren más maneras...


Un saludo