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

Nuovo commento
 
Renat Fatkhullin:

Quasi impossibile e se ti imbatti in uno, l'accesso è ancora super efficace.

La collisione a qualsiasi livello di efficienza è un male. Grazie per la risposta. Lo terrò presente.

 
fxsaber:

La collisione a qualsiasi livello di efficienza è un male. Grazie per la vostra risposta. Lo terrò presente.

Le hashmap non sono per definizione prive di collisioni.

 
fxsaber #:

Domanda sulle collisioni. È possibile incorrere in una collisione in un caso del genere?

Se sono stati prodotti 27.000 dischi.

Avrete costantemente delle collisioni, specialmente quando la collezione cresce (si ridimensiona). Poiché l'hash è ulteriormente troncato al numero della banda, e c'è sempre un numero limitato di essi (idealmente uguale a uno).

Conclusioni:

1. Non è la stabilità crittografica della funzione hash che conta per la mappa, ma la sua velocità. La funzione di hash deve solo fornire una buona casualità ed è tutto.

2. Il ridimensionamento è meglio evitarlo con tutti i mezzi. È il ridimensionamento che causa il principale calo, non le collisioni della funzione hash. Quando possibile, inizializzate sempre la collezione con un numero prestabilito di elementi. Anche se non li conosci esattamente, dai un numero approssimativo - aiuterà molto l'algoritmo.

3. Le collisioni sono un meccanismo di compattazione regolare. Attraverso le collisioni, è possibile memorizzare tre record con id, diciamo, 159, 4'569'209, 29'459'876 in array di lunghezza tre, piuttosto che di lunghezza 30 000 000, anche se gli ultimi due valori cadono entrambi nella banda con indice 2.

 
Vasiliy Sokolov #:

2. Il ridimensionamento è meglio evitarlo con tutti i mezzi. È il ridimensionamento, non le collisioni delle funzioni hash, che è lo svantaggio principale. Quando possibile, inizializzate la collezione con un numero prestabilito di elementi. Anche se non li conosci esattamente, dai un numero approssimativo - è un grande aiuto per l'algoritmo.

Si prega di mostrare con un esempio.

Per ora uso solo questo.

//+------------------------------------------------------------------+
//| 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 #:

Per favore, mostratemi un esempio.

Per ora uso solo questo.

Quando create una collezione CHashMap, usate uno dei costruttori che accetta il parametro capacity. Vedi il mio articolo su CDicionary per i dettagli sulle prestazioni durante il ridimensionamento. C'è un walkthrough completo di questo algoritmo.

 

Ho trovato un comportamento molto insolito in CHashMap.

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

#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

Sembra che una chiave sia presumibilmente aggiunta, ma non si può leggere nulla da essa. Tuttavia, non appena aggiungo di nuovo la chiave, diventa leggibile!

È una BORSA?


Se sostituisci il prezzo1,75141 nell'esempio con un altro, funzionerà correttamente.


È stato infernalmente difficile rilevare questo comportamento in un codice enorme senza debugging e creare un esempio così conciso.

 
Vasiliy Sokolov #:

Inizializza sempre l'insieme con un numero predeterminato di elementi, quando possibile. Anche se non li conosci esattamente, dai un numero approssimativo: sarà di grande aiuto per l'algoritmo.

Nell'esempio sopra ho cercato di impostare la capacità attraverso il costruttore. A partire da un certo valore di capacità l'esempio inizia a funzionare correttamente.

Ma credo che questa sia una coincidenza.

 
fxsaber #:

Ho trovato un comportamento molto insolito in CHashMap.


Sembra che una chiave sia presumibilmente aggiunta, ma non si può leggere nulla da essa. Tuttavia, non appena la chiave viene aggiunta di nuovo, diventa leggibile!

È una BORSA?


Se sostituisci il prezzo1,75141 nell'esempio con un altro, funzionerà correttamente.


È stato infernalmente difficile rilevare questo comportamento in un codice enorme senza debugging e creare un esempio così conciso.

Corretto, sarà nella versione di oggi.
 
MetaQuotes #:
Corretto, sarà nella versione di oggi.

Grazie! Vedo la modifica.


 
fxsaber #:

Nell'esempio sopra, ho cercato di impostare la capacità tramite il costruttore. A partire da un certo valore di capacità, l'esempio inizia a funzionare correttamente.

Ma credo che questa sia una coincidenza.

Sì, c'è un glitch su glitch. Sconsiglio vivamente di usare Generic.

1...2829303132333435363738
Nuovo commento