Newsgroup: it.comp.java
Titolo: Ricerche in un array di byte e prestazioni

Salve a tutti.
Sto realizzando un programma in cui ad un certo punto mi occorre
eseguire una ricerca di un byte all'interno di un array di 256 byte.
Sulle prime ho risolto con un if innestato in un ciclo for. Vi scrivo il
pezzo di codice così forse son più chiaro:
byte[] alfa=new byte[256];
// in alfa non ci sono due byte uguali in tutto l'array (per progetto),
// ergo ci sono tutti i byte da 0 a 255, come la tabella ascii;
byte[] beta=new byte[1048576];
// in quest'altro array ci sono dati reali (ad esempio una frase) ed è
// sempre tutto pieno
int[] decode(alfa,beta){
int i=0;
int j=0;
int[] risposta= new int[1048576];
for(j=0;j<1048576;j++){
for(i=0;i<256;i++) {
	if(beta[j]==alfa[i]) {
		risposta[j]=i;
		break;
	}
}
}
return risposta;
}
Il problema di prestazioni che riscontro utilizzando questo algoritmo è
il fatto che per ogni byte contenuto in beta io debba eseguire 256 (se
son sfortunato!!) istruzioni rallentando molto il programma.
C'è un modo per velocizzare l'agoritmo che ho scritto, una specie di
comando Ritornami la posizione di byte[j] all'interno di alfa, così come
 accade per il seguente codice, ma per i byte?
String a="ciao";
int i=a.indexOf("o");
System.out.println(i);
Output:
3
Grazie per aver letto questo post e per ogni consiglio o suggerimento
che vorrete darmi!
WildEagle

  accade per il seguente codice, ma per i byte?
Crea una copia di alfa, ordinala (Arrays.sort(byte[] a)) poi usa 
Arrays.binarySearch(byte[] a, byte key) per ogni byte di beta nell'array 
alfa.
Pero' se spieghi meglio che cosa vuoi fare, magari c'e' una soluzione 
ancora piu' veloce :)

 ancora piu' veloce :)
Purtroppo questa soluzione non la posso prendere in considerazione
perché implica il sort sull'array alfa, che non posso fare.
alfa contiene in pratica tutti i byte da 0 a 255 cioè tutte le possibili
combinazioni di 8 bit. Se queste combinazioni sono messe ordinate in
modo crescente ottengo 0,1,2,...,255 cioè la tabella ascii del pc.
Generando casualmente i numeri da 0 a 255 e poi riempiendo con tali
numeri l'array alfa, controllando pure di non inserire elementi già
messi prima, ottengo una nuova tabella ascii non posizionale del tipo
243,45,87,0,4,21,...,32. In questo modo posso prendere in ingresso un
qualsiasi valore tra 0 e 255 e associarlo ad un unico valore della nuova
tabella alfa. L'operazione di codifica è molto veloce perché mi basta
sapere il i=valore decimale del singolo byte per ottenere l'alfa[i],
rappresentazione dello stesso byte nella nuova tabella ascii.
Il contrario è più lungo, perché devo cercare il valore alfa[i]
all'interno di alfa, in modo da sapere quanto vale i. E' evidente che
non posso ordinare alfa sennò perdo immediatamente l'associazione
posto-valore reale. Ad esempio, supponiamo che il 79esimo elemento di
alfa sia una 'A', cioè il valore 65 e che il valore da codificare sia
una O, cioè il valore 79: l'algoritmo cambierà la O in ingresso con una
A perché alfa[79]=65. Per tornare indietro devo sapere qual'è la
posizione della A nell'array alfa. Saputo questo (79esima) posso
ottenere il byte di partenza, la O appunto. E' quest'ultimo passaggio il
più lento perché devo contare da 0 a 255 e fare il confronto tra il
carattere in ingresso e quello che sta invece in alfa[i]. Non posso fare
il sort su alfa perché sennò la A dell'esempio che era in 79esima
posizione, si piazza in 65esima e la decodifica non è più possibile.
Spero di aver reso l'idea di quello che voglio fare e ringrazio chi
fosse arrivato a leggere tutto questo!
Ciao
WildEagle


--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 Ciao Nicola
N


 perché implica il sort sull'array alfa, che non posso fare.
Infatti ho scritto di fare una copia dell'array e tieni una tabella di 
conversione della posizione in alfa_ordinato[] con alfa[]


WildEagle wrote:
Mi e' partito un messaggio di risposta incompleta per sbaglio :)
Da quel che ho capito, vorresti decodificare un messaggio codificato con 
una semplice sostituzione di lettere.
   byte[] alfa = new byte[256];
   for (int i = 1; i < 256; i++) {
     byte valoreCasuale = ...;
     alfa[i] = valoreCasuale;
   }
Puoi creare un array di byte con la sostituzione inversa:
   byte[] alfaInversa = new byte[256];
   for (int i = 0; i < 256; i++) {
     alfaInversa[alfa[i]] = (byte)i; // ci vuole il cast ? boh :) ?
   }
Quindi il tuo algoritmo di decodifica di beta sarebbe qualcosa del tipo:
   byte[] risposta = new byte[beta.length];
   for (int i = 0; i < beta.length; i++) {
     risposta[i] = alfaInversa[beta[i]];
   }
Spero di aver capito giusto :) !

 wrote:
[CUT]
non ho capito una mazza.
ma prova con:
for(j=0;j<1048576;j++){
  risposta[j]=alfa[beta[j]];
}
ma non ho capito bene cosa c'e' in alfa, beta e cosa vuoi cercare.
-- 
Yoda of Borg am I! Assimilated shall you be! Futile resistance is, hmm?

 > Spero di non avere preso un granchio :-)
Ho riletto il problema e lo ho preso :-(
Pensavo che cercavi una stringa di 256 dentro un testo in pratica
vedi Giambo che mi pare buona la sua idea.
Nicola


 tabella alfa.
allora fai prima a creare un array alfa2 con dentro il reciproco di
alfa.
for(i=0,i<256;i++)
{
    alfa2[alfa[i]] = i;
}
e poi usi alfa2 come per decodificare nello stesso modo in cui usi alfa
per codificare.
Ciao Jack
PS:fammi sapere se funziona


  accade per il seguente codice, ma per i byte?
Prima di tutto due domande:
1) byte alfa[] è la tabella ASCII?
2) (più articolata) Stai cercando il valore dell'indice associato al 
particolare carattere della tua tabella, giusto?
Mi spiego meglio, tu hai una frase, prendi carattere per carattere, lo 
ricerchi nella tua tabella ed ottieni il valore dell'indice, vero!?
Se cosi fosse, un modo molto ma molto "sporco" potrebbe essere:
byte[] alfa = ... 	// la tua tabella
byte[] beta = ...	// la tua frase
byte[] codifica = ...	// il tuo risultato
String t_alfa = new String(alfa);  // String(byte[] bytes) è lecito
String t_beta = new String(beta);  // come costruttore...
char c;
for(int i = 0; i < t_beta.lenght; i++){
	c = t_beta.charAt(i);
	codifica[i] = (byte) t_alfa.indexOf(c);
}
Credo che a livello didattico (sopratutto se il problema è 
universitario) nessuno te la farebbe mai passare questa cosa, ma 
tecnicamente .charAt() e .indexOf() nelle loro implementazioni fanno 
proprio quello che ti serve a te...! ;)
Ciao,
jRed

 Spero di aver capito giusto :) !
Hai certamente capito giusto e inoltre mi hai dato la soluzione
corretta!! Con questo metodo decodifico alla stessa velocità della
codifica, quindi rapidamente!
Ti ringrazio per l'aiuto!!
Ciao
WildEagle

 PS:fammi sapere se funziona
Si, esatto, l'idea del reciproco è quella giusta, come ha scritto anche
Giambo nel thread.
Funziona egregiamente come soluzione!
Grazie anche a te!
Ciao
WildEagle

 jRed
Non so se il problema possa essere universitario o meno. Io sto
realizzando un programma di codificazione che invece di usare una
password utilizza un "dizionario random" di tabelle ascii con le quali
codifico un qualsiasi file binario (e quindi anche di testo).
Grazie per l'aiuto comunque!
Ciao
WildEagle

 
Si, infatti. La sua idea è stata ottima.
Ciao e grazie anche a te!
WildEagle

 Spero di aver capito giusto :) !
anche qui ho dovuto correggere per colpa del fatto che i byte sono signed:
       beta[i]=alfa[h[w]][(int)(beta[i]+128)];
uso questa scrittura perché beta[i] è molto grosso ed è inutile duplicarlo.
P.S. alfa[][] è un array doppio di 4milioni x 256 elementi!! ;-) Solo
grazie a java son potuto arrivare a queste dimensioni in assoluto relax!
Grazie a tutti per i preziosi consigli!
Ciao
WildEagle

> codificato con una semplice sostituzione di lettere.
W> Si, il principio base è quello dell'alfabeto di Cesare, però fatto
W> con l'intera tabella ascii, quest'ultima creata in modo random.
Se non  ricordo male e`  una Enigma ad  un solo disco non  rotante per
essere precisi.  Vedo  che nel thread ti hanno  già indicato come fare
la decodifica.
Mi pare rimanga fuori questo punto
W> Generando casualmente i numeri da 0 a 255 e poi riempiendo con tali
W> numeri l'array alfa, controllando pure di non inserire elementi già
W> messi prima
A naso ti conviene generare l'array di codifica ordinato e poi eseguire
N volte (N a piacere)
i <- numero casuale in [0..255]
j <- numero casuale in [0..255]
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
-- 
 /\           ___
/___/\_|_|\_|__|___Gian Uberto Lauri_____
  //--\| | \|  |   Integralista GNUslamico
\/                 e coltivatore diretto di Software

 
Per questo punto, visto che devo generare un numero abbastanza elevato
di array di codifica (creando una specie di cifrario o dizionario) ho
optato per il seguente codice che mi garantisce un array diverso ogni
1568 estrazioni circa:
int w=0;int i=0;
int[] k=new int[256];
int p=0;
for(w=0;w<b;w++){
            for(i=0;i<256;i++){
            k[i]=i;
        }
        for(i=0;i<256;i++){
            p++;
            int c =  (int) (256*java.lang.Math.random());
            if (k[c]!=-1){
                alfa[w][i]=(byte)k[c];
                k[c]=-1;
            }else{
                i--;
            }
        }
//la media(p) è 1568 (al momento credo di aver estratto circa 100
milioni di combinazioni)
Ho scelto questo metodo perché il numero di tentativi per avere un array
 "disordinato" in modo diverso è scelto volta per volta dal sistema in
base a che cosa combina la funzione random() (che ritorna anche lo
stesso valore più volte di fila quando la si mette in un for).
Proverò a mettere un po' sotto test il tuo metodo perché mi sembra più
"pulito" di quello che ho scelto io anche se non saprei quanto grande
debba essere N.
Grazie del suggerimento!
Ciao
WildEagle