2013-05-12 9 views
12

Ho sentito che l'hashing (ovvero la conversione di una stringa o di un oggetto in un numero) viene utilizzato per le stringhe e tale perché è più facile confrontare i numeri rispetto alle stringhe. Se è vero, qual è la ragione di questo?Il confronto dei numeri è più veloce del confronto tra stringhe?

+0

I have a hunch - john = 12, johnny = 5. 12 = 1100 in binario 5 = 0101. Il confronto dei numeri (dopo la conversione in binario) è molto più veloce di. confrontando 4 caratteri di -john- (ogni carattere ha il proprio codice binario) e quindi rendendosi conto che non sono gli stessi. Tuttavia, se i nomi iniziano con un alfabeto diverso, l'hashing non sarebbe di aiuto. Ha senso ? Non sono sicuro se è corretto. –

+0

Le stringhe tendono ad essere molto più grandi dei numeri con cui solitamente si lavora in termini di quantità di memoria che occupano e il modo standard per confrontare le stringhe è vedere se hanno le stesse dimensioni e, in tal caso, confrontare la loro memoria per vedere se è diverso ovunque Semplici tipi interi "primitivi" possono essere memorizzati come bit complemento a 2 secondi: questo ha lo svantaggio di poter memorizzare solo valori da (circa) -2 miliardi a 2 miliardi (o così) nei loro 32 bit di spazio, ma ha il vantaggio che viene confrontata molta meno memoria. Questi confronti tra interi sono spesso eseguiti anche in un singolo ciclo del processore. – Yakk

risposta

25

Questo non è necessariamente il caso, ma probabilmente il caso più del tempo.

consideri la seguente situazione:

voglio mettere a confronto la stringa "mele" vs "arance". Se voglio solo determinare "mele" == "arance", devo solo confrontare il primo carattere di ogni stringa: 'a'! = 'O' => "mele"! = "Arance". Se eseguo l'hash della stringa e poi eseguo il confronto, è molto più lento in quanto devo analizzare entrambe le stringhe e inserirle in un algoritmo di hashing prima di confrontare gli interi risultanti.

Se, tuttavia, ho bisogno di fare questo confronto molte volte, e forse sto confrontando "arance" con "oranghi" molto, quindi se ho cancellato tutte le stringhe una volta e faccio il confronto di numeri interi molte volte, funzionerà più velocemente. Questo è il principio su cui si basa una mappa di hash.

Nota, tuttavia, che l'hashing di una stringa è utile per i confronti diretti degli uguali, non è possibile determinare se le stringhe sono lexigraficamente più grandi o meno l'una rispetto all'altra e quindi l'ordine delle stringhe non è possibile tramite il metodo di hashing. (Questo è il motivo per cui HashMap in Java non è ordinato).

+1

+1 per conferire un aspetto interessante alla domanda – SomeWittyUsername

0

Sì, ma questo non ha nulla a che fare con l'hashing.

Il confronto dei numeri comporta istruzioni hardware semplici che confrontano i bit.

Il confronto delle stringhe implica (a) iterare attraverso entrambe le stringhe finché non si trovano caratteri diversi (diversamente dai numeri, che sono di dimensione fissa) e (b) molto magia Unicode (stringhe diverse di lunghezze diverse possono effettivamente essere uguali e diverse i caratteri in diversi blocchi di codice si confrontano in modo diverso).


L'hash viene in genere utilizzato per convertire una stringa in un indice di array.

+0

Ho un'intuizione - john = 12, johnny = 5. 12 = 1100 in binario 5 = 0101. Confrontare i numeri (dopo la conversione in binario) è molto più veloce di. confrontando 4 caratteri di -john- (ogni carattere ha il proprio codice binario) e quindi rendendosi conto che non sono gli stessi. Tuttavia, se i nomi iniziano con un alfabeto diverso, l'hashing non sarebbe di aiuto. Ha senso ? Non sono sicuro se è corretto. –

+0

Dato che le possibili combinazioni di stringhe sono WAY superiori alla capacità media delle stringhe, ci saranno un sacco di stringhe che corrispondono allo stesso numero, quindi dovrai verificare se corrispondono e se lo fanno, esegui la vera e propria comprobazione. Inoltre, si interrompono tutti i problemi Unicode menzionati da SLaks. – SJuan76

+0

@SLaks Sospetto che la maggior parte dei tuoi numeri siano a dimensione fissa. :) Bignums richiederà iterazione, e "numeri" più elaborati (valutazione pigra, calcolo simbolico, real reals, ecc.) Possono essere piuttosto costosi da confrontare. Ma più seriamente, in quale mondo è "hashing" un termine per convertire una stringa in un indice di matrice? – Yakk

1

Il confronto dei numeri primitivi è decisamente più rapido rispetto al confronto delle stringhe perché è solo un'istruzione di computer mentre il confronto di stringhe in Java è un metodo. Ma l'hashing in Java viene utilizzato per un motivo diverso, Object.hashCode() viene utilizzato nelle tabelle hash per la ricerca rapida nelle raccolte.

8

Il confronto di due numeri è maggiore della velocità rispetto al confronto di due stringhe (che rappresentano gli stessi numeri). Confrontare due numeri richiede semplicemente il confronto di singoli bit e può essere fatto super veloce usando uno qualsiasi dei complementi di AND, XOR, 2, ecc.

Il confronto di due stringhe è molto lento e costoso. La maggior parte degli algoritmi richiede iterando attraverso l'intera stringa e facendo corrispondere ogni carattere.

Ad esempio, supponiamo di voler confrontare 9 con 12 (falso). Per il confronto numerico, supponiamo che l'algoritmo confronti un singolo bit. 9 = 1001 12 = 1100

Qui, l'algoritmo caso peggiore confronterà 4 bit.

Ora se rappresentiamo "9" e "12" come stringhe, verranno memorizzate nella memoria come 16 bit ciascuna (Richiamo: Java utilizza UTF-16 per rappresentare le stringhe in memoria) e devono essere passate a una stringa algoritmo di confronto. In effetti, funzione di confronto stringa effettiva di Java è qui sotto:

public boolean equals(Object anObject) { 
    if (this == anObject) { 
     return true; 
    } 
    if (anObject instanceof String) { 
     String anotherString = (String)anObject; 
     int n = count; 
     if (n == anotherString.count) { 
      char v1[] = value; 
      char v2[] = anotherString.value; 
      int i = offset; 
      int j = anotherString.offset; 
      while (n-- != 0) { 
       if (v1[i++] != v2[j++]) 
        return false; 
      } 
      return true; 
     } 
    } 
    return false; 
} 

Come si può vedere, c'è molto di più andando in giro per il confronto stringa.

+0

Anche la tua risposta mi piace. Per favore dimmi cos'è questo anotherString.count? non vedo .count ovunque nell'API.Intendevi String.length()? –

1

In generale, la maggior parte dei computer ha una singola istruzione per confrontare interi, long ecc. e al massimo un paio di cicli di istruzioni. Le stringhe vengono normalmente confrontate con una funzione/metodo di utilità (potrebbe esserci l'eccezione dispari a questa regola).

in Java per esempio una stringa è sostanzialmente rappresentata come

 /** The value is used for character storage. */ 
    private final char value[]; 

    /** The offset is the first index of the storage that is used. */ 
    private final int offset; 

    /** The count is the number of characters in the String. */ 
    private final int count; 

E il metodo equals è

if (this == anObject) { 
    return true; 
} 
if (anObject instanceof String) { 
    String anotherString = (String)anObject; 
    int n = count; 
    if (n == anotherString.count) { 
     char v1[] = value; 
     char v2[] = anotherString.value; 
     int i = offset; 
     int j = anotherString.offset; 
     while (n-- != 0) { 
      if (v1[i++] != v2[j++]) 
       return false; 
     } 
     return true; 
    } 
} 
return false; 

Il equivale metodo non sia questo == anObject e n == anotherString .count, entrambi i numeri interi sono comparabili, anche prima che inizi a confrontare i caratteri.Sta andando richiedere molto più tempo di una singola istruzione che un intero confrontare prende


La stringa C confrontare è più semplice/più veloce rispetto al Java equivalente ma conterrà una sorta di loop e istruzioni multiple per ogni passaggio attraverso il ciclo.

Questo richiederà più lungo di quello di istruzione che un intero Confronta richiede