Newsgroup: it.comp.lang.visual-basic
Titolo: [VB.NET] Ottimizzare Ricerca Binaria

Salve a tutti,
per il mio traduttore sto cercando di ottimizzare l'algoritmo di ricerca 
binaria in quanto, su PocketPC richiede troppo tempo (circa 1-2 sec.) 
per analizzare 2000-3000 parole (alcuni dizionari ne contengono anche 
40.000)
Per questo vi posto l'algoritmo che uso.
         Dim first As Long
         Dim last As Long
         Dim middle As Long
         first = LBound(arr)
         last = UBound(arr)
         Do
             arr(middle) = LCase(arr(middle))
             middle = (first + last) \ 2
             If arr(middle) > search Then
                 last = middle - 1
             ElseIf arr(middle) < search Then
                 first = middle + 1
             Else
                 last = first
                 Return middle
             End If
         Loop Until first > last
         Return -1
Avete consigli su come potrei ottimizzarlo? (la soluzione dovrebbe 
essere compatibile con .NET Compact Framework 2.0)
Saluti a tutti
Nicola

 40.000)
[cut]
potresti crearti un array che contenga l'indice dell'elemento dove 
inizia ogni lettera dell'alfabeto, in questo modo, basandoti 
sull'iniziale della parola, dovresti ridurre parecchio il range di 
elementi in cui effettuare la ricerca.
bye
r

         Return -1
Ciao 

         If string.Compare(arr(middle), search, true) Then
Sai dirmi se convene fare un tolower o lo String Compare?
Intendo dire come cicli macchina impiegati per ottenere la stessa cosa.
Grazie mille per l'aiuto Zanna.
Un abbraccio
Nicola

nerone ha scritto:

Il problema non è così banale in quanto il mio traduttore gestisce 
lingue di tutto il mondo.
Specie nel mondo asiatico (vedi cinese, coreano e giapponese) non 
esistono solo delle lettere, ma vari tipi di alfabeti basati su 
ideogrammi (In Giappone, ad esempio utilizzano l'Hiragana, Katakana, e 
Kanji).
Il Kanji (o in coreano Hanja) è l'alfabeto tradizionale Cinese, che 
contiene oltre 1500 ideogrammi (diciamo 1500 lettere, per semplicità).
Capisci che avrei un array di lettere più lungo del dizionario!!
Anche l'alfabeto arabo dà problemi, in quanto si legge da destra (quindi 
dovrei prendere l'ultima lettera della parola)... un casino.
A questo punto preferisco il consiglio di Zanna, per non incasinare 
troppo il mondo.
Grazie comunque per l'aiuto.
Un abbraccio
Nicola

 ha scritto nel messaggio 
news:43c97aaa$0$336$5fc...@news.tiscali.it...


 Nicola
bye
r

 Grazie mille per l'aiuto Zanna.
uh! mi hai riconosciuto? :)
Ciao 

Dunque, seguendo i tuoi consigli (mi ci sono messo d'impegno) ho tirato 
fuori questo algoritmo.
E' molto più veloce di prima (soprattutto per parole dalla lettera M in 
poi). Pubblico il codice così i posteri potranno usufruirne liberamente. 
Dici che si può ulteriormente migliorare?
La lista che prendo in input è già ordinata (il file viene ordinato già 
alla sua creazione, per non dover rifare il processo ogni volta).
     Function FastBinarySearch(ByVal arr() As String, ByVal search As 
String) As Long
         Dim first As Int32
         Dim last As Int32
         Dim middle As Int32
         first = arr.GetLowerBound(0)
         last = arr.GetUpperBound(0)
         Do
             'arr(middle) = arr(middle).ToLower()
             middle = (first + last) \ 2
             Dim ValStrCmp As Int32
             ValStrCmp = String.Compare(arr(middle), search, True)
             'If arr(middle) > search Then
             If ValStrCmp > 0 Then
                 last = middle - 1
             ElseIf ValStrCmp < 0 Then
                 'ElseIf arr(middle) < search Then
                 first = middle + 1
             Else
                 last = first
                 Return middle
             End If
         Loop Until first > last
         Return -1
     End Function
Grazie mille
Nicola

 Dici che si può ulteriormente migliorare?
Mi pare che non ci sia altro da ottimizzare, ma continuo a chiedermi perchè 
non usi quella già implementata nel framework.
Ciao 

 uh! mi hai riconosciuto? :)
Difficile sbagliarsi, visto l'indirizzo :-P
Bye, G.

 Difficile sbagliarsi, visto l'indirizzo :-P
Perchè, tu guardi l'indirizzo di chi posta quando leggi un messaggio? :)
Ciao
-- 
Free .Net Reporting Tool - 
http://www.neodatatype.net
 

 Free .Net Reporting Tool - 
http://www.neodatatype.net
Bye, G.


Io mi ero accorto subito del suo cambio di nick, ma con Agent č troppo facile
perchč l'indirizzo compare nella lista.
guarda lo screenshot:
http://img301.imageshack.us/img301/4549/agent6vn.jpg
--
ciao
  Stefano