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

Nuovo commento
 

Dal 6 dicembre 2017, la fornitura standard di MetaTrader 5 include le cosiddette classi generiche che implementano algoritmi efficienti per l'archiviazione e il recupero dei dati. Questo thread è stato creato per descrivere queste classi, esempi di lavoro con esse e suggerimenti per migliorarne il funzionamento.

Le classigeneriche sono speciali classi modello che possono memorizzare tipi di dati personalizzati. L'identificazione del tipo viene eseguita in fase di compilazione, con conseguenti prestazioni elevate.

Perché i generici? Di norma, i programmatori alle prime armi hanno familiarità con un solo tipo di collezione: un array. Ma ci sono molti compiti in cui lavorare con un array è inefficiente. Immaginiamo di avere un array composto da un milione di identificatori unici, ad esempio un migliaio di ordini. Come possiamo verificare se in questo migliaio di ordini c'è un ordine con il numero N? Se utilizziamo una delle classi generiche, questo compito può essere eseguito quasi istantaneamente, per un tempo costante, che non dipenderà dal numero di elementi tra cui avverrà la ricerca. Ci sono altri compiti in cui l'algoritmo corretto della collezione generica può essere più veloce dell'algoritmo inventato dal programmatore.

Algoritmi generici. Di seguito è riportata una tabella di classi generiche, con una breve descrizione di ciò che fanno:

ClasseDescrizione
CArrayList.Un array, con ripartizione automatica delle dimensioni. Permette di sfruttare un array senza dover controllare l'uscita da esso.
CHashMapUn insieme chiave-valore. Consente l'inserimento, il recupero e la ricerca efficiente di elementi in base alla loro chiave. La chiave deve essere unica. Ad esempio, CHashMap è in grado di trovare immediatamente un ordine con un numero specifico, se il numero è usato come chiave.
CHashSetUn insieme di elementi unici. Permette di fare tutte le stesse cose di CHashMap, ma non richiede una chiave. Gli elementi memorizzati in questo insieme non devono essere ripetuti. Consente inoltre la ricerca, il recupero e l'aggiunta istantanea di un elemento.
Elenco collegatoUn doppio elenco collegato. Consente di inserire ed eliminare facilmente gli elementi. Tuttavia, la ricerca dell'elemento desiderato richiede un tempo dipendente linearmente dal numero di elementi dell'elenco.
CQueueHeap. Organizza una coda di tipo FIFO
CStackPila. Organizza una coda di tipo LIFO
CRedAlbero neroRedBlackTree. Permette di inserire rapidamente (in tempo logaritmico) elementi, estrarli e trovarli. A differenza di CHashMap e CHashSet, consente di implementare in modo efficiente algoritmi di relazione aggiuntivi come more than, less than, between, ecc.
CSortedMapInsieme ordinato per chiave. Memorizza valori chiave-valore. In questo caso, la chiave è ordinata.
CSortedSetInsieme ordinato per valore. Memorizza un insieme ordinato di valori.

Più avanti continueremo a esaminare le caratteristiche di implementazione di queste classi.

 
Vasiliy Sokolov:

Immaginiamo di avere un array di un milione di identificatori unici, per esempio mille ordini. Come possiamo controllare se in questo migliaio di ordini c'è un ordine con il numero N? Se usiamo una delle classi generiche, questo compito può essere eseguito quasi istantaneamente, in un tempo costante, che non dipende dal numero di elementi che stiamo cercando.

Non conosco affatto l'argomento. Ma l'evidenziato suona illogico.

 

Sfortunatamente, la libreria è stata appena rilasciata ed è ancora grezza. Ho già trovato il primo errore in esso (evidenzierò gli errori per marker):

Errore in CSortedSet:

//+------------------------------------------------------------------+
//| Class CSortedSet<T>.                                             |
//| Usage: Represents a collection of objects that is maintained in  |
//|        sorted order.                                             |
//+------------------------------------------------------------------+
template<typename T>
class CSortedSet: public ISet<T>
  {
   ...
   bool              TryGetMin(T &min)    { return(m_tree.TryGetMin(min)); }
   bool              TryGetMax(T &max)    { return(m_tree.TryGetMin(max)); }
   ...
  }

Il metodo TryGetMax restituisce l'elemento minimo invece di quello massimo, così come TryGetMin

 
fxsaber:

... Ma l'evidenziato suona illogico.

Perché?

 
Vasiliy Sokolov:

Perché?

Fare gli hash, ordinandoli in ordine crescente. Ma la ricerca ci sarà comunque.

 
fxsaber:

Non conosco affatto l'argomento. Ma l'evidenziato suona illogico.

tempo medio O(1) peggiore O(n) e le prestazioni dipendono fortemente dall'hash.
 
fxsaber:

Fare hashish ...

Definiamo la terminologia. Niente è istantaneo. Qualsiasi operazione richiede tempo. Quando dico istantaneo, sto semplificando in modo che i programmatori inesperti mi capiscano. In senso stretto, ci sono diverse classi di complessità, le principali di cui ci occuperemo sono le seguenti:

  • Complessità costante cO(1).
  • Logaritmico: cO(log n).
  • Lineare: cO (n).
  • Algoritmi che richiedono un tempo di esecuzione non lineare.

Ho deliberatamente introdotto un segno c - come una specie di costante che si verifica quando si calcolano gli hash e altre manipolazioni tecniche. Ma in questo caso, la discussione sull'ottimizzazione ac costante è fuori tema di questo thread. Qui siamo interessati solo alle classi generiche e alla loro applicazione nella pratica.

 
fxsaber:

Fate degli hash, ordinateli in ordine crescente. Ma ci sarà una ricerca in entrambi i casi.

Combinatore:
Tempo medio O(1) peggiore O(n) e le prestazioni dipendono fortemente dall'hash.

+

p.s. Per illustrare, ecco un esempio in cui questa stessa performance scende a O(n) se non si gestisce correttamente CHashMap.

 

Suggerisco di semplificare i nomi, rendendoli più logici. Per esempio, CArrayList è un Array o una lista in mql5 un'implementazione di entrambi?

Tutto questo porta a domande e confusione. IMHO, dovremmo usare stl e non C# o Java. Oppure togliete la C davanti e lasciate che sia solo ArrayList.


Se si fanno nomi normali:

- la leggibilità salirà molte volte.

- avrete il vostro stile specifico di mql5.

- i principianti saranno in grado di navigare immediatamente nel codice (perché stl è incluso nello standard)

 
Vasiliy Sokolov:

...

Se potete fare degli esempi, per esempio sulla ricerca tra migliaia di offerte.
1234567891011121314151617181920212223242526272829303132333435363738
Nuovo commento
Motivazione: