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

Neuer Kommentar
 
Renat Fatkhullin:

Das ist fast unmöglich, und wenn man auf einen stößt, ist der Zugang trotzdem sehr effektiv.

Kollisionen auf jedem Effizienzniveau sind schlecht. Vielen Dank für die Antwort. Ich werde das im Hinterkopf behalten.

 
fxsaber:

Kollisionen auf jedem Effizienzniveau sind schlecht. Ich danke Ihnen für Ihre Antwort. Ich werde das im Hinterkopf behalten.

Hashmaps sind per Definition nicht kollisionsfrei.

 
fxsaber #:

Frage zu Kollisionen. Ist es möglich, in einem solchen Fall eine Kollision zu verursachen?

Wenn 27.000 Datensätze produziert worden sind.

Es kommt immer wieder zu Kollisionen, vor allem wenn die Sammlung wächst (Größenänderung). Da der Hash zusätzlich auf die Gangnummer gekürzt wird und es immer nur eine begrenzte Anzahl von ihnen gibt (im Idealfall gleich eins).

Schlussfolgerungen:

1. Für die Karte ist nicht die kryptografische Stabilität der Hash-Funktion wichtig, sondern ihre Geschwindigkeit. Die Hash-Funktion muss nur eine gute Zufälligkeit bieten und das war's.

2. Eine Größenänderung sollte auf jeden Fall vermieden werden. Es ist die Größenänderung, die den Hauptabfall verursacht, nicht die Kollisionen der Hash-Funktion. Wenn möglich, sollten Sie die Sammlung immer mit einer vorgegebenen Anzahl von Elementen initialisieren. Auch wenn Sie sie nicht genau kennen, geben Sie eine ungefähre Zahl an - das wird dem Algorithmus sehr helfen.

3. Kollisionen sind ein regelmäßiger Verdichtungsmechanismus. Durch Kollisionen ist es möglich, drei Datensätze mit den IDs 159, 4'569'209, 29'459'876 in einem Array der Länge 3 zu speichern, anstatt der Länge 30 000 000, selbst wenn die letzten beiden Werte beide in den Gang mit Index 2 fallen.

 
Vasiliy Sokolov #:

2. Eine Größenänderung sollte auf jeden Fall vermieden werden. Der größte Nachteil ist die Größenanpassung und nicht die Kollision der Hash-Funktionen. Wann immer es möglich ist, sollten Sie die Sammlung mit einer vorgegebenen Anzahl von Elementen initialisieren. Auch wenn Sie sie nicht genau kennen, geben Sie eine ungefähre Zahl an - das ist eine große Hilfe für den Algorithmus.

Bitte zeigen Sie das an einem Beispiel.

Ich verwende bisher nur diese.

//+------------------------------------------------------------------+
//| Adds the specified key and value to the map.                     |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Add(TKey key,TValue value);
//+------------------------------------------------------------------+
//| Gets the value associated with the specified key.                |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::TryGetValue(TKey key,TValue &value);
 
fxsaber #:

Bitte zeigen Sie mir ein Beispiel.

Ich verwende bisher nur diese.

Wenn Sie eine CHashMap-Sammlung erstellen, verwenden Sie einen der Konstruktoren, der den Parameter capacity akzeptiert. In meinem Artikel über CDicionary finden Sie Einzelheiten zur Leistung bei der Größenänderung. Es gibt einen vollständigen Überblick über diesen Algorithmus.

 

Ich habe ein sehr ungewöhnliches Verhalten in CHashMap gefunden.

// Демонстрация невозможности доступа по ключу после первого добавления.

#include <Generic\HashMap.mqh>

void OnStart()
{
  // Отсортированный массив неповторяющихся цен.
  const double Array[] =
{1.70682, 1.70691, 1.70700, 1.70709, 1.70710, 1.70717, 1.70721, 1.70742, 1.70749, 1.70752, 1.70757, 1.70766, 1.70768, 1.70769, 1.70771, 1.70773, 1.70774, 1.70777,
 1.70782, 1.70785, 1.70786, 1.70797, 1.70804, 1.70808, 1.70813, 1.70850, 1.70868, 1.70879, 1.70881, 1.70883, 1.70895, 1.70905, 1.70918, 1.70921, 1.70936, 1.70962,
 1.70966, 1.71022, 1.71027, 1.71047, 1.71056, 1.71080, 1.71081, 1.71093, 1.71096, 1.71109, 1.71112, 1.71119, 1.71120, 1.71127, 1.71128, 1.71135, 1.71136, 1.71138,
 1.71145, 1.71147, 1.71148, 1.71150, 1.71155, 1.71159, 1.71162, 1.71164, 1.71168, 1.71172, 1.71203, 1.71204, 1.71210, 1.71269, 1.71289, 1.71293, 1.71299, 1.71334,
 1.71337, 1.71343, 1.71357, 1.71358, 1.71367, 1.71371, 1.71374, 1.71380, 1.71402, 1.71410, 1.71414, 1.71425, 1.71426, 1.71427, 1.71429, 1.71430, 1.71446, 1.71474,
 1.71477, 1.71518, 1.71521, 1.71558, 1.71587, 1.71588, 1.71617, 1.71620, 1.71624, 1.71626, 1.71629, 1.71635, 1.71644, 1.71654, 1.71655, 1.71658, 1.71661, 1.71664,
 1.71689, 1.71700, 1.71712, 1.71718, 1.71727, 1.71752, 1.71769, 1.71775, 1.71780, 1.71782, 1.71786, 1.71792, 1.71795, 1.71797, 1.71798, 1.71801, 1.71815, 1.71827,
 1.71832, 1.71835, 1.71841, 1.71869, 1.71895, 1.71908, 1.71951, 1.71984, 1.71992, 1.72008, 1.72086, 1.72132, 1.72147, 1.72204, 1.72208, 1.72212, 1.72215, 1.72227,
 1.72230, 1.72233, 1.72234, 1.72336, 1.72374, 1.72378, 1.72381, 1.72405, 1.72454, 1.72464, 1.72477, 1.72488, 1.72541, 1.72553, 1.72562, 1.72588, 1.72625, 1.72651,
 1.72653, 1.72671, 1.72679, 1.72685, 1.72720, 1.72783, 1.72849, 1.72852, 1.72854, 1.72925, 1.72927, 1.72938, 1.72953, 1.72956, 1.72960, 1.72970, 1.72975, 1.72979,
 1.72996, 1.73014, 1.73028, 1.73034, 1.73050, 1.73056, 1.73084, 1.73085, 1.73119, 1.73137, 1.73176, 1.73278, 1.73328, 1.73337, 1.73344, 1.73345, 1.73362, 1.73377,
 1.73385, 1.73399, 1.73401, 1.73405, 1.73425, 1.73432, 1.73445, 1.73446, 1.73447, 1.73451, 1.73458, 1.73468, 1.73491, 1.73512, 1.73515, 1.73516, 1.73537, 1.73545,
 1.73553, 1.73580, 1.73581, 1.73598, 1.73611, 1.73630, 1.73635, 1.73643, 1.73658, 1.73678, 1.73694, 1.73695, 1.73698, 1.73712, 1.73713, 1.73721, 1.73746, 1.73748,
 1.73750, 1.73751, 1.73781, 1.73782, 1.73789, 1.73821, 1.73843, 1.73845, 1.73854, 1.73857, 1.73858, 1.73861, 1.73874, 1.73892, 1.74003, 1.74060, 1.74062};

  CHashMap<double, int> Index; // Будем по double-ключу хранить int-значения.
  
  for (int i = ArraySize(Array) - 1; i >= 0; i--)
    Index.Add(NormalizeDouble(Array[i], 5), 0); // Каждую цену массива используем в качестве ключа.
    
  // Все это было подготовкой, чтобы продемонстрировать поведение ниже.
  
  const double Price = 1.75141; // Берем новую цену.
  
  if (Index.Add(Price, 0)) // Если получилось добавить ее в качестве ключа.
  {
    int Value = 0;

    Print(Index.TryGetValue(Price, Value)); // (false) Проверяем, получается ли посмотреть данные по этому ключу.
    
    if (Index.Add(Price, 0)) // Пробуем повторно добавить в качестве ключа
      Print(Index.TryGetValue(Price, Value)); // (true) Проверяем, получается ли посмотреть данные по этому ключу.
  }
}


false
true

Es scheint so, als ob ein Schlüssel hinzugefügt wird, aber es kann nichts daraus gelesen werden. Sobald ich jedoch den Schlüssel wieder hinzufüge, wird er lesbar!

Ist das ein BAG?


Wenn Sie den Preis1,75141 im Beispiel durch einen anderen ersetzen, funktioniert er korrekt.


Es war höllisch schwierig, dieses Verhalten in einem riesigen Code ohne Debugging zu erkennen und ein solch prägnantes Beispiel zu erstellen.

 
Vasiliy Sokolov #:

Initialisieren Sie die Sammlung nach Möglichkeit immer mit einer vorgegebenen Anzahl von Elementen. Auch wenn Sie sie nicht genau kennen, geben Sie eine ungefähre Zahl an - das wird dem Algorithmus eine große Hilfe sein.

In dem obigen Beispiel habe ich versucht, die Kapazität über den Konstruktor festzulegen. Ab einem bestimmten Kapazitätswert beginnt das Beispiel korrekt zu funktionieren.

Aber ich glaube, das ist ein Zufall.

 
fxsaber #:

Ich habe ein sehr ungewöhnliches Verhalten in CHashMap gefunden.


Es scheint so, als ob ein Schlüssel hinzugefügt wird, aber es kann nichts daraus gelesen werden. Sobald der Schlüssel jedoch wieder hinzugefügt wird, ist er lesbar!

Ist das ein BAG?


Wenn Sie den Preis1,75141 im Beispiel durch einen anderen ersetzen, funktioniert er korrekt.


Es war höllisch schwierig, dieses Verhalten in einem riesigen Code ohne Debugging zu erkennen und ein solch prägnantes Beispiel zu erstellen.

Behoben, wird in der heutigen Version enthalten sein.
 
MetaQuotes #:
Korrigiert, wird in der heutigen Version enthalten sein.

Ich danke Ihnen! Ich sehe die Bearbeitung.


 
fxsaber #:

In dem obigen Beispiel habe ich versucht, die Kapazität über den Konstruktor festzulegen. Ab einem bestimmten Kapazitätswert beginnt das Beispiel korrekt zu funktionieren.

Aber ich glaube, das ist ein Zufall.

Ja, es gibt eine Störung nach der anderen. Ich würde dringend davon abraten, Generika zu verwenden.

1...2829303132333435363738
Neuer Kommentar