Libreria di classi generiche - bug, descrizione, domande, caratteristiche d'uso e suggerimenti - pagina 6

Nuovo commento
 
Vasiliy Sokolov:

Succede che diverse parole iniziano con la stessa lettera dell'alfabeto. Se mettiamo "mela" nel nostro dizionario precedente, e poi proviamo a metterci "applicazione", non funzionerà. L'indice 0 sarà occupato dalla parola mela. In questo caso si parla di una collisione della funzione hash. La nostra funzione hash è molto semplice - restituisce il numero del primo carattere della parola, quindi le collisioni in questa funzione saranno molto frequenti. Per memorizzare diverse parole che iniziano con la stessa lettera, faremo un'addizione: memorizzeremo gli elementi non in array, ma in array di array. In questo caso, l'indice 0 conterrà un altro array con due parole: "apple" e "application":

Ora il nostro dizionario memorizza parole che iniziano anche con la stessa lettera. Ma il costo di accesso alle parole con la stessa prima lettera aumenta. Perché ora abbiamo bisogno di una ricerca completa di tutte le parole che iniziano con 'a' per scoprire se la parola 'applicazione' è nel dizionario o no. Se la nostra funzione hash dovesse produrre numeri diversi anche se le parole differiscono di un solo carattere, allora la probabilità di provare parole con gli stessi indici tenderebbe a zero, e l'accesso a un elemento arbitrario tenderebbe a o(1). Questo è esattamente ciò che accade nei dizionari reali e le funzioni che vi sono utilizzate sono a prova di collisione, quindi possiamo sicuramente dire che l'accesso agli elementi in queste collezioni è molto veloce e non ha quasi nessuna ricerca.

Cercherò di fornire la mia soluzione a questo esempio. Senza puntatori. Un po' più tardi.
 

Recentemente ho letto un libro sull'argomento. Si chiama"Rattling Algorithms". Tutto è esposto molto chiaramente, con esempi.

 
Vasiliy Sokolov:

Nel prossimo esempio lo miglioreremo in modo che possa memorizzare parole che iniziano con la stessa lettera.

Per favore, scrivete in modo succinto, senza intestazioni o entità inutili.

Per esempio, questo

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}

potrebbe essere scritto in modo molto più chiaro.

bool Contains(string word)
{
   return words[word[0]-'a'] != NULL;
}


E ancora questo codice potrebbe funzionare diversamente per MT4/5 perché in MT4 l'array è inizializzato con valori NULL, e in MT5 potrebbe essere spazzatura.

 
fxsaber:

Per favore, scrivete in modo succinto, senza il casino dei cappelli e delle entità superflue.

...


Categoricamente CONTRO! Il codice dovrebbe preferibilmente essere scritto per intero. Guardate tutti i codici MQ - ci sono "tappi" ovunque. Questo è lo standard.


fxsaber:

...

Eppure questo codice per MT4/5 potrebbe funzionare diversamente perché in MT4 l'array è inizializzato con valori NULL, e in MT5 potrebbe essere spazzatura.


Cosa ha a che fare questo con il vecchio terminale? Se siete pigri e usate ancora quello vecchio, questo è un problema vostro. La comunità non dovrebbe rallentare a causa di questi fannulloni.

 
Vladimir Karputov:

Guardate tutti i codici MQ - ci sono 'tappi' ovunque. Questo è lo standard.

Fanculo lo standard, qui è importante l'essenza, non lo stile che prende il 50% del codice.

 
fxsaber:

Al diavolo lo standard, è l'essenza che conta, non lo stile che occupa il 50% del codice.


Il compito principale del forum è l'EDUCAZIONE. Quindi il codice dovrebbe essere espanso e chiaro con la massima approssimazione possibile alla norma.

 
Vasiliy Sokolov:

Questo è esattamente ciò che accade nei dizionari reali; le funzioni utilizzate sono resistenti alle collisioni, quindi possiamo dire che l'accesso agli elementi di queste collezioni è molto veloce e quasi senza overshoot.

Cioè per ogni compito è necessario trovare una via di mezzo tra la dimensione del dizionario (RAM) e la complessità computazionale della funzione hash (CPU).

 
Vladimir Karputov:

Lo scopo principale del forum è quello di educare. Pertanto, il codice dovrebbe essere ampliato e compreso

questo è sufficiente.

il più vicino possibile allo standard.

Potete inserire le vostre intestazioni. A100 ha pubblicato centinaia di rapporti nella SD senza tappi - questo è lo standard! Perché l'essenza è ciò che conta, non l'orpello.

 
C'è una soluzione. Tuttavia, per preservare temporaneamente l'intrigo, vorrei postare qui l'eseguibile. Inoltre, persone capaci confronteranno le prestazioni della mia soluzione e la soluzione fornita dall'autore di cui sopra. Mi chiedo quale funzioni più velocemente.
File:
Dictionary.ex5  10 kb
 
ReTeg Konow:
C'è una soluzione. Tuttavia, per mantenere temporaneamente vivo l'intrigo, vorrei pubblicare qui l'estratto. Inoltre, persone capaci confronteranno le prestazioni della mia soluzione e la soluzione fornita dall'autore di cui sopra. Mi chiedo quale funzioni più velocemente.
È necessario eseguire l'eseguibile. Apparirà un campo di input. Poi, puoi digitare diverse parole. Se c'è una corrispondenza, la stampante ti avviserà che la parola è nel dizionario. Se non c'è una parola, ti verrà notificato che la parola è stata aggiunta al dizionario.
12345678910111213...38
Nuovo commento