Newsgroup: it.comp.lang.c
Titolo: Simboli diversi

Ho un vettore di unsigned long che può contenere da 2 a circa 1000 numeri 
del tutto casuali da 0 a 2^11-1 (in qualunque ordine, con o senza 
ripetizioni). Se può servire, posso anche usare un vettore di unsigned 
short.
Mi servirebbe contare *nel modo più veloce possibile* quanti numeri diversi 
sono presenti nel vettore. L'occupazione di RAM non è un problema, 
l'importante è la velocità d'esecuzione (il codice che ho scritto io è un 
po' lentino).
Per fare un esempio con un vettore da 5 numeri, il risultato della funzione 
deve essere:
0 8 3 4 5  =>  5 numeri diversi
9 2 3 2 1  =>  4 numeri diversi
7 5 7 3 5  =>  3 numeri diversi
2 2 0 2 6  =>  3 numeri diversi
    ...
3 3 3 3 3  =>  1 numero diverso
Grazie
Cristiano 


ordinali e poi scorri il vettore
Ciao


Così su due piedi e senza pensarci troppo farei un cosiddetto
istogramma: se i numeri vanno da 0 a 2^11-1 fai un vettore di 2^11 int
inizializzato a zero. Scorri il primo array e per ogni valore aumenti
di uno la corrispondente locazione sul secondo. Fatto questo scorri il
secondo array e conti :-)
L'occupazione di memoria è ridicola (2048 int) e computazionalmente
sono solo due cicli lunghi quanto l'input (è lineare).
Ciao!

On Aug 31, 11:19 am, logicmind

Questo conviene solo se il range di possibili valori è molto grosso (o
se il numero di entrate è molto piccolo).
Ciao!


parla di max 1000 numeri, ma anche fossero 1 milione, col quicksort non 
fai in tempo a cliccare che te li ha ordinati. Poi basta scorrere una 
volta il vettore e verificare se l'elemento corrente è uguale o diverso 
dal precedente ed incrementare di conseguenza il conteggio.
Ciao

On Aug 31, 11:58 am, logicmind

Certo. Rimane il fatto che quicksort gira in O(nlog) (O(n^2) se ti
dice male) mentre l'altro sempre in O(n). Non vedo quindi perché
implementarlo a meno che appunto non sia possibile allocare il vettore
d'istogramma.
Ciao!


con un range di [0 : 2^11-1] si, vale la pena di fare l'istogramma.
Anche se con questi valori non penso ci siano grandi diversità, ma il 
mio è scalabile ed è indifferente al range di valori e si sa come vanno 
le cose ... oggi è 2^11-1, domani potrebbe diventare 2^32-1 :-)
Ciao

On Aug 31, 12:35 pm, logicmind

eheheh e se domani il range diventa 2^4 e i numeri 2^64? :-)
In generale senza il contesto il concetto di "scalabile" è quasi
sempre troppo fumoso, per cui meglio seguire i requisiti (contare *nel
modo più veloce possibile*...) che fra parentesi non sono sicuro di
aver rispettato neanche io :-/
Ciao!

 vanno le cose ... oggi è 2^11-1, domani potrebbe diventare 2^32-1 :-)
No, no; penso di fermarmi a 2^10-1. :-)
Il sistema dell'istogramma è perfetto per il mio caso, perché evito anche il 
passaggio di memorizzare i numeri in un vettore temporaneo.
Il guadagno di tempo di tutta la funzione è intorno al 10% (ci sono altre 
cose ben più lente), ma la semplificazione del codice è notevole (rispetto a 
quello che avevo scritto io, una specie di bubble-sort modificato per lo 
scopo).
Grazie a tutti
Cristiano 


usa una hash table
scorri l' array
per ogni numero ricavi, tramite una funzione hash, un valore
se non è presente nella hash table incrementi il contatore ed inserisci 
il valore nella hash table
alla fine del ciclo il contatore conterrà il valore cercato

 alla fine del ciclo il contatore conterr il valore cercato
Ma anche no.
http://en.wikipedia.org/wiki/Hash_table
Ciao!


Premetto che a grandi linee (ricordi vecchi universitari)
so cosa è una hash table e come funziona (ti ringrazio per la 
rinfrescata di wikipedia)
ma non riesco a capire il tuo no
 


Perché in questo caso è molto inefficiente.
Se il range è di 2^11, lo hash dovrà ovviamente essere più piccolo
(altrimenti non ha senso utilizzare una hash table: visto che con la
funzione ottima di hash che semplicemente ritorna il valore di input
non hai collisioni rientri nel caso dell'istogramma), e la scelta di
2^8 mi sembra ovvia per facilitare l'indirizzamento. Quindi (se non
ricordo male e se faccio bene i conti) avresti O(1+2^8/n) per *ogni*
lookup (contro l'ovvio O(1)). Questo poi solo considerando la
complessità computazionale del lookup e non l'inserimento, visto che,
a livello pratico, anche se dipendono dall'implementazione, le
operazioni di chaining sono tutt'altro che "aggratis". :-)
Ciao!
 
P.S. E' comunque da dire che ovviamente nel caso sia il range di
valori che la quantità di dati sia molto grande una hash-table sia
probabilmente la soluzione migliore...


S, hai ragione
essendo il range dei valori 0..2^11 - 1 basta indirizzare un array in 
modo diretto con il valore, dato che la quantita di ram non è un 
problema in questo caso