Newsgroup: it.comp.lang.visual-basic
Titolo: Implementazione VB del DISTINCT

A tempo perso, ho provato a scrivere un algoritmo che, dato in ingresso un
array di long ed un array vuoto (sempre di long), inserisce nel secondo
array tutti i valori distinti che si trovano nel primo.
In pratica la clausola DISTINCT di SQL.
Esempio: se v()=6,1,2,3,1 dovrà essere d()=6,1,2,3 (l'ordine è irrilevante).
Algoritmo ovvio: per ogni elemento di V() controllo se tale elemento esiste
già in d(), e, in caso contrario, lo aggiungo.
Unica nota di ottimizzazione: faccio il redim a blocchi e non per ogni
elemento aggiunto.
L'algoritmo è molto lento:
Sub makedistinct_1(v() As Long, d() As Long)
Const passo = 10000
Const passoMenoUno = passo - 1
Dim a As Long
Dim b As Long
ReDim d(passoMenoUno) As Long
d(0) = v(0)
b = 0
For a = 1 To UBound(v())
    If Not esiste(v(a), d, b) Then
        b = b + 1
        If UBound(d) < b Then
            ReDim Preserve d(UBound(d) + passo)
        End If
        d(b) = v(a)
    End If
Next
ReDim Preserve d(b)
End Sub
Function esiste(e As Long, d() As Long, b As Long) As Boolean
Dim a As Long
esiste = False
For a = 0 To b
    If e = d(a) Then
        esiste = True
        Exit Function
    End If
Next
End Function
'-----------------------------------------------------------------------
Algoritmo pigro: uso le collection;
lento e occupa molta memoria:
Sub makedistinct_2(v() As Long, d() As Long)
Dim a As Long
Dim c As Collection
Set c = New Collection
On Error Resume Next
For a = LBound(v) To UBound(v)
    c.Add v(a), "_" & v(a)
Next
On Error GoTo 0
ReDim d(c.Count - 1)
For a = 1 To c.Count
    d(a - 1) = c(a)
Next
Set c = Nothing
End Sub
-------------------------------------------------
Algoritmo termoPilucco: esegue la distinct di 10.000.000 di elementi scelti
a caso fra 10.000.000 di numeri in 2.66 Secondi su un P3 1,2Ghz;
questo lo posto solo se siete interessati :)
Se qualcuno ha qualche idea originale è il ben venuto
<x:termoPilucco>

 Se qualcuno ha qualche idea originale è il ben venuto
C'ho provato (persino con stringhe e Instr conseguenti), ma non arrivo a
quei tempi, quindi ... sono interessato.

 questo lo posto solo se siete interessati :)
sempre interessato a imparare qualcosa di nuovo
ciaociao

 quei tempi, quindi ... sono interessato.
Premesse:
-il mio algoritmo è una lamerata :)
-è una lamerata perchè pretende che l'array di ingresso sia formato da
numeri non negativi e non superiori ad una soglia che dipende dalla memoria
montata sul PC su cui girerà (quindi bisogna farne un uso ponderato).
-è una variante dell'ordinamento "lineare" che avevo scritto, il quale è a
sua volta, indovinate, una lamerata.
-ovviamente la velocità va testata sul compilato ottimizzato PPro e senza
check su array e compagni.
Sub makedistinct_3(v() As Long, d() As Long)
Dim lngmax As Long
Dim a As Long
Dim b As Long
Const passo = 100000
Const passoMenoUno = passo - 1
' ricerca del massimo valore
lngmax = v(LBound(v))
For a = LBound(v) + 1 To UBound(v)
    If v(a) > lngmax Then lngmax = v(a)
Next
If lngmax > 134217727 Then
    ' dovrei dimensionare un array di oltre 134.217.728 byte=128MB
    MsgBox "ERRORE: prova con qualche algoritmo scialbo e lento :)"
    ' call AlgoritmoScialboELento(v,d)
    Exit Sub
Else
    ' I valori distinti possono essere al massimo
    ' tanti quanti i valori originali:
    ReDim Preserve d(UBound(v))
    ' Buffer d'appoggio: ci finirà un valore 1 per ogni valore dell'array
v()
    ReDim buf(0 To lngmax) As Byte
    ' inserisco 1 in corrispondenza di ogni elemento esistente
    For a = LBound(v) To UBound(v)
        buf(v(a)) = 1
    Next
    ' cerco in quali celle ho messo 1; effetto collaterale:
    ' l'array d() risulta ordinato
    b = -1
    For a = LBound(buf) To UBound(buf)
        If buf(a) = 1 Then
            b = b + 1
            d(b) = a
        End If
    Next
End If
' Se necessario taglio l'array all'ultimo
' elemento distinto.
If b <> UBound(d) Then
    ReDim Preserve d(b)
End If
End Sub
<x:termoPilucco>

 su un P3 1,2Ghz;
Tra l'altro mi devo correggere: la versione che ho postato esegue la
distinct di 10.000.000 di
elementi scelti a caso fra 10.000.000 di numeri in 2,2 Secondi su un P3 a
833Mhz.
<x:termoPilucco>

 senza check su array e compagni.
Ho guardato e provato il codice. Va.
Sintetizzerei in questo modo:
-Crei un vettore di tanti long quanti sono gli elementi/numeri del vettore
d'ingresso, poi lo ridurrai per i distinct trovati.
-Crei un vettore di tanti byte quanti sono gli elementi/numeri del vettore
d'ingresso per segnare quali sono i numeri presenti.
Obiezioni:
-Quel test su lngmax andrebbe "corretto". Se il limite è di 128 Mb non basta
contare gli elementi, ma gli stessi per l'occupazione (4 bytes per un long,
più puntatori relativi?)
Suggerimenti:
-Per ridurre l'occupazione (salvo verificare la velocità) al posto dei byte
si potrebbe usare una stringa di lngmax/8 byte, pari a lngmax bits, da
trattarsi come tali, consumando quindi un bit invece di un byte per il
numero degli elementi del vettore.
-Perchè dimensionare a priori d (vettore di output) grande per poi troncarlo
ai distinct? Non so quanto sia più performante (ma certamente consumerebbe
meno memoria), ma andrebbe dimensionato esattamente, contando (già lo fai,
ma andrebbe spostato nell'assegnazione dei vari "1", per non fare due volte
il ciclo finale) quanti sono i distinct prima della loro restituzione.

 ai distinct? [...]
Qui hai ragione, però:
per sapere quanti sono i distinct dovrei fare un ciclo preventivo (non che
pesi eccessivamente) ma nel caso peggiore dovrei comunque dimensionare
l'array alla dimensione di quello originale.
<x:termoPilucco>, sborone.

 <x:termoPilucco>, sborone.

buf(v(a)) = 1
Giusto, però dovrei anche verificare che buf(v(a)) non sia già uguale a 1,
atrimenti mi conta sempre il numero degli elementi d'ingresso.
<x:termoPilucco>

 distinti risultano già ordinati?
Sì.
Rinunciando a questo mi viene un'altra ipotesi che consumerebbe 0 bytes
aggiuntivi, cambiando però anche il metodo di ricerca/scandaglio e quindi i
tempi
di elaborazione:
Uno dei tuoi attuali presupposti è che i numeri siano interi e positivi o,
al minimo, zero.
Rinunciando anche allo 0, potresti usare sempre e solo il vettore di input
prevedendo che lo stesso riporti al chiamante tutti i numeri distinti
(purtroppo in disordine, ovvero nello stesso ordine originale) positivi e,
convenzionalmente (pur potendone ricostruire la loro esatta entità
semplicemente con un Abs), i numeri duplicati come negativi, che il
chiamante ignorerà, magari in blocco dopo un ordinamento crescente o
decrescente dell'intero vettore...

termoPilucco wrote:
termo....(che bella abbreviazione per uno come me che sta a 5 gradi)....
non ho provato il tuo algoritmo......
e lamerata per lamerata :-P
...se la memoria non č un problema.....e al limite c'č un file sull'HD
SE
hai  un vettore disordinato e con ocorrenze multiple
ad esempio: 1,2,3,2,3,2,4,5,6,4,5,6,5,1,2,3,8....n
E
non ti importa ordinarlo ma trovare i valori "unici"
ALLORA....
....(lo scan del vettore lo devi fare per forza)....
se via via che lo scandisci incrementi in un altra matrice/vettore/tabella
le occorrenze di quello che trovi.....
......
alla fine basta fare lo scan della matrice/vettore/tabella occorrenze
.....
quelle ad 1 sono le tue distinct
...oltre ad avere un conto delle occorrenze (se ti serve)....
non ho tempo per implementare le mille varianti che mi vengono in mente
....(una matrice clone con i valori da max a min trovati...oppure una
matrice bidimensionale (numero/oggetto)(Occorrenza).....etc etc)
se hai tempo prova a vedere se č piů lento del tuo algoritmo.....di sicuro
consuma piů memoria!
ma tu usi Redim Ubound etc etc che dovrebbero essere lentissimi in un loop
( e non son sicuro che la memoria del pc non si sovraccarichi!).....mentre
con il mio faresti solo un Occor(n)=Occor(n)+1
...boh pensaci....
Saluti
-- 
Il Wodkino Nazionale č a : 
www.martek.it
Pagina Vb/Bestiario/Lamer Experience :
http://www.martek.it/go.asp?portamia=2
 Quotefix e altro:
http://www.martek.it/go.asp?portamia=4
Usr: ICLVB Pw: amici

 ...oltre ad avere un conto delle occorrenze (se ti serve)....
E' quello che fa il mio ordinamento "lineare" (l'altra lamerata)
Ho in mente un modo per trasformare entrambi i metodi (sort e distinct) in
un algoritmo serio: niente occupazione eccessiva di memoria e prestazioni
nei casi pratici migliori di QuickSort/algoritmi analoghi.
<x:termoPilucco>

 ....
Per ovviare al secondo punto potresti ricavare all'inizio sia il valore
minimo che quello massimo e quindi ripetere il ciclo in base alla dimensione
massima che vuoi dare al buffer di appoggio.
Ovviamente tutto dipende dalle dimensioni del vettore in input e dai valori
contenuti, nel caso di due soli campi uno con -2G e l'altro con +2G avresti
delle prestazioni schifose in quanto si avrebbero 4G di IF praticamente
inutili.
Visto che il risultato poi viene ordinato forse sarebbe meglio ordinare il
vettore in input e quindi con un solo ciclo estrarre i valori unici.

 il  vettore in input e quindi con un solo ciclo estrarre i valori unici.
Nonono :) il problema "distinct" è, mal che vada, risolvibile con un
ordinamento preventivo ed un ciclo successivo, quindi un buon algoritmo
"distinct" dovrebbe essere mediamente più veloce del migliore algoritmo di
ordinamento.
<x:termoPilucco>