[repne scasb]

Originariamente inviato da yorkeiser

Interessante in termini di velocità, ma ti mostro con un semplice output grafico...[CUT]

Ottima osservazione, c'e' pero' da considerare che il limite da te giustamente notato, non sta nell'algoritmo di "mix classico", ma nella 'rand()' in quanto l'output di rand() e' distribuito su RAND_MAX e non su TABLE_LEN. Riscrivendo la funzione rand() con RAND_MAX==TABLE_LEN, l'inconveniente da te menzionato verrebbe assai ridotto (non eliminato(NOTA 1)). Tanto piu' TABLE_LEN differisce da RAND_MAX tanto piu' e' vera la tua osservazione (a causa di rand()).

E' anche utile ricordare che la funzione rand() disponibile per alcuni compilatori C non "brilla" per la capacita' di distribuire in modo uniforme il proprio output e differisce da compilatore a compilatore (meglio da libreria a libreria), per esempio compilando il mio esempio con il Watcom C, ottengo risultati meno negativi da quelli da te riportati.

Per correggere tale comportamento "non ottimale" della funzione rand() e' necessario modificare nel mio codice la seguente riga come segue:

	for(i=0;i<TABLE_LEN*K;i++)

K e' un fattore che dipende dalla bonta' della funzione rand() e da quanto TALBLE_LEN differisce da RAND_MAX, in linea puramente teorica vale 1.

NOTA 1: Ineliminabile in quanto estraendo a caso (nella tombola vera), la probabilita' che l'ennesimo numero estratto sia proprio 'n' e' diversa da zero.

NOTA 2: Con TABLE_LEN==90 ed una funzione rand di media qualita', con K=3 il problema non "dovrebbe" presentarsi.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TABLE_LEN 90
#define K 3

void main(void)

{
    int i,j,k,tmp_val,table_n[TABLE_LEN];
    time_t t;

    srand((unsigned)time(&t));

    for(i=0;i<TABLE_LEN;i++)
	table_n[i]=i+1;

    for(i=0;i<TABLE_LEN*K;i++)
    {
	j=(double)rand()*TABLE_LEN/(RAND_MAX+1);
	k=(double)rand()*TABLE_LEN/(RAND_MAX+1);	
	tmp_val=table_n[j];
	table_n[j]=table_n[k];
	table_n[k]=tmp_val; 	
    }

    for(i=0;i<TABLE_LEN;i++)
	printf("%2d %2d %s\n",i+1,table_n[i],table_n[i]==i+1?"<*************":"");
}