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

Nuovo commento
 
Alexey Oreshkin:

Un grande esempio teorico! In pratica, qualcuno ha mai operato migliaia di transazioni?

p.s. non sto cercando di dimostrare che è una merda e che nessuno ne ha bisogno. Sto cercando di capire il valore per il trading reale. Non sono un teorico in generale, ma un puro praticante.

Non si tratta di 1000 scambi o solo di 10. Il punto è che scriviamo un codice breve, che funziona altrettanto efficacemente con 10 o 1000000..... operazioni.
 

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:

- inserito in un contenitore di chiavi e valori
- valore di hash nella cache per la chiave - hash_code
- next - "puntatore" alla prossimaEntry<TKey,TValue> per risolvere le collisioni attraverso la lista unidirezionale


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. Calcola l'hash per chiave, ottieni 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 a 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 per aumentare la 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)



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

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

Sergey Dzyublik, 2017.12.09 01:12

Ho fatto conoscenza con l'implementazione diCHashMap
 Onestamente, mi è piaciuto.


Ci sono diversi suggerimenti per un possibile miglioramento:

1) A mio modesto parere, l'implementazione contiene una selezione non proprio 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 tramite 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 le chiavi che non sono distribuite molto uniformemente.
Come opzione, considerate l'introduzione di un fattore di riempimento che riduce il 100% del limite necessario per eseguire una ricostruzione della tabella hash.


 
Alexey Oreshkin:

In pratica, qualcuno ha mai operato su migliaia di transazioni?

Sì, milioni di chiamate di storia in un solo passaggio sono praticate da molti.

 
Vasiliy Sokolov:

Sui forti ogni primo.

È chiaro.

L'invio di ordini tramite algoritmo hft e il loro ritiro per l'analisi sono cose diverse. Questi hash non sono necessari per l'invio, e non lo sono nemmeno per l'analisi, perché vengono analizzati in modo diverso.

Quindi, senza offesa. Avete anche bisogno di teoria.

 
Alexey Oreshkin:

È chiaro.

Inviare gli ordini con l'algoritmo hft e ritirarli dopo per l'analisi sono cose diverse. Non avete bisogno di questi hash per l'invio, e nemmeno per l'analisi, perché non è quello che viene analizzato.

Quindi, senza offesa. Abbiamo anche bisogno di teoria.


Non uso la lavastoviglie, uso una spugna.
Senza offesa alcuna. Le lavapiatti sono zoppe, a cosa servono.

 
Alexey Oreshkin:

È chiaro.

L'invio di ordini tramite l'algoritmo hft e il loro innalzamento in seguito per l'analisi sono cose diverse. Non hai bisogno di questi hash per inviarli e non ne hai bisogno per l'analisi, dato che analizziamo qualcos'altro dopo.

Quindi, senza offesa. Abbiamo anche bisogno di teoria.

Quali rancori? Continuate a scrivere le vostre stampelle.

 
Sergey Dzyublik:

Brevemente sull'attuale implementazione diCHashMap

Grazie, lo userò quando analizzerò il codice sorgente.

 
Vasiliy Sokolov:

Quali rancori? Continuate a scrivere le vostre stampelle.

Il fatto è che non sto usando il soggetto offerto qui, e sto cercando di capire se ho ragione o no. Sono soddisfatto degli array associativi ordinari, ma voglio sempre migliorare.
 
fxsaber:

Grazie, lo userò quando analizzerò le fonti.


Omesso il controllo dell'esistenza della chiave nel contenitore quando si aggiunge una nuova coppia chiave-valore, eseguita per prima.
Ma non è importante.

 
Affrontato un messaggio di errore causato dall'assenza di questo
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value) const

Per favore, sistemate qualcosa del genere in tutto il generico.

1...101112131415161718192021222324...38
Nuovo commento