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

Nuovo commento
 

Esegui questo

#include <Generic\ArrayList.mqh>
#include <Generic\HashMap.mqh>

CHashMap<int, int> MagicsByDeals;

#define  AMOUNT 1000000

template <typename T>
int Test( T &Object )
{
  int Res = 0;
  
  for(int i = 0; i < AMOUNT; i++)
  {
    int Tmp = 0;
    
    if (Object.TryGetValue(i, Tmp))    
      Res += Tmp;
  }
  
  return(Res);
}

#define  BENCH(A)                                                              \
{                                                                             \
  const ulong StartTime = GetMicrosecondCount();                              \
  A;                                                                          \
  Print("Time[" + #A + "] = " + (string)(GetMicrosecondCount() - StartTime)); \
} 

void OnStart()
{   
  CArrayList<int> CollectionList;
  CHashMap<int, int> CollectionHash;
  
  for(int i = 0; i < AMOUNT; i++)
  {      
    CollectionHash.Add(i, i);
    CollectionList.Add(i);
  }
  
  BENCH(Print(Test(CollectionList)));
  BENCH(Print(Test(CollectionHash)));
}


e ho ottenuto questo.

1783293664
Time[Print(Test(CollectionList))] = 24819
1783293664
Time[Print(Test(CollectionHash))] = 91270


CArrayList è più veloce della variante hash. Sono entrato nelle viscere di CArrayList, e c'è questo

template<typename T>
class CArrayList: public IList<T>
  {
protected:
   T                 m_items[];
   int               m_size;

Ora mi sento imbrogliato. CArrayList è risultato essere un wrapper per un normale array. Pensavo fosse una lista normale con puntatori Prev/Next, ma è così

template<typename T>
bool CArrayList::TryGetValue(const int index,T &value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- get value by index
      value=m_items[index];
      return(true);
     }
   return(false);
  }
 
fxsaber:
Oltre agli algoritmi effettivi per lavorare con le strutture, c'è il problema di scegliere il giusto contenitore in base alle specifiche del compito.
 
Combinatore:
A parte gli algoritmi di lavoro con le strutture in sé, c'è anche il problema di scegliere il contenitore giusto in base alle specifiche del compito.

Quindi l'interfaccia può essere la stessa per diverse implementazioni. Qualche delusione, non dall'interfaccia, ma dall'implementazione specifica - l'array. Rispetto all'hashish, è il cielo e la terra.

 
fxsaber:

Ora mi sento imbrogliato. CArrayList è risultato essere un wrapper per un normale array. Pensavo fosse una lista normale con puntatori Prev/Next, ma ecco qui


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

Algoritmi, metodi di soluzione, confronto delle prestazioni

Sergey Dzyublik, 2017.12.10 20:52


Che tipo di DBMS, cosa dici a un uomo che non sa nulla distrutture di dati.
Se non esiste il concetto di ArrayList (vettore dal C++), di cosa possiamo parlare qui.....


È più la tua disattenzione qui...
Leggi tutto l'elenco disponibile -https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList è un analogo di std::vector del C++
CLinkedList è molto probabilmente un analogo di std::list del C++

 
fxsaber:

Esegui questo

e ho ottenuto questo.

CArrayList è più veloce della variante hash. Sono entrato nelle viscere di CArrayList, e c'è questo

Ora mi sento imbrogliato. CArrayList è risultato essere un wrapper per un normale array. Pensavo fosse una lista normale con puntatori Prev/Next, ma sembrava così

Storicamente, List non è affatto un foglio - è un array. Quindi è tutto a posto. Se ottenete una lista in generico, probabilmente si chiamerà LinkedList o qualcosa del genere.

 
fxsaber:

Un po' di frustrazione, non con l'interfaccia, ma con l'implementazione specifica - l'array.

bene... questo contenitore è un array (cioè un analogo del vettore in C++), e l'array nativo di mql è molto buono, quindi arraylist è più un ripensamento, un po' più comodo da usare.
 

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

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

Sergey Dzyublik, 2017.12.09 01:12


Ci sono alcuni suggerimenti per un possibile miglioramento:

1) A mio modesto parere, l'implementazione contiene una scelta non del tutto corretta della capacità - sia la dimensione iniziale 3 che quelle successive quando si ricostruisce la tabella hash.
Sì, è corretto che un numero primo dovrebbe essere scelto per l'uniformità della distribuzione.
Tuttavia, l'implementazione di CPrimeGenerator non soddisfa le aspettative e contiene omissioni di numeri primi.
Lo scopo di un tale "generatore" è chiaro - fornire un fattore di incremento dell'ordine di 1,2 con la generazione automatica di numeri primi.
Tuttavia, non è un coefficiente troppo piccolo? In C++ per i vettori, il coefficiente è di solito 1,5-2,0, a seconda della libreria (poiché influenza fortemente la complessità media dell'operazione).
La via d'uscita potrebbe essere un coefficiente costante seguito dall'arrotondamento del numero al primo attraverso una ricerca binaria di una lista di numeri primi.
E una dimensione iniziale di 3 è troppo piccola, non viviamo nel secolo scorso.

2) Attualmente la tabella hash viene ricostruita (Resize) solo quando la capacità è piena al 100% (tutte le m_entries[] sono riempite).
A causa di questo, ci può essere una quantità significativa di collisioni per chiavi che non sono distribuite in modo molto uniforme.
Come opzione, considerate l'introduzione di un fattore di riempimento, che ridurrebbe il 100% del limite necessario per la ricostruzione della tabella hash.

1) Il fattore di crescita del volume (capacità) non è uguale a 1,2, il metodo CPrimeGenerator::ExpandPrime è usato per calcolare il nuovo volume in CHashMap:

int CPrimeGenerator::ExpandPrime(const int old_size)
  {
   int new_size=2*old_size;
   if((uint)new_size>INT_MAX && INT_MAX>old_size)
      return INT_MAX;
   else
      return GetPrime(new_size);
  }

In questo metodo, la vecchia dimensione della collezione viene moltiplicata per due, poi troviamo il numero semplice più vicino dall'alto per il valore risultante e lo restituiamo come nuovo volume.

Sul valore iniziale della capacità - sono d'accordo, è molto piccolo.

Ma d'altra parte ci sono sempre i costruttori, dove si può specificare esplicitamente la capacità iniziale:

class CHashMap: public IMap<TKey,TValue>
  {
public:
                     CHashMap(const int capacity);
                     CHashMap(const int capacity,IEqualityComparer<TKey>*comparer);
  }

Quindi non vedo molto senso di cambiare qualcosa qui.

2) L'aggiunta di un parametro di fattore di riempimento aiuterebbe davvero ad evitare le collisioni in alcuni casi. Il più probabile da implementare.

 
Roman Konopelko:

1) Il coefficiente di capacità non è uguale a 1,2, per calcolare il nuovo volume in CHashMap, si usa il metodo CPrimeGenerator::ExpandPrime:

In questo metodo, la vecchia dimensione della collezione viene moltiplicata per due, poi per il valore risultante troviamo il più vicino al numero primo superiore e lo restituiamo come nuovo volume.

Sul valore iniziale della capacità - sono d'accordo, è molto piccolo.

Ma d'altra parte ci sono sempre i costruttori, dove si può specificare esplicitamente la capacità iniziale:

Ecco perché non vedo alcuna ragione per cambiare qualcosa qui.

2) Aggiungere il parametro del fattore di riempimento aiuterà davvero ad evitare le collisioni in alcuni casi. Molto probabilmente sarà implementato.

Roman, credo che tu ti sia fatto un'idea sbagliata. Ora alcune classi non contengono nemmeno i metodi più necessari. Avete mai provato a usarli? Prendete CRedBlackTree, per esempio, la classica implementazione di un albero rosso-nero. Algoritmo abbastanza figo ma senza la possibilità di iterazione. Cosa vuoi dire con questo? Ci sono molte altre cose di cui potreste aver bisogno ma che nessuno si è preoccupato di implementare per qualche motivo. La roba di GetHashCode è orribile. Mi dispiace, ma non è al livello di MQ!

 
Vasiliy Sokolov:

Roman, non credo che tu stia facendo la cosa giusta. Ora alcune classi generiche non contengono nemmeno i metodi più necessari. Avete provato ad usarli? Prendiamo ad esempio CRedBlackTree - una classica implementazione di un albero rosso-nero. Algoritmo abbastanza figo ma senza la possibilità di iterazione. Cosa vuoi dire con questo? Ci sono molte altre cose di cui potreste aver bisogno ma che nessuno si è preoccupato di implementare per qualche motivo. La roba di GetHashCode è orribile. Mi dispiace, ma questo non è il livello di MQ!

Sono ben consapevole della necessità di iteratori per tutte le collezioni di modelli della libreria Genric, ma senza la possibilità di creare classi annidate e l'ereditarietà multipla dalle interfacce, non è possibile implementarle correttamente.

Vorrei sentire commenti più specifici su GetHashCode.

 
Roman Konopelko:

...

Per quanto riguarda GetHashCode, mi piacerebbe sentire osservazioni più specifiche.

Problema

Ovviamente, GetHashCode non può essere implementato correttamente in un ambiente MQL5 personalizzato. Questo perché non tutti gli oggetti sono accessibili. E mentre l'implementazione funziona bene per i membri primitivi come double int, per gli oggetti complessi (classi, strutture e persino enumerazioni) l'hash è calcolato per nome. Se abbiamo migliaia di CObjects o anche ENUM_something_that, allora CHashMap e CHashSet degenereranno in LinkedList:

#include <Generic\HashSet.mqh>
//+------------------------------------------------------------------+
//| Безобидное перечисление, но может быть класс или структура       |
//+------------------------------------------------------------------+
enum ENUM_NUMBER
{
   NUMBER_FIRTS,  // First
   NUMBER_SECOND, // Second
   NUMBER_THIRD   // Third
};
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
{
   CHashSet<ENUM_NUMBER> set_enum;
   for(int i = 0; i < 3; i++)
      set_enum.Add((ENUM_NUMBER)i);
   //-- Поздравляю, мы выродились в LinkedList.... 
   for(int i = 0; i < 3; i++)
   {
      //-- Здесь дикий оверхед по производительности, который тчательно скрывается...
      string is = set_enum.Contains((ENUM_NUMBER)i) ? " присутствует " : " отсутствует ";
      //...
   }
}

Non possiamo evitarlo perché tutto ciò che abbiamo a livello utente è il nome dell'oggetto:

//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value)
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>(value);// <-- Здесь будет получено название класса, структуры или перечисление
   if(equtable)
     {
      //--- calculate hash by specied method   
      return equtable.HashCode();
     }
   else
     {
      //--- calculate hash from name of object
      return GetHashCode(typename(value));
     }
  }

Quindi, gli hash di tutti gli oggetti di tipo complesso sono uguali tra loro e questo codice di ricerca qui comporta un'enumerazione di array completa:

//+------------------------------------------------------------------+
//| Determines whether a set contains the specified element.         |
//+------------------------------------------------------------------+
template<typename T>
bool CHashSet::Contains(T item)
  {
//--- check buckets
   if(ArraySize(m_buckets)!=0)
     {
      //--- get hash code for item      
      int hash_code=m_comparer.HashCode(item);
      //--- search item in the slots       
      for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
         if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
            return(true);
     }
   return(false);
  }

In effetti, questo è così critico che sconfigge il punto di usare tutti i generici alla radice. Il punto è che nella maggior parte dei casi è necessario associare o memorizzare oggetti complessi: enumerazioni, strutture o classi. Se avete bisogno di operare solo con tipi semplici, potete fare con qualcosa di più semplice.


Soluzione

Ovviamente, MQL5 è un linguaggio di programmazione personalizzato e sicuro di tipo che gira in una macchina virtuale interna. Qualcosa come Net. Questo significa che l'accesso necessario agli oggetti esiste ancora, ma ad un livello più sistematico. Quindi,forse scrivere la funzione di sistema GetHashCode con il prossimo prototipo:

int GetHashCode(void sample);

Come dovrebbe funzionare? In primo luogo, deve essere onnivoro e veloce. Dovrebbe dare una distribuzione uniforme. Per esempio:

int hash = GetHashCode(3);
// hash = 3

hash = GetHashCode(3.14159);
// hash = 2039485

enum EType{E1, E2, E3};
hash = GetHashCode(E2);
// hash = 2

class C1{};
C1* class1 = new C1();
hash = GetHashCode(class1);
//hash = 39203847

struct S1{};
S1 struct1;
hash = GetHashCode(struct1);
//hash = 83928342

Questa funzione potrebbe trovarsi nella sezione delle funzioni di sistema. Non vedo altre soluzioni.

s.e. Farò altri suggerimenti su interfacce, ereditarietà multipla e altre cose legacy del C++ un po' più tardi.
1...111213141516171819202122232425...38
Nuovo commento