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

Nuovo commento
  
//+------------------------------------------------------------------+
//|                                              CompareFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IComparable.mqh>
//+------------------------------------------------------------------+
//| Compares two objects and returns a value indicating whether one  |
//| is less than, equal to, or greater than the other.               |
//+------------------------------------------------------------------+
int Compare(const bool x,const bool y)
  {
   if(x>y)
      return(1);
   else if(x<y)
      return(-1);
   else
      return(0);
  }


La funzione è dichiarata globalmente. Per questo motivo c'è un conflitto con il loro Confronto da parte degli utenti.

'Compare' - function already defined and has body

Per ridurre i conflitti di denominazione, l'autore potrebbe rendere tutte le funzioni ausiliarie globali generiche pubbliche-statiche-metodi?

 

fxsaber:

Per ridurre i conflitti di denominazione, l'autore potrebbe rendere tutte le funzioni ausiliarie globali generiche pubbliche-statiche-metodi?

Forum sul trading, sistemi di trading automatico e test di strategia

Bug del compilatore: 'operator=' - la struttura ha oggetti e non può essere copiata

fxsaber 2018.09.10 11:00 2018.09.10 10:00:13 RU
Alexey Navoykov:
Questo è per il momento. Se volete includere la libreria di qualcuno, scoprirete che l'autore scrive in modo "primitivo" come voi, usando gli stessi nomi di classi e funzioni.

Li inchioderò con le macro.

E le macro?
 
A100:
E le macro?

Non stavo parlando di me stesso.

 

Ho letto tutte le pagine della discussione ma non ho ancora capito come si usa?

Qualcuno può darmi qualche esempio?

 
Vladimir Pastushak:

Ho letto tutte le pagine della discussione ma non ho ancora capito come si usa?

Qualcuno può darmi qualche esempio?

Dimenticalo. Non si può usare così com'è ora. Usate invece il CObject + CDictionary standard. Per la maggior parte dei compiti, è sufficiente.

 
Vasiliy Sokolov:


ClasseDescrizione
CHashMapUn insieme chiave-valore. Permette di inserire, recuperare e cercare in modo efficiente gli elementi in base alla loro chiave. La chiave deve essere unica. Per esempio, CHashMap può trovare istantaneamente un ordine con un numero specificato, dove il numero è usato come chiave.

Domanda sul recupero di un valore per chiave. Nel codice della libreria, questo metodo si presenta così

//+------------------------------------------------------------------+
//| Find index of entry with specified key.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::FindEntry(TKey key)
  {
   if(m_capacity!=NULL)
     {
      //--- get hash code from key
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      //--- search pair with specified key
      for(int i=m_buckets[hash_code%m_capacity]; i>=0; i=m_entries[i].next)
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
            return(i);
     }
   return(-1);
  }

Gli strumenti di navigazione ME (ALT+G e CTRL+-) per fonte si rifiutano di funzionare in questa libreria. Perciò è molto difficile rintracciare la logica. In particolare, non ho ancora capito il valore iniziale nel ciclo evidenziato. Ma c'è l'intesa che se c'è una velocità, questo valore dovrebbe essere molto inferiore al numero di chiavi.


Per favore, chiarite l'idea, qual è la velocità raggiunta in questa funzione? L'overkill è chiaramente presente. Ma a quanto pare è breve per qualche motivo.


SZ Sono passato attraverso il mio debugger passo dopo passo. Tutto chiaro sull'esempio TKey = int: m_bucket[Array[i]] = i. Solo le collisioni quando Array[i] == Array[j] (i != j) non sono chiare.

 
fxsaber:

La domanda riguarda l'ottenimento del valore in base alla chiave. Nel codice della libreria questo metodo si presenta così
Per favore, chiarite l'idea, cosa rende questa funzione veloce? L'overshoot è ovviamente presente. Ma a quanto pare è breve per qualche motivo.

Una volta stavo rivedendo e descrivendo come funzionaCHashMap
 Devi cercare le voci, probabilmente in questo thread.

 

Forum sul trading, sistemi di trading automatico e test di strategie di trading

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

Sergey Dzyublik, 2017.12.11 13:41

Brevemente sull'attuale implementazione diCHashMap:

template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected:
   int               m_buckets[];                        
   Entry<TKey,TValue>m_entries[];
   int               m_count;
   int               m_free_list;
   int               m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool              m_delete_comparer;

     .................................

     .................................

  }

Per prima cosa, scopriamo cos'èEntry<TKey,TValue>.
Essenzialmente è un nodo come in CLinkedList che contiene:

- posto nel contenitore chiave e valore
- valore di hash nella cache per la chiave - hash_code
- next - "puntatore" alla prossimaEntry<TKey,TValue> con lo scopo di risolvere le collisioni attraverso la lista a connessione singola


m_entries[] - array di "celle" dove sono posizionati chiave e valore aggiunti, hash_code, next. La dimensione dell'array corrisponde alla Capacità.
m_count - specifica l'indice della prima cella inutilizzata in m_entries. Il valore iniziale è 0, che cresce fino alla capacità, il prossimo è la ricostruzione di tutti gli array con l'aumento della capacità e delle dimensioni di tutti gli array.
m_buckets[] - array di indici su m_entries[]. Il valore predefinito è -1. La dimensione della matrice corrisponde alla capacità.


Nessuna collisione, aggiungendo un valore unico al contenitoreCHashMap:

  1. Calcolare l'hash per chiave, ottenere l'hash_code
  2. Mettere chiave, valore, hash_code in m_entries[] per indice m_count. (next = -1 perché l'esempio non ha collisioni)
  3. Mettere in m_buckets[] per hash_code % (ArraySize(m_buckets)) il valore dell'indice dell'elemento appena aggiunto in m_entries[] (questo è m_count).
  4. Aumenta m_count di +1

Senza collisioni, ottenere il valore per chiave nel contenitoreCHashMap:

  1. Calcola l'hash dalla chiave, ottieni l'hash_code
  2. Da m_buckets[], per hash_code % (ArraySize(m_buckets)) ottenere il valore che è un indice dell'array m_entries[]
  3. Usando l'indice ottenuto m_buckets[hash_code % (ArraySize(m_buckets))], otteniamo il nostro valore dall'array m_entries[].

Risoluzione delle collisioni:

Per chiavi diverse può succedere che hash_code_key_1 % (ArraySize(m_buckets)) sia uguale a hash_code_key_2 % (ArraySize(m_buckets)) Questo è chiamato collisione.
Tutti gli elementi con collisione aggiunti a m_entries[] sono collegati attraverso la lista unificata con next (vedi strutturaEntry<TKey,TValue>)
E m_buckets[] punta sempre all'indice del primo elemento di testa in questa lista di collisione.
Non otteniamo una grande lista con collisioni, ma molte piccole liste.


Collisione, ottenere il valore per chiave nel contenitoreCHashMap:

  1. Sulla chiave calcoliamo l'hash, otteniamo hash_code
  2. Usando l'indice hash_code % (ArraySize(m_buckets)), ottenere il valore dall'array m_entries[]
  3. Possiamo vedere che il valore di next non è uguale a -1, il che indica che c'è una collisione
  4. Cammina attraverso la lista di voci singole costituita da elementi di m_entries[] e confronta il valore cercato e la chiave salvata per l'uguaglianza


Rimozione di un valore dal contenitoreCHashMap:

- Quando si cancella una cella in m_entries[], non viene fatta alcuna cancellazione; la cella viene marcata come libera e hash_code = -1.
- le celle libere formano la propria lista di celle libere (usando la stessa prossima da Entry<TKey,TValue>),m_free_list
- le celle libere sono prima usate per aggiungere nuovi valori al contenitore.
-m_free_count è usato per controllare il numero corrente di celle libere


Ricostruire la tabella hash (processo di aumento della capacità) :

- ricostruire solo quando la capacità è piena al 100%.
- la dimensione della capacità successiva viene presa dall'elenco:

const static int  CPrimeGenerator::s_primes[]=
  {
   3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
   1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
   17519,21023,25229,30293,36353,43627,52361,62851,75431,90523,108631,130363,156437,
   187751,225307,270371,324449,389357,467237,560689,672827,807403,968897,1162687,1395263,
   1674319,2009191,2411033,2893249,3471899,4166287,4999559,5999471,7199369
  };

- Gli array m_entries[] e m_buckets[] sono incrementati.
- m_buckets[] viene svuotato e riempito completamente, in base ai dati di m_entries[] (valore hash della chiave nella cache - hash_code)


Comportamento descritto da2017.12.11
 Attualmente, potrebbe aver aggiunto/modificato alcuni dettagli/coefficienti.

 
Sergey Dzyublik:

Una volta ho smontato e descritto come funziona laCHashMap
 Devi cercare le voci, probabilmente in questo thread.

L'ho trovato su

Forum sul trading, sistemi di trading automatico e test di strategia

Libreria di classi generiche - errori, descrizioni, domande, peculiarità d'uso e suggerimenti

Sergey Dzyublik, 2017.12.07 14:21


In questo esempio l'hash è il compleanno dello studente.
Abbiamo un armadio con 365 ripiani che contengono i diari degli studenti.
Abbiamo messo ogni diario sullo 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 in base all'ora di nascita dello studente.


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

Forum sul trading, sistemi di trading automatico e test di strategie di trading

Libreria di classi generiche - errori, descrizione, domande, peculiarità d'uso e suggerimenti

Sergey Dzyublik, 2017.12.08 14:40

Le basi di questo argomento sono per i pigri:
https://www.slideshare.net/mkurnosov/6-32402313

In realtà è molto più complicato e viene discusso nella letteratura pertinente o in buoni corsi di "algoritmi e strutture dati".


Grazie, il debug ha aiutato. Ci sono piccole liste per le collisioni. Ho letto il thread e sono rimasto inorridito. Risulta essere stato in tema...

 
Sergey Dzyublik:
Comportamento descritto dal2017.12.11

A partire da ora, potrebbe aver aggiunto/modificato alcuni dettagli/coefficienti.

Grazie mille! Mi ha aiutato molto la tua descrizione.

1...161718192021222324252627282930...38
Nuovo commento
Motivazione: