FórumSeções

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

Novo comentário 
//+------------------------------------------------------------------+
//|                                              CompareFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IComparable.mqh>
//+------------------------------------------------------------------+
//| Compares two objects and returns a value indicating whether one  |
//| is less than, equal to, or greater than the other.               |
//+------------------------------------------------------------------+
int Compare(const bool x,const bool y)
  {
   if(x>y)
      return(1);
   else if(x<y)
      return(-1);
   else
      return(0);
  }


A função é declarada globalmente. Por esta razão, existe um conflito com a sua Comparação pelos utilizadores.

'Compare' - function already defined and has body

Para reduzir os conflitos de nomes, poderia o autor tornar públicas todas as funções genéricas auxiliares globais?

fxsaber:

Para reduzir os conflitos de nomes, poderia o autor tornar públicas todas as funções genéricas auxiliares globais?

Fórum sobre comércio, sistemas de comércio automatizados e testes estratégicos

Bug de compilador: 'operator=' - a estrutura tem objectos e não pode ser copiada

fxsaber 2018.09.10 11:00 2018.09.10 10:00:13 RU
Alexey Navoykov:
Isto é, por enquanto. Se quiser incluir a biblioteca de alguém, descobrirá que o autor escreve como "primitivo" como você, usando os mesmos nomes de classes e funções.

Vou pregá-los com macros.

E as macros?
A100:
E as macros?

Eu não estava a falar de mim.

Li todas as páginas da discussão mas ainda não percebi como utilizá-la ?

Alguém me pode dar alguns exemplos?

Vladimir Pastushak:

Li todas as páginas da discussão mas ainda não percebi como utilizá-la ?

Alguém me pode dar alguns exemplos?

Esqueça. Não se pode utilizá-lo como está agora. Utilize antes o CObject padrão + CDictionary. Para a maioria das tarefas, é suficiente.

Vasiliy Sokolov:


ClasseDescrição
CHashMapUm conjunto de valores-chave. Permite-lhe inserir, recuperar e procurar eficazmente artigos com base na sua chave. A chave deve ser única. Por exemplo, CHashMap pode encontrar instantaneamente uma encomenda com um número especificado, onde o número é utilizado como chave.

Pergunta sobre a recuperação de um valor por chave. No código da biblioteca, este método parece-se com o seguinte

//+------------------------------------------------------------------+
//| Find index of entry with specified key.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::FindEntry(TKey key)
  {
   if(m_capacity!=NULL)
     {
      //--- get hash code from key
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      //--- search pair with specified key
      for(int i=m_buckets[hash_code%m_capacity]; i>=0; i=m_entries[i].next)
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
            return(i);
     }
   return(-1);
  }

As ferramentas de navegação ME (ALT+G e CTRL+-) por fonte recusam-se a trabalhar nesta biblioteca. Por conseguinte, é muito difícil traçar a lógica. Em particular, ainda não descobri o valor inicial no laço realçado. Mas há um entendimento que se houver uma velocidade, este valor deve ser muito inferior ao número de chaves.


Por favor, esclareça a ideia, qual é a velocidade alcançada nesta função? O excesso de mortes está claramente presente. Mas aparentemente é curto, por alguma razão.


SZ Passei pelo meu depurador passo a passo. Tudo claro no exemplo TKey = int: m_bucket[Array[i]] = i. Apenas colisões quando Array[i] == Array[j] (i != j) não são claras.

fxsaber:

A questão é de obter o valor pela chave. No código da biblioteca este método parece-se com o seguinte
Por favor esclareça a ideia, o que torna esta função rápida? O excesso está obviamente presente. Mas aparentemente é curto, por alguma razão.

Em tempos estive a rever e descrever como funcionao CHashMap
 É necessário procurar entradas, provavelmente neste tópico.

Fórum sobre comércio, sistemas automatizados de comércio e testes de estratégia comercial

Biblioteca de classes genéricas - bugs, descrição, perguntas, peculiaridades de uso e sugestões

Sergey Dzyublik, 2017.12.11 13:41

Brevemente sobre a implementação actual doCHashMap:

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;

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

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

  }

Primeiro, vamos descobrir o que éEntrada<TKey,TValue>.
Essencialmente é um Nodo como na CLinkedList que contém:

- colocado na chave e valor do recipiente
- hash_code - um valor de hash em cache para chave
- next - "pointer" to the nextEntry<TKey,TValue> com o objectivo de resolver a colisão através de uma lista de ligações


m_entries[] - matriz de "células" onde são colocadas chave e valor acrescentado, hash_code, a seguir. O tamanho da matriz corresponde à Capacidade.
m_count - especifica o índice da primeira célula não utilizada em m_entries. O valor inicial é 0, crescendo para Capacidade, a seguir é a reconstrução de todas as matrizes com aumento de Capacidade e tamanho de todas as matrizes.
m_buckets[] - matriz de índice em m_entries[]. O valor por defeito é -1. O tamanho da matriz corresponde à Capacidade.


Sem colisão, acrescentando um valor único ao contentorCHashMap:

  1. Calcular o hash por chave, obter o código hash_code
  2. Colocar chave, valor, hash_code em m_entries[] por índice m_count. (seguinte = -1 porque o exemplo não tem colisões)
  3. Colocar em m_buckets[] por hash_code % (ArraySize(m_buckets)) o valor do índice de elementos apenas adicionados em m_entries[] (isto é m_count).
  4. Aumentar m_count em +1

Sem colisões, obter valor por chave no contentorCHashMap:

  1. Calcule o hash a partir da chave, obtenha o código hash_code
  2. De m_buckets[], por hash_code % (ArraySize(m_buckets)) obtêm o valor que é um índice do array m_entries[]
  3. Utilizando o índice obtido m_buckets[hash_code % (ArraySize(m_buckets))], obtenha o nosso valor a partir do array m_entries[].

Resolução de colisões:

Para chaves diferentes, pode acontecer que o hash_code_key_1 % (ArraySize(m_buckets)) seja igual a hash_code_key_2 % (ArraySize(m_buckets)) Isto chama-se uma colisão.
Todos os elementos com colisão adicionados a m_entries[] estão ligados através da lista de um ligado com o seguinte (verEntrada<TKey,TValue> estrutura)
E m_buckets[] aponta sempre para o índice do primeiro elemento da cabeça nesta lista de colisão.
Recebemos não uma lista grande com colisões, mas muitas listas pequenas.


Colisão, obter valor por chave no contentorCHashMap:

  1. Na chave calculamos o hash, obtemos o código hash_code
  2. Usando o índice hash_code % (ArraySize(m_buckets)), obtenha o valor de m_entries[] array
  3. Podemos ver que o valor do próximo não é igual a -1, o que indica que há uma colisão
  4. Percorrer a lista de entrada única composta por elementos de m_entries[] e comparar o valor procurado e a chave guardada para a igualdade


Remoção de um valor do contentorCHashMap:

- Ao apagar uma célula em m_entries[], não é feita nenhuma eliminação; a célula é marcada como livre e o código hash_code = -1.
- as células livres formam a sua própria lista de células livres (utilizando a mesma da Entrada<TKey,TValue>),m_free_list
- as células livres são primeiro utilizadas para adicionar novos valores ao contentor.
-m_free_count é utilizado para controlar o número actual de células livres


Reconstruir a tabela de hash (processo de aumento da capacidade) :

- reconstruir apenas quando a Capacidade estiver 100% cheia.
- O tamanho da capacidade seguinte é retirado da lista:

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

- m_entries[] e m_buckets[] arrays são incrementados.
- m_buckets[] é limpo e completamente preenchido, com base em dados de m_entries[] (cached hash value for key - hash_code)


Comportamento descrito a partir de2017.12.11
 Actualmente, pode ter acrescentado/alterado alguns detalhes/coeficientes.

Sergey Dzyublik:

Já desmontei e descrevi como funciona oCHashMap
 É necessário procurar entradas, provavelmente neste tópico.

Encontrei-o em

Fórum sobre comércio, sistemas de comércio automatizados e testes estratégicos

Biblioteca de classes genéricas - erros, descrições, perguntas, peculiaridades de utilização e sugestões

Sergey Dzyublik, 2017.12.07 14:21


Neste exemplo, o hash é o aniversário do estudante.
Temos um armário com 365 prateleiras contendo as agendas dos estudantes.
Colocamos cada diário na prateleira correspondente ao aniversário do aluno.

Precisamos do diário do aluno Petrov e sabemos quando ele nasceu.
Agora pela data de nascimento em O(1) podemos facilmente encontrar o diário de Petrov, bem como o diário de qualquer outro estudante.
A excepção é quando dois estudantes têm o mesmo aniversário - chama-se a isto uma colisão.

Resolver uma colisão é usar a informação extra para descobrir qual de duas ou mais revistas precisamos.
A resolução da colisão através de uma lista é simplesmente percorrer todas as entradas da colisão uma a uma para encontrar uma correspondência. Arrancar cada diário e ver de quem é.
Uma sub-rubrica está a organizar uma tabela de hash dos itens envolvidos na colisão, mas por um critério diferente. Por exemplo, na hora em que o estudante nasceu.


Se estiver interessado no tópico - aconselho um curso do MailRu no youtube sobre algoritmos e estruturas de dados.

Fórum sobre comércio, sistemas automatizados de comércio e testes de estratégia comercial

Biblioteca de classes genéricas - erros, descrição, perguntas, peculiaridades de uso e sugestões

Sergey Dzyublik, 2017.12.08 14:40

As bases sobre este tópico são para os preguiçosos:
https://www.slideshare.net/mkurnosov/6-32402313

Na realidade, é muito mais complicado e é discutido na literatura relevante ou em bons cursos de "algoritmos e estruturas de dados".


Obrigado, o debug ajudou. Existem pequenas listas para colisões. Passou pelo fio e ficou horrorizado. Acontece que tem sido um tema...

Sergey Dzyublik:
Comportamento descrito a partir de2017.12.11

A partir de agora, poderá ter acrescentado/alterado alguns detalhes/coeficientes.

Muito obrigado! Ajudou muito com a sua descrição.

1...161718192021222324252627282930...38
Novo comentário