Newsgroup: it.comp.lang.visual-basic
Titolo: [semi OT] Velocità algoritmo hashing

Ciao ragazzi,
devo fare delle prove sulla convenienza di utilizzare un algorimo di 
hashing per confrontare due valori.
In pratica devo confrontare due valori generici molto grandi (esempio 
può essere una sequenza di bit anche lunga vari MegaByte, e questo 
confronto deve avvenire per centinaia di iterazioni).
Ciò che voglio capire è se è più veloce confrontare due valori molto 
grandi o se è meglio fare un hash dei valori e confrontare gli hash.
Mi interessa sapere solo se i valori cambiano, ma non di quanto cambiano.
[Info Opzionale] Il campo di applicazione, per chi fosse ferrato in 
materia, sarebbe una tabu search dove, invece di memorizzare la 
caratteristica della mossa, memorizzo l'intera mossa.
Grazie a chiunque possa aiutarmi
Nicola

 Grazie a chiunque possa aiutarmi
Non ho riscontri pratici ma ad occhio direi che l'hashing comunque ti
analizza tutta la stringa e ne crea l'hash, forse equivale a confrontare i
due valori, con l'aggravante della creazione dell'hash.
Forse però potresti fare un algoritmo che ti confronti a blocchi i valori,
e se trova valori diversi significa che è cambiato. In questo modo potresti
confrontare solo una piccola parte dei valori, o al peggio tutto il file.
Se li hai in una stringa magari con la Len (che se non erro è memorizzata
all'inizio della stringa) vedi subito se sono di lunghezza uguale.
-- 
DBMS Firebird
VB6 + Ado

 due valori, con l'aggravante della creazione dell'hash.
Ciao Andrea,
ho provato a farmi un pezzo di codice per misurare le velocità.
Ho usato .NET 2003 (quindi non ho il controllo su ciò che succede, 
poichè è il framework a decidere cosa và analizzato prima).
Ho usato la lettura di un file di 430 KB circa e il valore viene messo 
in due stringhe uguali.
Cosa strana è che se confronto gli hash il tempo è di circa 20 volte 
minore rispetto al confronto diretto.
Lo stesso risultato lo ottengo sia se controllo prima gli hash e poi 
faccio il confronto diretto sia facendo il contrario (prima il confronto 
diretto e poi tra hash)
Ecco il codice che ho scritto, va messo in un form 
VB.NET
Imports System.IO
Public Class Form1
     Inherits System.Windows.Forms.Form
#Region " Codice generato da Progettazione Windows Form "
     Public Sub New()
         MyBase.New()
         'Chiamata richiesta da Progettazione Windows Form.
         InitializeComponent()
         'Aggiungere le eventuali istruzioni di inizializzazione dopo la 
chiamata a InitializeComponent()
     End Sub
     'Form esegue l'override del metodo Dispose per pulire l'elenco dei 
componenti.
     Protected Overloads Overrides Sub Dispose(ByVal disposing As Boolean)
         If disposing Then
             If Not (components Is Nothing) Then
                 components.Dispose()
             End If
         End If
         MyBase.Dispose(disposing)
     End Sub
     'Richiesto da Progettazione Windows Form
     Private components As System.ComponentModel.IContainer
     'NOTA: la procedura che segue è richiesta da Progettazione Windows 
Form.
     'Può essere modificata in Progettazione Windows Form.
     'Non modificarla nell'editor del codice.
     Friend WithEvents TextBox1 As System.Windows.Forms.TextBox
     Friend WithEvents Button1 As System.Windows.Forms.Button
     Friend WithEvents Button2 As System.Windows.Forms.Button
     <System.Diagnostics.DebuggerStepThrough()> Private Sub 
InitializeComponent()
         Me.TextBox1 = New System.Windows.Forms.TextBox
         Me.Button1 = New System.Windows.Forms.Button
         Me.Button2 = New System.Windows.Forms.Button
         Me.SuspendLayout()
         '
         'TextBox1
         '
         Me.TextBox1.Location = New System.Drawing.Point(8, 8)
         Me.TextBox1.Multiline = True
 
Me.TextBox1.Name
 = "TextBox1"
         Me.TextBox1.ScrollBars = System.Windows.Forms.ScrollBars.Vertical
         Me.TextBox1.Size = New System.Drawing.Size(496, 232)
         Me.TextBox1.TabIndex = 0
         Me.TextBox1.Text = ""
         '
         'Button1
         '
         Me.Button1.Location = New System.Drawing.Point(8, 248)
 
Me.Button1.Name
 = "Button1"
         Me.Button1.Size = New System.Drawing.Size(88, 24)
         Me.Button1.TabIndex = 1
         Me.Button1.Text = "Avvia"
         '
         'Button2
         '
         Me.Button2.Location = New System.Drawing.Point(432, 248)
 
Me.Button2.Name
 = "Button2"
         Me.Button2.Size = New System.Drawing.Size(72, 24)
         Me.Button2.TabIndex = 2
         Me.Button2.Text = "Chiudi"
         '
         'Form1
         '
         Me.AutoScaleBaseSize = New System.Drawing.Size(5, 13)
         Me.ClientSize = New System.Drawing.Size(512, 273)
         Me.ControlBox = False
         Me.Controls.Add(Me.Button2)
         Me.Controls.Add(Me.Button1)
         Me.Controls.Add(Me.TextBox1)
         Me.Name = "Form1"
         Me.Text = "Form1"
         Me.ResumeLayout(False)
     End Sub
#End Region
     Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As 
System.EventArgs) Handles Button2.Click
         Me.Close()
     End Sub
     Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As 
System.EventArgs) Handles Button1.Click
         Dim Testofile1, Testofile2 As String
         Dim i As Integer
         TextBox1.Text = TextBox1.Text & "Acquisisco i dati da un file 
di grosse dimensioni (3.2 Milioni di bit circa)." & vbCrLf & vbCrLf
         Dim SR As New StreamReader("fileprova.pdf")
         Testofile1 = SR.ReadToEnd()
         Testofile2 = Testofile1
         SR.Close()
         Dim t, th, t1, t2 As Int32
         TextBox1.Text = TextBox1.Text & "File Importato. Ora inizio il 
confronto (1000 Iterazioni)." & vbCrLf
         t = Environment.TickCount
         Dim numIterazioni As Integer
         numIterazioni = 1000
         'confronto diretto
         For i = 0 To numIterazioni
             If Testofile1 = Testofile2 Then
             End If
         Next
         t1 = Environment.TickCount
         'confronto con hashing
         th = Environment.TickCount
         For i = 0 To numIterazioni
             If Testofile1.GetHashCode = Testofile2.GetHashCode Then
             End If
         Next
         t2 = Environment.TickCount
         t1 = t1 - t
         t2 = t2 - th
         TextBox1.Text = TextBox1.Text & "Tempo necessario al confronto 
diretto: " & t1.ToString & " Millisecondi" & vbCrLf
         TextBox1.Text = TextBox1.Text & "Tempo necessario al confronto 
con hashing: " & t2.ToString & " Millisecondi" & vbCrLf & vbCrLf
         TextBox1.Text.GetHashCode()
     End Sub
End Class

         Next
Occhio che la String.GetHashCode così a occhio è un po' strana (in questi 
casi Reflector aiuta a capire cosa "sta sotto").
Io non me la cavo bene con i puntatori, ma vista così mi pare che legga 2 
byte sì e 2 no
Public Overrides Function GetHashCode() As Integer
      Dim text1 As Char*
      Fixed text1 = DirectCast(Me, Char*)
            Dim chPtr1 As Char* = text1
            Dim num1 As Integer = 352654597
            Dim num2 As Integer = num1
            Dim numPtr1 As Integer* = DirectCast(chPtr1, Integer*)
            Dim num3 As Integer = Me.Length
            Do While (num3 > 0)
                  num1 = ((((num1 << 5) + num1) + (num1 >> 27)) Xor 
numPtr1(0))
                  If (num3 <= 2) Then
                        Exit Do
                  End If
                  num2 = ((((num2 << 5) + num2) + (num2 >> 27)) Xor 
numPtr1(1))
                  numPtr1 = (numPtr1 + 2)
                  num3 = (num3 - 4)
            Loop
            Return (num1 + (num2 * 1566083941))
      End Fixed
End Function
Per avere un ashing un po' serio dovresti guardare la classe 
System.Security.Cryptography.MD5.
Poi, per le stringhe prova a dare un occhio ai vari Equals(), Compare() e 
CompareOrdinal() anzichè all'operatore = (non mi ricordo mai le differenze).
Ciao 

     End Function
bye

 ha scritto nel messaggio 
news:4556fa3b$0$9617$5fc...@news.tiscali.it...

Beh, l'MD5 non è certo famoso per le prestazioni, comunque  in questo modo 
hai il calo di prestazioni dovuto anche alle varie conversioni in stringa.
L'md5 puro, cioè l'array di 32 byte, magari evitando la creazione della 
classe md5 ogni volta.
Ciao 

 classe md5 ogni volta.
Si, comunque la portata del rallentamento è comunque notevole.
In realtà il mio voleva essere una sorta di proof of concept.
Ho cercato una soluzione ad un problema di ricerca operativa e possodire 
che, variando ed ottimizzando l'algoritmo di ha una velocità buona nel 
calcolo della tabu search.
Quindi ciò che mi interessava era sapere, per sommi capi, di quanto 
peggiora la velocità di esecuzione dell'algoritmo tabu search se volessi 
risparmiare memoria.
bye