Generische Klassenbibliothek - Bugs, Beschreibung, Fragen, Nutzungsmöglichkeiten und Vorschläge - Seite 17

Neuer Kommentar
 
Alexey Oreshkin:

Ein großartiges theoretisches Beispiel! Hat jemand in der Praxis schon einmal Tausende von Transaktionen durchgeführt?

P.S. Ich versuche nicht zu beweisen, dass es Quatsch ist und niemand es braucht. Ich versuche, den Wert für den realen Handel zu verstehen. Ich bin im Allgemeinen kein Theoretiker, sondern ein reiner Praktiker.

Es geht nicht um 1000 Geschäfte oder nur 10. Der Punkt ist, dass wir einen kurzen Code schreiben, der gleichermaßen effektiv mit 10 oder 1000000..... Geschäften funktioniert.
 

Kurzer Überblick über die aktuelle Implementierung vonCHashMap:

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;

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

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

  }

Zunächst wollen wir herausfinden, wasEntry<TKey,TValue> ist.
Im Wesentlichen ist es ein Knoten wie in CLinkedList, der enthält:

- in einem Schlüssel- und Wertecontainer platziert
- zwischengespeicherter Hash-Wert für den Schlüssel - hash_code
- next - "Zeiger" auf den nächstenEintrag<TKey,TValue> zur Auflösung von Kollisionen durch eine Einwegliste


m_entries[] - Array von "Zellen", in denen der hinzugefügte Schlüssel und Wert, Hash_code, next abgelegt werden. Die Größe des Arrays entspricht der Kapazität.
m_count - gibt den Index der ersten unbenutzten Zelle in m_entries an. Der Anfangswert ist 0, er wächst bis zur Kapazität, dann werden alle Felder mit zunehmender Kapazität und Größe aller Felder neu aufgebaut.
m_buckets[] - Index-Array auf m_entries[]. Der Standardwert ist -1. Die Größe des Arrays entspricht der Kapazität.


Keine Kollision, Hinzufügen eines eindeutigen Wertes zumCHashMap-Container:

  1. Hash nach Schlüssel berechnen, Hash_code ermitteln
  2. Schlüssel, Wert, Hash_code in m_entries[] nach Index m_count eintragen. (next = -1, da das Beispiel keine Kollisionen aufweist)
  3. In m_buckets[] durch hash_code % (ArraySize(m_buckets)) den Indexwert des soeben in m_entries[] hinzugefügten Elements eintragen (dies ist m_count).
  4. m_count um +1 erhöhen

Ohne Kollisionen, Wert nach Schlüssel imCHashMap-Container erhalten:

  1. Hash aus Schlüssel berechnen, Hash_code erhalten
  2. Von m_buckets[], durch hash_code % (ArraySize(m_buckets)) den Wert erhalten, der ein Index des Arrays m_entries[] ist
  3. Verwenden Sie den erhaltenen Index m_buckets[hash_code % (ArraySize(m_buckets))], um unseren Wert aus dem Array m_entries[] zu erhalten.

Kollisionsauflösung:

Bei unterschiedlichen Schlüsseln kann es vorkommen, dass hash_code_key_1 % (ArraySize(m_buckets)) gleich hash_code_key_2 % (ArraySize(m_buckets)) ist. Dies nennt man eine Kollision.
Alle Elemente mit Kollision, die zu m_entries[] hinzugefügt werden, werden durch die einbindige Liste mit next verknüpft (siehe StrukturEntry<TKey,TValue>)
Und m_buckets[] zeigt immer auf den Index des ersten Kopfelements in dieser Kollisionsliste.
Wir erhalten nicht eine große Liste mit Kollisionen, sondern viele kleine Listen.


Kollision, Wert nach Schlüssel imCHashMap-Container erhalten:

  1. Auf dem Schlüssel berechnen wir den Hash, erhalten hash_code
  2. Mit dem Index hash_code % (ArraySize(m_buckets)) den Wert aus dem Array m_entries[] holen
  3. Wir sehen, dass der Wert von next ungleich -1 ist, was bedeutet, dass es eine Kollision gibt
  4. Die aus den Elementen von m_entries[] bestehende Liste mit einem Eintrag durchgehen und den gesuchten Wert und den gespeicherten Schlüssel auf Gleichheit vergleichen


Entfernen eines Wertes aus demCHashMap-Container:

- Beim Löschen einer Zelle in m_entries[] wird keine Löschung vorgenommen; die Zelle wird als frei markiert und hash_code = -1.
- freie Zellen bilden ihre eigene Liste von freien Zellen (unter Verwendung der gleichen nächsten von Entry<TKey,TValue>),m_free_list
- freie Zellen werden zuerst verwendet, um neue Werte zum Container hinzuzufügen.
-m_free_count wird verwendet, um die aktuelle Anzahl der freien Zellen zu kontrollieren


Hash-Tabelle neu aufbauen (Verfahren zur Erhöhung der Kapazität) :

- nur dann wiederherstellen, wenn die Kapazität zu 100 % gefüllt ist.
- Die nächste Kapazitätsgröße wird der Liste entnommen:

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
  };

- Die Arrays m_entries[] und m_buckets[] werden inkrementiert.
- m_buckets[] wird auf der Grundlage der Daten aus m_entries[] (zwischengespeicherter Hash-Wert für den Schlüssel - hash_code) geleert und wieder vollständig aufgefüllt



Forum zum Thema Handel, automatisierte Handelssysteme und Strategietests

Generic Class Library - Bugs, Beschreibung, Fragen, Verwendung und Vorschläge

Sergey Dzyublik, 2017.12.09 01:12

Habe mich mit derCHashMap-Implementierung vertraut gemacht
Ehrlich gesagt, ich mochte sie.


Es gibt mehrere Vorschläge für mögliche Verbesserungen:

1) Meiner bescheidenen Meinung nach enthält die Implementierung eine nicht ganz korrekte Auswahl der Kapazität - sowohl der anfänglichen Größe 3 als auch der nachfolgenden beim Wiederaufbau der Hashtabelle.
Ja, es ist richtig, dass für eine gleichmäßige Verteilung eine Primzahl gewählt werden sollte.
Die Implementierung von CPrimeGenerator entspricht jedoch nicht den Erwartungen und enthält Auslassungen von Primzahlen.
Der Zweck eines solchen "Generators" ist klar: Er soll einen Steigerungsfaktor in der Größenordnung von 1,2 mit automatischer Generierung von Primzahlen liefern.
Aber ist dieser Koeffizient nicht zu klein? In C++ für Vektoren beträgt der Koeffizient normalerweise 1,5-2,0, je nach Bibliothek (da er die durchschnittliche Komplexität der Operation stark beeinflusst).
Der Ausweg könnte ein konstanter Koeffizient sein, gefolgt von einer Rundung der Zahl auf eine Primzahl über eine binäre Suche in einer Liste von Primzahlen.
Und eine Anfangsgröße von 3 ist zu klein, wir leben nicht im letzten Jahrhundert.

2) Derzeit wird die Hash-Tabelle nur dann neu aufgebaut (Resize), wenn die Kapazität zu 100% voll ist (alle m_entries[] sind gefüllt).
Aus diesem Grund kann es bei nicht sehr gleichmäßig verteilten Schlüsseln zu einer erheblichen Anzahl von Kollisionen kommen.
Als Option könnte man die Einführung eines Füllfaktors in Erwägung ziehen, der 100 % um den notwendigen Grenzwert für den Neuaufbau einer Hash-Tabelle reduziert.


 
Alexey Oreshkin:

Hat jemand in der Praxis schon einmal mit Tausenden von Transaktionen gearbeitet?

Ja, Millionen von Geschichtsaufrufen in einem Durchgang werden von vielen praktiziert.

 
Vasiliy Sokolov:

Auf Forts jeden ersten.

Das ist klar.

DieÜbermittlung von Aufträgen durch den hft-Algorithmus und ihre Abholung zur Analyse sind zwei verschiedene Dinge. Diese Hashes werden für den Versand nicht benötigt und auch nicht für die Analyse, da sie auf andere Weise ausgewertet werden.

Also, nichts für ungut. Sie brauchen auch Theorie.

 
Alexey Oreshkin:

Das ist klar.

Die Übermittlung von Aufträgen durch den hft-Algorithmus und die spätere Abholung zur Analyse sind unterschiedliche Dinge. Sie brauchen diese Hashes nicht zum Senden und auch nicht zur Analyse, denn das ist nicht das, was analysiert wird.

Also, nichts für ungut. Wir brauchen auch Theorie.


Ich benutze keinen Geschirrspüler, sondern einen Schwamm.
Nichts für ungut. Geschirrspüler sind lahm, wozu sind sie da?

 
Alexey Oreshkin:

Das ist klar.

Die Übermittlung von Aufträgen durch den hft-Algorithmus und die spätere Erhebung zur Analyse sind zwei verschiedene Dinge. Sie brauchen diese Hashes nicht, um sie einzureichen, und Sie brauchen sie auch nicht für die Analyse, da wir anschließend etwas anderes analysieren.

Also, nichts für ungut. Wir brauchen auch Theorie.

Welcher Groll? Schreiben Sie weiter an Ihren Krücken.

 
Sergey Dzyublik:

Kurz über die aktuelle Implementierung vonCHashMap

Danke, ich werde es beim Parsen von Quellcode verwenden.

 
Vasiliy Sokolov:

Welcher Groll? Schreiben Sie weiter an Ihren Krücken.

Die Sache ist die, dass ich das hier angebotene Thema nicht verwende, und ich versuche zu verstehen, ob ich Recht habe oder nicht. Ich bin mit gewöhnlichen assoziativen Arrays zufrieden, aber ich will immer besser werden.
 
fxsaber:

Danke, ich werde sie beim Parsen der Quellen verwenden.


Beim Hinzufügen eines neuen Schlüssel-Wert-Paares wurde nicht geprüft, ob der Schlüssel im Container vorhanden ist, sondern zuerst ausgeführt.
Aber das ist nicht wichtig.

 
Es wurde eine Fehlermeldung angezeigt, die durch das Fehlen dieser
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value) const

Bitte bringen Sie so etwas in Generic unter.

1...101112131415161718192021222324...38
Neuer Kommentar