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

Novo comentário
 

Execute isto

#include <Generic\ArrayList.mqh>
#include <Generic\HashMap.mqh>

CHashMap<int, int> MagicsByDeals;

#define  AMOUNT 1000000

template <typename T>
int Test( T &Object )
{
  int Res = 0;
  
  for(int i = 0; i < AMOUNT; i++)
  {
    int Tmp = 0;
    
    if (Object.TryGetValue(i, Tmp))    
      Res += Tmp;
  }
  
  return(Res);
}

#define  BENCH(A)                                                              \
{                                                                             \
  const ulong StartTime = GetMicrosecondCount();                              \
  A;                                                                          \
  Print("Time[" + #A + "] = " + (string)(GetMicrosecondCount() - StartTime)); \
} 

void OnStart()
{   
  CArrayList<int> CollectionList;
  CHashMap<int, int> CollectionHash;
  
  for(int i = 0; i < AMOUNT; i++)
  {      
    CollectionHash.Add(i, i);
    CollectionList.Add(i);
  }
  
  BENCH(Print(Test(CollectionList)));
  BENCH(Print(Test(CollectionHash)));
}


e consegui isto.

1783293664
Time[Print(Test(CollectionList))] = 24819
1783293664
Time[Print(Test(CollectionHash))] = 91270


A CArrayList é mais rápida que a variante hash. Entrou nas entranhas da CArrayList, e há isto

template<typename T>
class CArrayList: public IList<T>
  {
protected:
   T                 m_items[];
   int               m_size;

Sinto-me enganado agora. A CArrayList acabou por ser um invólucro para uma matriz habitual. Pensei que era uma lista normal com apontadores Prev/Next, mas parece-se com isto

template<typename T>
bool CArrayList::TryGetValue(const int index,T &value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- get value by index
      value=m_items[index];
      return(true);
     }
   return(false);
  }
 
fxsaber:
Além dos próprios algoritmos de estrutura, há também o problema de escolher o recipiente certo com base nas especificidades da tarefa.
 
Combinador:
Além dos algoritmos de trabalhar com estruturas em si, há também o problema de escolher o recipiente certo com base nas especificidades da tarefa.

Portanto, a interface pode ser a mesma para diferentes implementações. Algum desapontamento, não da interface, mas da implementação específica - uma matriz. Em comparação com o haxixe, é o céu e a terra.

 
fxsaber:

Sinto-me enganado agora. A CArrayList acabou por ser um invólucro para uma matriz normal. Pensei que era uma lista normal com apontadores Prev/Next, mas aqui está.


Fórum sobre negociação, sistemas de negociação automatizados e testes estratégicos

Algoritmos, métodos de solução, comparação de desempenho

Sergey Dzyublik, 2017.12.10 20:52


Que tipo de SGBD, o que você diz a um homem que não sabe nada sobreestruturas de dados.
Se não existe um conceito de ArrayList (vector de C++), sobre o que podemos falar aqui.....


É mais a tua falta de atenção aqui...
Leia toda a lista disponível -https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList é um análogo de std::vector de C++
CLinkedList é muito provavelmente um análogo de std::list de C++

 
fxsaber:

Execute isto

e consegui isto.

A CArrayList é mais rápida que a variante hash. Entrou nas entranhas da CArrayList, e há isto

Sinto-me enganado agora. A CArrayList acabou por ser um invólucro para uma matriz habitual. Pensei que era uma lista normal com apontadores Prev/Next, mas parecia assim.

Historicamente, Lista não é uma folha - é uma matriz. Então está tudo bem. Se você conseguir uma lista em genérico, ela provavelmente será chamada de LinkedList ou algo parecido.

 
fxsaber:

Alguma frustração, não com a interface, mas com a implementação específica - a matriz.

bem... este contentor é um array (ou seja, um análogo de vector em C++), e o array mql nativo é muito bom, por isso o arraylist é mais um afterthought, um pouco mais conveniente de usar.
 

Fórum sobre negociação, sistemas de negociação automatizados e testes de estratégia de negociação

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

Sergey Dzyublik, 2017.12.09 01:12


Há algumas sugestões para possíveis melhorias:

1) Na minha humilde opinião, a implementação não contém uma escolha muito correcta da capacidade - tanto o tamanho inicial 3 como os subsequentes quando se reconstrói a tabela de hash.
Sim, é correto que um número primo deve ser escolhido para a uniformidade da distribuição.
No entanto, a implementação do CPrimeGenerator não corresponde às expectativas e contém omissões de números primos.
O propósito de tal "gerador" é claro - fornecer um fator de incremento da ordem de 1,2 com geração automática de números primos.
No entanto, isto não é um coeficiente muito pequeno? Em C++ para vetores, o coeficiente é normalmente de 1,5-2,0, dependendo da biblioteca (pois afeta fortemente a complexidade média da operação).
A saída poderia ser um coeficiente constante seguido de arredondamento do número para prime através de uma pesquisa binária de uma lista de números primos.
E um tamanho inicial de 3 é muito pequeno, nós não vivemos no século passado.

2) Atualmente a tabela de hash é reconstruída (Redimensionada) somente quando a capacidade está 100% cheia (todos os m_entries[] são preenchidos).
Devido a isso, pode haver uma quantidade significativa de colisões de chaves que não estão muito bem distribuídas.
Como opção, considere a introdução de um fator de preenchimento, que reduziria em 100% o limite necessário para a reconstrução da mesa de hash.

1) O factor de crescimento do volume (capacidade) não é igual a 1.2, CPrimeGenerator::O método ExpandPrime é utilizado para calcular o novo volume no CHashMap:

int CPrimeGenerator::ExpandPrime(const int old_size)
  {
   int new_size=2*old_size;
   if((uint)new_size>INT_MAX && INT_MAX>old_size)
      return INT_MAX;
   else
      return GetPrime(new_size);
  }

Neste método, o tamanho antigo da colecção é multiplicado por dois, depois encontramos o número simples mais próximo do topo para o valor resultante e devolvemo-lo como o novo volume.

Sobre o valor inicial da capacidade - concordo, é muito pequena.

Mas, por outro lado, há sempre construtores, onde se pode especificar explicitamente a capacidade inicial:

class CHashMap: public IMap<TKey,TValue>
  {
public:
                     CHashMap(const int capacity);
                     CHashMap(const int capacity,IEqualityComparer<TKey>*comparer);
  }

Por isso não vejo muito sentido mudar nada aqui.

2) Adicionar um parâmetro de fator de preenchimento ajudaria realmente a evitar colisões em alguns casos. O mais provável é que seja implementado.

 
Roman Konopelko:

1) O coeficiente de capacidade não é igual a 1,2, para calcular o novo volume no CHashMap, é utilizado o método CPrimeGenerator::ExpandPrime:

Neste método, o tamanho da colecção antiga é multiplicado por dois, depois para o valor resultante encontramos o mais próximo do número primo superior e devolvemo-lo como o novo volume.

Sobre o valor inicial da capacidade - concordo, é muito pequena.

Mas, por outro lado, há sempre construtores, onde se pode especificar explicitamente a capacidade inicial:

É por isso que não vejo nenhuma razão para mudar algo aqui.

2) Adicionar o parâmetro do fator de preenchimento ajudará realmente a evitar colisões em alguns casos. O mais provável é que seja implementado.

Roman, acho que te enganaste. Agora algumas aulas não contêm sequer os métodos mais necessários. Já tentou usá-los? Por exemplo, o CRedBlackTree, a implementação clássica de uma árvore negra-vermelha. Algoritmo bem legal, mas sem a possibilidade de iteração. O que queres dizer com isso? Há muitas outras coisas que você pode precisar, mas ninguém se preocupou em implementar por alguma razão. As coisas do GetHashCode são horríveis. Desculpe, mas não está ao nível do MQ!

 
Vasiliy Sokolov:

Roman, acho que não estás a fazer a coisa certa aí. Agora algumas classes genéricas não contêm sequer os métodos mais necessários. Já tentou usá-los de todo? Por exemplo, o CRedBlackTree, a implementação clássica de uma árvore negra-vermelha. Algoritmo bem legal, mas sem a possibilidade de iteração. O que queres dizer com isso? Há muitas outras coisas que você pode precisar, mas ninguém se preocupou em implementar por alguma razão. As coisas do GetHashCode são horríveis. Desculpe, mas este não é o nível do MQ!

Eu estou bem ciente da necessidade de iteradores para todas as coleções de modelos da biblioteca Genric, mas sem a possibilidade de criar classes aninhadas e herança múltipla a partir das interfaces, você não pode implementá-los corretamente.

Eu gostaria de ouvir comentários mais específicos sobre o GetHashCode.

 
Roman Konopelko:

...

Quanto ao GetHashCode, gostaria de ouvir comentários mais específicos.

Problema

Obviamente, o GetHashCode não pode ser implementado adequadamente em ambiente MQL5 personalizado. Isto é porque nem todos os objectos podem ser acedidos. E enquanto a implementação funciona bem para membros primitivos como a int dupla, para objetos complexos (classes, estruturas e até enumerações) o hash é calculado pelo nome. Se tivermos milhares de CObjects ou mesmo ENUM_something_that, então CHashMap e CHashSet irão degenerar em LinkedList:

#include <Generic\HashSet.mqh>
//+------------------------------------------------------------------+
//| Безобидное перечисление, но может быть класс или структура       |
//+------------------------------------------------------------------+
enum ENUM_NUMBER
{
   NUMBER_FIRTS,  // First
   NUMBER_SECOND, // Second
   NUMBER_THIRD   // Third
};
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
{
   CHashSet<ENUM_NUMBER> set_enum;
   for(int i = 0; i < 3; i++)
      set_enum.Add((ENUM_NUMBER)i);
   //-- Поздравляю, мы выродились в LinkedList.... 
   for(int i = 0; i < 3; i++)
   {
      //-- Здесь дикий оверхед по производительности, который тчательно скрывается...
      string is = set_enum.Contains((ENUM_NUMBER)i) ? " присутствует " : " отсутствует ";
      //...
   }
}

Não podemos evitar isto porque tudo o que temos ao nível do utilizador é o nome do objecto:

//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value)
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>(value);// <-- Здесь будет получено название класса, структуры или перечисление
   if(equtable)
     {
      //--- calculate hash by specied method   
      return equtable.HashCode();
     }
   else
     {
      //--- calculate hash from name of object
      return GetHashCode(typename(value));
     }
  }

Assim, os hashes de todos os objetos de tipos complexos são iguais entre si e este código de busca aqui envolve uma enumeração completa da matriz:

//+------------------------------------------------------------------+
//| Determines whether a set contains the specified element.         |
//+------------------------------------------------------------------+
template<typename T>
bool CHashSet::Contains(T item)
  {
//--- check buckets
   if(ArraySize(m_buckets)!=0)
     {
      //--- get hash code for item      
      int hash_code=m_comparer.HashCode(item);
      //--- search item in the slots       
      for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
         if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
            return(true);
     }
   return(false);
  }

Na verdade, isto é tão crítico que derrota o ponto de usar todos os genéricos na raiz. A questão é que na maioria dos casos você precisa associar ou armazenar objetos complexos: enumerações, estruturas ou classes. Se você precisasse operar apenas com tipos simples, você poderia fazer com algo mais simples.


Solução

Obviamente, MQL5 é uma linguagem de programação personalizada e segura, que funciona em uma máquina virtual interna. Algo como a Net. Isto significa que o acesso necessário aos objectos ainda existe, mas a um nível mais elevado do sistema. Daí,talvez escreva a função do sistema GetHashCode com o próximo protótipo:

int GetHashCode(void sample);

Como deve funcionar? Primeiro, deve ser omnívoro e rápido. Deve dar uma distribuição uniforme. Por exemplo:

int hash = GetHashCode(3);
// hash = 3

hash = GetHashCode(3.14159);
// hash = 2039485

enum EType{E1, E2, E3};
hash = GetHashCode(E2);
// hash = 2

class C1{};
C1* class1 = new C1();
hash = GetHashCode(class1);
//hash = 39203847

struct S1{};
S1 struct1;
hash = GetHashCode(struct1);
//hash = 83928342

Esta função pode ser localizada na seção de funções do sistema. Não vejo outras soluções.

s.e. Farei outras sugestões sobre interfaces, herança múltipla e outras coisas do legado C++ um pouco mais tarde.
1...111213141516171819202122232425...38
Novo comentário