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

[fxsaber]

Sergey Dzyublik:

Gli hash sono in media O(1) se la dimensione del dizionario al numero di elementi previsti lo permette.
E poi dipende dalle implementazioni di gestione delle collisioni, può essere attraverso una lista, forse più subhash....

La mia ignoranza terminologica ostacola il processo di approfondimento. Aspetterò degli esempi. Vorrei che fosse succinto e che arrivasse al punto: mandati, zecche e simili.

[Vladimir Karputov]

fxsaber:

La mia ignoranza terminologica ostacola il processo di approfondimento. Aspetterò degli esempi. Vorrei che fosse succinto e che arrivasse al punto: mandati, zecche e simili.

I mandati sono fuori questione. Sono interessato agli accordi.

[Sergey Dzyublik]

fxsaber:

L'ho letto sul wiki. Il tipo di caso in cui non si capisce affatto la logica del ragionamento intuitivo.

365 giorni è il limite della dimensione del dizionario
il numero di studenti in classe è il numero previsto di oggetti nella collezione
coincidenza di compleanni è una collisione

[fxsaber]

Sergey Dzyublik:

365 giorni è un limite alla dimensione del dizionario.
il numero di studenti in classe è il numero previsto di oggetti nella collezione
coincidenza di compleanni è una collisione

Grazie, questa definizione terminologica è più chiara. Non capisco proprio cosa abbia a che fare questo "paradosso" con l'argomento del thread?

[Sergey Dzyublik]

Sergey Dzyublik:

365 giorni è il limite della dimensione del dizionario
il numero di studenti in classe è il numero previsto di oggetti nella collezione
coincidenza di compleanni è una collisione

In questo esempio l'hash è il compleanno dello studente.
Abbiamo un armadio con 365 ripiani dove sono conservati i diari degli studenti.
Abbiamo messo ogni diario su uno scaffale corrispondente al compleanno dello studente.

Abbiamo bisogno del diario dell'allievo Petrov e sappiamo quando è nato.
Ora con la data di nascita in O(1) possiamo facilmente trovare il diario di Petrov, così come il diario di qualsiasi altro studente.
L'eccezione è quando due studenti hanno lo stesso compleanno - questo si chiama collisione.

Risolvere una collisione significa usare le informazioni extra per trovare quale di due o più riviste ci serve.
La risoluzione delle collisioni attraverso una lista è semplicemente passare attraverso tutte le voci della collisione una per una per trovare una corrispondenza. Strappa ogni diario e vedi di chi è.
Una sottovoce sta organizzando una tabella hash degli elementi coinvolti nella collisione, ma secondo un criterio diverso. Per esempio, per l'ora in cui lo studente è nato.

Se siete interessati all'argomento, vi suggerisco un corso su youtube di MailRu su algoritmi e strutture dati.

[fxsaber]

Sergey Dzyublik:

In questo esempio l'hash è il compleanno dello studente.
Abbiamo un armadio con 365 ripiani che contengono i diari degli studenti.
Mettiamo ogni diario sullo scaffale che corrisponde al compleanno dello studente.

Abbiamo bisogno del diario di Petrov e sappiamo quando è nato.
Ora con la data di nascita in O(1) possiamo facilmente trovare il diario di Petrov così come un altro studente.
L'eccezione è quando due studenti hanno lo stesso compleanno - questo si chiama collisione.

Risolvere una collisione significa usare le informazioni extra per scoprire quale di due o più riviste ci serve.
La risoluzione delle collisioni attraverso una lista è semplicemente passare attraverso tutte le voci della collisione una per una per trovare una corrispondenza. Strappa ogni diario e vedi di chi è.
Una sottovoce sta organizzando una tabella hash degli elementi coinvolti nella collisione, ma secondo un criterio diverso. Per esempio in base all'ora in cui uno studente è nato.

Se siete interessati all'argomento, vi suggerisco un corso su youtube di MailRu su algoritmi e strutture dati.

È così che me lo immaginavo all'inizio. Solo che non capisco quello evidenziato. Hash non è un indice, quindi potete trovarlo per offset in un array di puntatori. In ogni caso, dovremmo cercare nella lista. E questa è una ricerca binaria con un corretto ordinamento.

[Sergey Dzyublik]

fxsaber:

Questo è il modo in cui l'ho immaginato dall'inizio. Solo che non capisco quello evidenziato. Hash non è un indice, quindi potete trovarlo per offset in un array di puntatori. Devi cercare in una lista, però. E questa è una ricerca binaria con un corretto ordinamento.

Evidenziati sono refusi verbali)) E già corretto.
L'hash è un indice. È dato alla dimensione del dizionario.

Ogni ripiano ha la stessa altezza e dal numero del ripiano si può sapere esattamente a quale altezza cercarlo. O(1)

[Vasiliy Sokolov]

Il più semplice possibile sull'array associativo #1

Molti algoritmi presentati in Generic sono basati in un modo o nell'altro su un array associativo o un dizionario. È anche uno dei due algoritmi più utilizzati. Penso di essere vicino ad avere ragione quando dico che il 90% di tutti i compiti di programmazione sono coperti da array e dizionari. Prima di passare alla pratica, descriviamo il lavoro del dizionario nel modo più chiaro e diretto possibile, semplificando deliberatamente alcuni dettagli.

Mostreremo il dizionario su un esempio molto semplice: un elenco di parole regolari. Supponiamo di avere solo alcune parole, che iniziano tutte con lettere diverse dell'alfabeto:

string words[] = {"apple", "cat", "fog", "dog", "walk", "zero"};

L'alfabeto inglese contiene 26 caratteri. Creiamo un array di stringhe, di 26 elementi:

string dictionary[26];

Ora, se accettiamo di memorizzare le parole in indici corrispondenti alla loro prima lettera, otterremo un semplice dizionario. Indicizzeremo da zero. La parola 'mela' sarà memorizzata nel nostro dizionario all'indice 0, perché il carattere 'a' è la prima lettera dell'alfabeto, 'gatto' - all'indice 1, 'cane' - all'indice 3, nebbia - occuperà l'indice 4, passeggiata - indice 24 e zero - l'ultimo indice 25.

Si noti che gli indici da 5 a 23 non saranno utilizzati. Questo è un ulteriore spreco di memoria, ma possiamo accedere istantaneamente ad esempio alla parola "walk", perché sappiamo che se esiste, si trova all'indice 24.

Scriviamo il nostro primo dizionario vuoto:

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
string words[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   if(words[index] == NULL)
   {
      words[index] = word;
      return true;
   }
   return false;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   Add("apple");
   if(Contains("apple"))
      printf("Словарь содержит слово apple");
   else
      printf("Словарь не содержит слово apple");
  }
//+------------------------------------------------------------------+

Se vi aggiungiamo la parola "mela" e poi la troviamo, l'operazione di ricerca per accedere a questa parola sarà istantanea. Perché conosciamo in anticipo l'indice con cui si può trovare questa parola. Non ci possono essere altre varianti dell'indice, quindi non è necessario passare attraverso l'intera lista. Questa è più o meno la base di tutti i dizionari.

Nell'esempio seguente lo miglioreremo in modo che possa memorizzare parole che iniziano con la stessa lettera.

[Vasiliy Sokolov]

Il più semplice possibile sull'array associativo #2

A volte capita che parole diverse inizino con la stessa lettera dell'alfabeto. Se mettiamo "apple" nel nostro dizionario precedente, e poi proviamo a metterci "application", 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":

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words = WordsArray[index];
   if(words == NULL)
      return false;
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return true;
   return false;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words;
   if(WordsArray[index] == NULL)
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return false;
   words.Add(word);
   return true;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add("apple");
   Add("application");
   if(Contains("application"))
      printf("Словарь содержит слово application");
   else
      printf("Словарь не содержит слово 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). Nei dizionari reali questo è esattamente ciò che accade, le funzioni che vengono utilizzate sono a prova di collisione, quindi possiamo tranquillamente dire che l'accesso agli elementi di queste collezioni è molto veloce e quasi senza forza bruta.

[Реter Konow]

Vasiliy Sokolov:

Mantenere l'array associativo il più semplice possibile

Molti algoritmi che sono presentati in Generic sono in un modo o nell'altro basati sull'array associativo o sul dizionario. È anche uno dei due algoritmi più usati. Penso che sarei vicino alla verità se dicessi che il 90% di tutti i compiti di programmazione sono coperti da array e dizionari. Prima di passare alla pratica, descriviamo il lavoro del dizionario nel modo più chiaro e diretto possibile, semplificando deliberatamente alcuni dettagli.

Mostreremo il dizionario su un esempio molto semplice: un elenco di parole regolari. Supponiamo di avere poche parole, che iniziano tutte con lettere diverse dell'alfabeto:

L'alfabeto inglese contiene 26 caratteri. Creiamo un array di stringhe, di 26 elementi:

Ora, se accettiamo di memorizzare le parole in indici corrispondenti alla loro prima lettera, otterremo un semplice dizionario. Indicizzeremo da zero. La parola 'mela' sarà memorizzata nel nostro dizionario all'indice 0, perché il carattere 'a' è la prima lettera dell'alfabeto, 'gatto' - all'indice 1, 'cane' - all'indice 3, nebbia - occuperà l'indice 4, passeggiata - indice 24 e zero - l'ultimo indice 25.

Si noti che gli indici da 5 a 23 non saranno utilizzati. Questo è un ulteriore spreco di memoria, ma possiamo accedere istantaneamente ad esempio alla parola "walk", perché sappiamo che se esiste, si trova all'indice 24.

Scriviamo il nostro primo dizionario vuoto:

Se vi aggiungiamo la parola "mela" e poi la troviamo, l'operazione di ricerca per accedere a questa parola sarà istantanea. Perché conosciamo in anticipo l'indice con cui si può trovare questa parola. Non ci possono essere altre varianti dell'indice, quindi non è necessario cercare nell'intera lista. Questa è più o meno la base di tutti i dizionari.

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

Questa soluzione è perfetta. Tutto è il più semplice possibile. Solo funzioni, array e organizzazione corretta dei dati. Ecco di cosa sto parlando.