Biblioteca de classes genéricas - bugs, descrição, perguntas, recursos de uso e sugestões - página 35

Novo comentário
 
Renat Fatkhullin:

Quase impossível e se se deparar com um, o acesso continua a ser super eficaz.

A colisão a qualquer nível de eficiência é má. Obrigado pela resposta. Terá isso em mente.

 
fxsaber:

A colisão a qualquer nível de eficiência é má. Obrigado pela sua resposta. Vou ter isso em mente.

Os hashmaps não estão, por definição, livres de colisões.

 
fxsaber #:

Pergunta sobre colisões. É possível entrar em colisão em tal caso?

Se tiverem sido produzidos 27.000 registos.

Receberá constantemente colisões, especialmente quando a colecção cresce (redimensiona). Uma vez que o haxixe é adicionalmente truncado ao número de gangues, e há sempre um número limitado deles (idealmente igual a um).

Conclusões:

1. Não é a estabilidade criptográfica da função hash que importa mapear, é a sua velocidade. A função do hash só precisa de proporcionar uma boa aleatoriedade e é isso.

2. O redimensionamento é melhor evitado por todos os meios. É o redimensionamento que causa a principal desvantagem, não as colisões da função hash. Sempre que possível, inicializar sempre a colecção com um número de artigos predefinido. Mesmo que não os conheça exactamente, dê um número aproximado - isso irá ajudar muito o algoritmo.

3. As colisões são um mecanismo de compactação regular. Através de colisões, é possível armazenar três registos com id, digamos, 159, 4'569'209, 29'459'876 na matriz de comprimento três, em vez de comprimento 30 000 000, mesmo que os dois últimos valores caiam ambos no bando com índice 2.

 
Vasiliy Sokolov #:

2. O redimensionamento é melhor evitado por todos os meios. É o redimensionamento, não as colisões da função hash, que é o principal inconveniente. Sempre que possível, inicializar a colecção com um número pré-definido de artigos. Mesmo que não os conheça exactamente, dê um número aproximado - será uma grande ajuda para o algoritmo.

Por favor, mostre pelo exemplo.

Até agora só utilizei isto.

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

Por favor, mostrem-me um exemplo.

Até agora só utilizei isto.

Quando criar uma colecção CHashMap, utilize um dos construtores que aceita o parâmetro de capacidade. Ver o meu artigo sobre o CDicionary para detalhes sobre o desempenho durante o redimensionamento. Há uma passagem completa deste algoritmo.

 

Encontrei um comportamento muito invulgar no 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

Parece que uma chave é supostamente adicionada, mas nada pode ser lido a partir dela. No entanto, assim que a chave é novamente adicionada, torna-se legível!

Isto é um BAG?


Se substituir o preço1,75141 no exemplo por outro, este funcionará correctamente.


Foi infernalmente difícil detectar este comportamento num código enorme sem depuração e criar um exemplo tão conciso.

 
Vasiliy Sokolov #:

Inicializar sempre que possível a colecção com um número pré-determinado de elementos. Mesmo que não os conheça exactamente, dê um número aproximado - será uma grande ajuda para o algoritmo.

No exemplo acima, tentei definir a capacidade através do construtor. A partir de um certo valor de capacidade, o exemplo começa a funcionar correctamente.

Mas penso que se trata de uma coincidência.

 
fxsaber #:

Encontrei um comportamento muito invulgar no CHashMap.


Parece que uma chave é supostamente adicionada, mas nada pode ser lido a partir dela. No entanto, assim que eu voltar a adicionar a chave, ela torna-se legível!

Isto é um BAG?


Se substituir o preço1,75141 no exemplo por outro, este funcionará correctamente.


Foi infernalmente difícil detectar este comportamento num código enorme sem depuração e criar um exemplo tão conciso.

Fixo, estará no lançamento de hoje.
 
MetaQuotes #:
Corrigido, estará no lançamento de hoje.

Obrigado! Vejo a edição.


 
fxsaber #:

No exemplo acima, tentei definir a capacidade através do construtor. A partir de um certo valor de capacidade, o exemplo começa a funcionar correctamente.

Mas penso que se trata de uma coincidência.

Sim, há uma falha sobre uma falha. Eu desaconselho vivamente a utilização de genéricos.

1...2829303132333435363738
Novo comentário
Razão: