Newsgroup: it.comp.lang.visual-basic
Titolo: Ricerca Dicotomica

Qualcuno ha qualche esempio da mostrarmi su questa ricerca?Avrei intenzione
di usarla in un prog e vorrei documentarmi...
Grazie.

 intenzione di usarla in un prog e vorrei documentarmi...
Guarda Fra è una cosa molto semplice.
Prima cosa.... è necessario che l'insieme di elementi sia ordianto, per
poter effettuare una ricerca dicotomica.
Mettiamo di voler cercare l'elemento 11, nella sequenza di input 12 18 14 15
6 7 22 11 45 72.
Bisogna prima riordinare l'input con degli algoritmi classici (BubbleSort,
InsertionSort, HeapSort, MergeSort, QuickSort, ecc... ti consiglio il
QuickSort)
Una volta che una funzione QuickSort mi riordina l'input come 6 7 11 12 14
15 18 22 45 72, potrai applicare la ricerca dicotomica.
Ti parlo di interi e di array, ma puoi applicare lo stesso principio a
qualsiasi tipo di elementi... basta che siano una "lista" di valori.
La ricerca dicotomica allora si effettua sulla sequenza ordinata.
Determino l'elemento centrale: 15
IF elemento cercato = elemento centrale THEN trovato
ELSE IF elemento cercato > elemento centrale THEN RicercaDicotomica(Elemento
Cercato, Dalla posizione centrale + 1)
ELSE  RicercaDicotomica(Elemento Cercato, Dalla posizione centrale -1).
In pratica, pseudo linguaggio a parte, essendo l'array ordinato, è chiaro
che io posso dividere via via in intervalli dimezzati.
Mi spiego, se tu cerchi il valore 11, e lo confronti con 15, scopri subito
che è inferiore... essendo ordinato l'array... 11 si troverà,
se c'è a sinistra. Per cui mi divido l'intervallo dall posizione 1 alla
posizione precedente alla centrale. A questo punto confronto 11 con il
valore centrale
del nuovo intervallo. Nel nostro caso è proprio 11 e l'abbiamo scovato.
In generale l'ordine di grandezza del numero di passi che devi fare per
trovare la chiave cercata è il log in base 2 del numero di elementi.
In pratica, hai  circa 4 miliardi di elementi in cui cercare... con una
ricerca lineare compi in media 2 miliardi di passi. Con la ricerca
dicotomica circa 32.
Non sono stato chiarissimo, ma se ti serve una mano ad implementarla...
volentieri.
Saluti,
--
Antonio Cangiano
Webmaster di 
www.visualcsharp.it
free.it.comp.lang.csharp / free.it.comp.lang.vbnet /
free.it.comp.lang.aspnet

 wrote in message
news:al7ffa$k02$1...@panco.nettuno.it...


con 1000 records ordinati, KeyRec + la chiave del record letto, Key è la
chiave di ricerca.
pseudo-esempio:
---------------------------
Inizio:
1000/2=500
Test:
if keyRec > Key then
   500/2 =250
   Goto Test
ElseIf KeyRec<Key Then
   500+(500/2)=750
   Goto Test
ElseIf KeyRec=Key Then
   Record trovato.
   Exit
Endif
Fabio

 con 1000 records ordinati, KeyRec + la chiave del record letto, Key č la


 ha scritto nel messaggio
news:al7h8a$qf6$1...@newsreader1.mclink.it...


 ha scritto nel messaggio
news:al7ffa$k02$1...@panco.nettuno.it...


 sia... Con che la valorizzo???E' una funzione? Grazie...
RecordKey() indica qualsiasi cosa - 
p.es
. una funzione - tu usi per farti
ritornare la chiave del i-esimo record. Quindi RecordKey(iMid) č la chiave
dell'iMid-esimo record.
s.

dim iLow as integer, iUpp as integer, iMid as integer, iFnd as integer
dim Key as string
iLow=1
iUpp=List1.ListCount
Key=Trim(Text1.Text)
iFnd = 0
do while iLow <=  iUpp
    iMid = (iLow + iUpp) / 2
    if Key = List1.List(iMid) then
        debug.print "Item found: " & iMid
        iFnd = iMid
        exit do
    elseif Key > List1.List(iMid) then
        iLow = iMid + 1
    else
        iUpp = iMid - 1
    end if
loop
if iFnd = 0 then
    debug.print "Item not found!"
end if

 di usarla in un prog e vorrei documentarmi...
Tratto dal SiDB, e leggermente riadattato per chiarezza:
Function sdbs_SearchDicotomic () As Long
    Dim i As Long
    Dim Min As Long
    Dim Max As Long
    Dim Count As Long
    Dim Direction As Long
    Dim RecordPtrIdx As Long
    ' ritorna l'indice dell'item cercato
    ' oppure -1 se non trovato
        '=============================================
        '      Ricerca della posizione del nuovo
        '      record
        '=============================================
        Min = 1
        Max = Count
        Do 'While True
            i = Min + (Max - Min) \ 2
            Direction = KeyBuffer -  Item(i)
            If (Direction = 0) Then
                Exit Do
            Else
                If (Direction < 0) Then
                    Max = i - 1
                Else
                    Min = i + 1
                End If
            End If
            If (Min > Max) Then
                ' non trovato
                Exit Do
            End If
        Loop
        ' -----------------------------------
        '  controllo per chiave duplicata
        ' -----------------------------------
        If (Direction = 0) and (SearchNewIndex) Then
            ' usa una chiave univoca
            ' e sto cercando la posizione di inserimento
            ' del nuovo item
            If (TableInfo.tKey.Unique) Then
                sdbs_SearchDicotomic = -1
                Exit Function
            End If
        End If
        ' Ecco la posizione dell'item!
        RecordPtrIdx = i
        If (SearchNewIndex) Then
        ' Se sto cercando la posizione dell'item
        ' da inserire scorro le posizioni fino alla prima libera
            Do While (Direction >= 0)
                If (RecordPtrIdx >= Count) Then
                    RecordPtrIdx = Count + 1
                    Exit Do
                Else
                    RecordPtrIdx = RecordPtrIdx + 1
                End If
                Direction = KeyBuffer - Item(RecordPtrIdx)
            Loop
        End If
        sdbs_SearchDicotomic = RecordPtrIdx
End Sub
Ciao
--
' // Initialize the expression evaluator
Engines.Evaluator = CreateObject("
http://www.neodatatype.net
")
' // you can find resources for and from the NG here!
Me.SitoComune = "
http://www.it-lang-vb.it
"

     KeyRec = (List1.ListCount / 2)
Nota n° 2: RICERCA DICOTOMICA SU UN LISTBOX???
Di norma una ricerca del genere si fa solo sugli indici, e garantisce
altissime prestazioni anche con DB di milioni e milioni di records. La R.D.
accede al record voluto con un massimo di 12/15 accessi al file.
Sei sicuro di essere obbligato a implementare una cosa del genere su un
ListBox?
Fabio

Segue il codice ottimizzato della funzione.
Function RkKey(Value As Variant) As Long
   Dim i As Long, i1 As Long, i2 As Long, d As Long, v1 As Variant
 ' ricerca dicotomica: 15 accessi massimi
 ' sono sufficenti per trovare qualsiasi valore in files di qualsiasi
 ' dimensione
   i1 = 1: i2 = hFile.nr ' <- hFile.nr: Numero totale di records
   Do While i2 - i1 >= 2
      d = i2 - i1
      i = i1 + d / 2
      ' Rk(i).Key  č la chiave del record  i
      If  Rk(i).Key = Value Then
           RkKey = i
           MsgBox "Trovato"
           Exit Function
      End If
      If Rk(i).Key < Value Then i1 = i
      If Rk(i).Key > Value Then i2 = i
   Loop
   MsgBox "Non trovato"
End Function

 ha scritto nel messaggio
news:al87aq$1llj$1...@newsreader1.mclink.it...


       ' Rk(i).Key  è la chiave del record  i


 sia... Con che la valorizzo???
C'è qualcun altro che viene colto da conati di vomito, oltre me, a sentire
l'ormai (ab)usatissimo "valorizzare una variabile"?
Capisco l'inglesismo "settare", ma valorizzare proprio no!
v. tr. far acquistare valore, far aumentare di valore: valorizzare un
terreno; le nuove costruzioni hanno valorizzato l'intera zona | mettere in
risalto, far figurare meglio: il nero valorizza la sua figura; valorizzare
una persona, fornirle delle occasioni che le permettano di esprimere le sue
capacità ||| valorizzarsi v. intr. pron. accrescere di valore, di
importanza: un paese che per valorizzarsi ha bisogno di strutture
alberghiere.
http://www.garzantilinguistica.it/
--
Ciao, Silv:o)

>RA>>iLow=0
s.

> iUpp=List1.ListCount - 1
s.

> "Silvio Sergio" [...]:

    Io dico "assegnare un valore a una variabile". Ma e' francesismo. Bleah,
che schifo. Sai che non ho idea di come si dica in italiano? A dire il vero
non so piu' nemmeno cosa sia, l'italiano. Degl'italiani... lasciam perdere.
Da quando abbiam ricalzato l'elmo di Scipio ci ho un mal di testa... Doveva
avercela proprio piccina, la testa, quel Scipio. Anche lo Stivale mi sta
stretto. 'St'italian fascion!... Bello e' bello, ma ci mettessero un niente
di stoffa in piu' che, se s'ingrassa... o se il lavasecco... come dice il
nome... sottostima le masse...
--
Ciao :-)
Maurizio
--------
?SPQR(C)
 X
--------

 l'ormai (ab)usatissimo "valorizzare una variabile"?
Piů che altro il problema č logico: una variabile č *sempre* valorizzata, se
per "valorizzata" si intende "avente valore".
Una variabile si puň settare, cambiare, assegnare, impostare, rendere uguale
a, porla a, metterci detro il valore di...


 Capisco l'inglesismo "settare", ma valorizzare proprio no!
Scusa, ma se ad una variabile assegni un valore, non l'hai appunto
"valorizzata"?  ovverro gli hai dato un'importanza, logica, che prima non
aveva.
Se questo fosse scorretto, dovremmo rivedere il termine che usaimo quando si
assegna qualcosa ad una variabile.
A me 'valore' sembrava corretto.
Non per essere pignolo, ma non vedo come puoi far passare 'settare' che sa
di 'ciuingam' e non 'valorizzare' che a senso mi suona italianissimo.
Oppure prevedi che garzanti aggiunga 'settare', 'la funzione ritorna',
'killato', IMHO, BTW  ecc, mettendo il poco italiano rimasto fra i termini
arcaici? :)
Fabio

> "Fabio Guerrazzi" [...]:

    Ci sono buone probabilita' che cio' avvenga. Dal tabaccaio, Lucio
Stanca, Ministro per l'Innovazione e le Tecnologie, suppongo a spese della
Federazione Italiana Tabaccai perche' in ultima pagina questa ci racconta
quanto sono bravi, ha messo in distribuzione un opuscolo intitolato:
        "Dalle code al click."
    Ti prego di notare, prima di tutto, il fatto che in un titolo, in una
copertina, ci sia il punto fermo. Poi ovviamente il "k" di clic.
    Ciliegina: la gambetta di @. A circondare lo Stellone d'Italia.
    Prefazione. Terza riga: La digitalizzazione della Pubblica
Amministrazione, [...]
    Capisci? La "digitalizzazione"!
    E mi fermo qui.


 arcaici? :)
Forestierismi se ne aggiungono a tonnellate ogni anno, a dimostrazione della
natura dinamica della lingua. Fortunatamente.
Il problema sorge quando usiamo a sproposito parole che già ci sono, solo
perché la nostra lingua non ha un termine che si adatti alla perfezione al
contesto. Comunque, come ha dimostrato Zanna, l'impresa è ampiamente alla
portata del nostro vecchio Zanichelli.
--
Ciao, Silv:o)

 a, porla a, metterci detro il valore di...
Ci ho pensato e, visto che il 3d è un po' deviato, detto simpaticamente,
propongo il mio neologismo:
Giustificare.
Credo che possa avere un senso ben preciso, anche tecnicamente, anche con
Null, anche con Nothing.

 Oppure prevedi che garzanti aggiunga 'settare', 'la funzione ritorna',
Non vorrei dare un colpo alle tue credenze, ma mentre non ho mai sentito
dire "valorizzare una variabile" (ma tutto può essere fuor che l'uomo
gravido, diceva la mia povera nonna) il verbo "settare" è ormai entrato a
far parte della lingua italiana da molti anni e alcuni vocabolari - fra i
quali il Garzanti [sic!] - riportano appunto l'accezione di "settare il
valore di una variabile".
D'altra parte, essendo il procedimento conosciuto anche in altre
discipline - 
p.es
. la logica e la matematica - i puristi potrebbero comunque
rivolgersi a queste discipline e usare verbi come "assegnare" o "impostare"
il valore a/di una variabile, piuttosto che impiegare locuzioni che, seppure
non derivate da lingue straniere, non hanno tuttavia patria nella nostra
lingua.
S.

 portata del nostro vecchio Zanichelli.
ah ! e' finalmente uscito lo zannichelli ?
e invece di sfogliarlo (possibilmente senza defoliarlo) ci si fanno le
query ?
ciao, a.
[*] mi sto esercitando con le classi.
vorrei almeno passare l'ammissione alla prima.

 gravido, diceva la mia povera nonna)
povera ? se sapesse che la ricerca mira a smentirla...

 Giustificare.
"Giustificare" non è un neologismo, e secondo me assomiglia molto più a
"indentare".


 "indentare".
pero' azzannare il codice lo puoi fare solo tu :P

 "indentare".
Zanna, non sarà un neologismo in quanto termine già esistente col
significato (anche tecnico) che gli hai dato (anche se invece di indentare
direi "stiracchiare").
Mi sembrava carino, mi sarò sbagliato:
Quand'è che una variabile ha ragion d'essere, giustificata, appunto?
E, per contro, non è corretto dire che una variabile definita, ma non
assegnata, settata, etc... non è "giustificata"?
Mi piace sempre più!
Lupo.borioso

 visto che tanto si parla di idioletti...
Volevo quotare, stavo quotando tutto, non si puņ.
Cutto (no, non apriamo un altro trattato sul "cutto").
"Bentornato" al nostro miglior Java!
Grande risata.
(giusto per evitare un forestierismo inutile, specialmente da uno degli
ampollanti sul po, non politico, perņ)


Sei mitico.. spedisci i più gradevoli post del NG :)
Ciao


Ok, ma capiamoci. Se qualcuno ha conati di vomito alla vista di 'valorizzare
una variabile' rischia un infarto su questo NG!!
Completare la frase seguente:
"Ho impostato ad una variabile il *valore* 1. Essendo ora  ______________ ad
1, posso .. (ecc.) "
Soluzioni possibili
1) Impostata
2) Valorizzata
3) Assegnata
4) Settata
5) Inizializzata
6) Impiastricciata
Risposte
1) Sbagliata, è il valore che è impostato, non la variabile. In più è
iterativo
2) Avendo acquisito un 'valore' a me suona come giusta
3) Sbagliata, il valore è assegnato, non la variabile
4) Se trovo un sorgente in cui qualcuno ha una variabile 'settata' cestino
sia il codice che il programmatore :)
5) ai miei tempi l'inizializzazione si chiamava IPL e durava mezz'ora per
far partire i mainframe IBM
6) Forse, daltronde su Garzanti e Zanichelli il termine esiste
Oppure, in termini puramente informatici, se ti chiedessi lo stato di una
variabile non 'nulla' (quindi il contrario), mi risponderesti 'settata'?
Ti ricordo che è il valore che assegni, non la variabile. la variabile è
'assegnata' al programma quando la dichiari.
--
Fabio Guerrazzi
http://www.sourcecode4free.com/cgt
fab...@libero.it

 assegnata, settata, etc... non č "giustificata"?
ma, piů che 'non giustificata' mi sembra semplicemente 'non usata'
Fabio

 ma, più che 'non giustificata' mi sembra semplicemente 'non usata'
Ok, ma se non venisse mai assegnata, settata, etc.? davvero inutile no? Non
giustificata, appunto.
Poi bisognerebbe (ormai siamo abbondantemente OT, farò danni se mi dilungo
un pelo?) discutere sull'interpretazione di Null o Nothing.
Io non credo al nulla, come non credo all'infinito.
Nel senso che i due concetti non stanno nella mia testa, dopo un po' che ci
penso fuma.
Una variabile non definita, semplicemente non esiste.
Una variabile definita, IMHO, esiste eccome e quindi qualsiasi contenuto
abbia (0, "", Null, Nothing, senza voler fare paragoni per il libero elenco)
questo rappresenta qualcosa, indefinibile e/o non misurabile, ma
assolutamente presente in quanto la sua "scatola" esiste. Dentro la scatola
c'è "qualcosa" che qualcuno ha definito Null o Nothing, ma che nessenu,
nemmeno lui, potrà mai abbinare al "nulla". Se così fosse, risponderei
"allora perchè hai dovuto definire Null e Nothing?".
In questo senso il mio scherzoso "giustificata" sta a indicare che una
variabile (o un oggetto) contiene qualcosa (compreso Null o Nothing), mentre
non è giustificata se non le è stato esplicitamente assegnato un valore,
cioè qualcosa (sempre compreso Null e Nothing).
Che poi il qualcuno di prima, per sua spudorata comodità (e, IMHO, la
scomodità degli altri), abbia deciso che la definizione di una variabile
tipizzata le faccia contestualmente assumere un "valore" (o "qualcosa") è un
altro discorso. Comprensibile e quasi obbligato, direi. Nemmeno lui poteva
mettere il nulla in una variabile, solo perchè non esiste e quindi non può
comprarlo.

 lingua italiana :)
Sì, ma - non è per volertene, giuro - è la prima volta che lo sento usare in
quest'accezione. Indubbiamente l'età ormai mi  rende poco incline a recepire
i nuovi slang, ma così è!
Secondo il dizionario, "settare" è usato in italiano almeno dal 1988. Io
sono piuttosto sicuro che nell'88 "settare" si usava e sono sicurissimo che
non si usava "valorizzare" (allora lavoravo in grossi team, non solo
italiani, e la cerchia dei programmatori non era enorme, perciò avrei saputo
una cosa del genere) . Se però mi giuri che anche 'valorizzare' ha corso
ufficiale, mi adeguerò...

 1, posso .. (ecc.) "
Così però te la suoni e te la canti. Intanto la premessa è sbagliata, perché
tu dici "ho impostato ad una variabile il valore 1" (a parte che io direi
"ho impostato il valore di una variabile a 1" o anche "ho assegnato ad una
variabile il valore 1" e anche, in sintesi, "ho impostato una variabile a
1") e poi ci dici che la risposta 1 è sbagliata perché non è la variabile ma
il valore ad essere impostato. Però così:
(a) risolvi la questione usando tu stesso il verbo "impostare" (la premessa
contiene quindi la soluzione)
(b) formuli la domanda in modo che sia sintatticamente impossibile formulare
la risposta 1 in modo corretto: avresti dovuto dire: "essendo ora il valore
_____ a 1, posso ... (ecc.)" (e qui mica ci metteresti "valorizzato"!)
Ora, è vero che Totti docet e che in fondo il significato è nell'uso, quindi
lungi da me fare il perfettino, ma poiché avete iniziato questo thread nel
segno degli occhi alle pulci diciamoci che "settare" non sarà bello, ma
"valorizzare" ve lo siete inventato ieri e ora cercate di rimanere a galla.
In italiano si dice "impostare il valore di (o ad) una variabile" e forse
(in gergo matematico) si dice meglio "assegnare un valore ad una variabile".
Si diceva quando gli elaboratori erano un barlume in fondo alle pupille di
Lord Babbage e prima che Turing e Goedel mettessero i calzoni corti.
Andiamo!

 'valorizzare una variabile' rischia un infarto su questo NG!!
Mica vero. Quel qualcuno sono io, il ng lo seguo da parecchio e
frequento la comunità dei programmatori da ancor di più, ma brutte
come 'valorizzare' non me ne ricordo (de gustibus ecc.). Hai presente
Fonzie quando doveva dire "ho sbagliato" e non ci riusciva? ecco: se
dovessero imporre per decreto 'valorizzare una variabile' avrei le
stesse difficoltà. E purtroppo se le tre cose fondamentali della vita
sono le tre "I", dovrò rassegnarmi
OT nell'OT: maccheccazzomenefrega poi che mio figlio faccia
l'imprenditore su internet in inglese? Sarà mica meglio se gli
insegnano a pensare pensare con la sua testa, magari coi congiuntivi,
dando ai soldi il valore che meritano?
--
Ciao, Silv:o)

 i nuovi slang, ma così è!
Il fatto strano e che non capisco sta proprio su questo punto:
'settare' _E'_ slang, non 'valorizzare'.
Anch'io non ho più 15 anni, e ammetto che prima non si usava. Credo solo di
aver accettato il nuovo uso perché coerente con la lingua italiana, molto
più di settare.
Inoltre credo che detto slang, o forestierismo, sia stato anche applicato
male. Dubito che gli inglesi abbiano una 'setted variable'. Immagino che per
loro sia 'evaluated'
Ad ogni modo siamo incappati in uno dei problemi che riguardano più la
glottologia che l'informatica: La trasformazione della lingua. Se una volta
erano le invasioni barbariche a modificare il modo di parlare mi sembra
scontato che oggi sia il popolo computerizzato. E a giudicare dalla qualità
dei nuovi termini introdotti le due correnti si assomigliano molto.
Poi ragazzi, mi rivolgo anche a Silvio Sergio,  io non metto in dubbio il
gusto. E' ovvio che si tratta di interpretazione, io ho conati di vomito
alla vista dei gamberetti, e non per questo dico che è stupido mangiarli.
Sono solo opinioni, le verità e le certezze le lascio ad altri. Comunque
sia, a me piacciono chiacchierate del genere :) spero di non aver offeso
nessuno.
Fabio

 pero' azzannare il codice lo puoi fare solo tu :P
Questa me l'aspettavo :) ma ho detto "indentare", non "addentare" :)


 Questa me l'aspettavo :) ma ho detto "indentare", non "addentare" :)
ah, lo inzaghi o lo inzanni, alloro ?

 nessuno.
Confidando che nessuno se la prenda per due chiacchiere - specialmente
quelle OT! - concludo con questo: le opinioni sono come la palle, ognuno ha
le sue, tuttavia l'alternativa non è la "verità" - che solo gli dèi
posseggono. Per noi mortali è il significato quello che conta.
Saluti.