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

Novo comentário
 

Aqui está o código junto com o campo de entrada. (Pode vir a ser útil para alguém. Pode ser refinado).

//+------------------------------------------------------------------+
//|                                                   Dictionary.mq5 |
//|                                                      Peter Konow |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Peter Konow"
#property link      ""
#property version   "1.00"
#property strict
//+------------------------------------------------------------------+
//| Expert initialization function                                   |
//+------------------------------------------------------------------+
#define  Max_possible_collisions    100
#define  Max_letters_in_word        100
#define  All_letters_in_alphabet    255 
//------------------------------------
string Dictionary[Max_possible_collisions][All_letters_in_alphabet][Max_letters_in_word];
//-------------------------------------------------------------------
int OnInit()
  {
//---
   Create_text_box();
//---
   return(INIT_SUCCEEDED);
  }
//+------------------------------------------------------------------+
//| Expert deinitialization function                                 |
//+------------------------------------------------------------------+
void OnDeinit(const int reason)
  {
   ObjectDelete(0,"Text_box");
  }
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| ChartEvent function                                              |
//+------------------------------------------------------------------+
void OnChartEvent(const int id,
                  const long &lparam,
                  const double &dparam,
                  const string &sparam)
  {
    if(id == CHARTEVENT_OBJECT_ENDEDIT)
      { 
       //-----------------------
       string Text;     
       //---------------------
       ObjectGetString(0,"Text_box",OBJPROP_TEXT,0,Text);
       //-------------------------------------
       Add(Text);
      } 
  }
//+------------------------------------------------------------------+

void Add(string word)
{
 uchar First_letter = (uchar)StringGetCharacter(word,0) - 97;
 //-----------------------
 int All_letters_in_word = StringLen(word);
 //-----------------------
 for(int a1 = 0; a1 < Max_possible_collisions; a1++)
   {
     string word_inside = Dictionary[a1][First_letter][All_letters_in_word];
     //-----------------------   
    if(word_inside == NULL)
      {
       Dictionary[a1][First_letter][All_letters_in_word] = word;
       Print("Your word has been added to our dictionary!");
       break;
      }
    if(word_inside == word)
      {
       Print("This word already exists in our dictionary");
       break;
      } 
   }   
 //------------------------   
}
//--------------------------------------------------------------------+


//--------------------------------------------------------------------
void Create_text_box()
{
  ObjectCreate(0,"Text_box",OBJ_EDIT,0,0,0);
  ObjectSetInteger(0,"Text_box",OBJPROP_XDISTANCE,500);
  ObjectSetInteger(0,"Text_box",OBJPROP_YDISTANCE,250);
  ObjectSetInteger(0,"Text_box",OBJPROP_XSIZE,400);
  ObjectSetInteger(0,"Text_box",OBJPROP_YSIZE,30);
  ObjectSetString(0,"Text_box",OBJPROP_TEXT,"Please enter your word here...");
  ObjectSetString(0,"Text_box",OBJPROP_FONT,"TimesNewRoman");
  ObjectSetInteger(0,"Text_box",OBJPROP_STATE,1);
  //----------------------------------------------
  ObjectSetInteger(0,"Text_box",OBJPROP_FONTSIZE,12);
  ObjectSetInteger(0,"Text_box",OBJPROP_BGCOLOR,clrWhite);
  ObjectSetInteger(0,"Text_box",OBJPROP_COLOR,clrBlack);
  ObjectSetInteger(0,"Text_box",OBJPROP_BORDER_COLOR,clrBlack);
  ObjectSetInteger(0,"Text_box",OBJPROP_ALIGN,ALIGN_CENTER);
  //----------------------------------------------
  ObjectSetInteger(0,"Text_box",OBJPROP_CORNER,CORNER_LEFT_UPPER);
  ObjectSetInteger(0,"Text_box",OBJPROP_ANCHOR,ANCHOR_LEFT_UPPER);  
  //---------------------------------------------- 
}
//-----------------------------------------------------------------------

Só por alguma razão, funciona plenamente no quarto. No quinto, o campo não aparece. Eu procurei a razão e não a encontrei.

 
fxsaber:

Ou seja, você tem que encontrar o equilíbrio certo entre o tamanho do dicionário (RAM) e a complexidade computacional da função hash (CPU) para cada tarefa.


Relativamente sim.
Quando o número de elementos é pequeno, o tamanho ideal do dicionário é o número de elementos ao quadrado (tanto quanto me lembro do curso de 3 anos de idade, mas é sempre melhor checar novamente).
Quando um grande número de elementos torna impossível escolher o tamanho ideal, eles tomam o tamanho do dicionário várias vezes maior do que o número de elementos esperados e otimizam o manuseio da colisão, por exemplo, usando tabelas hash internas para cada uma das colisões.

É feita uma tentativa de escolher uma tabela de hash para que ela seja pesquisada o mais rápido possível, mas ainda assim fornecer uma distribuição uniforme dos resultados obtidos sobre o tamanho da lista de palavras.
O uso de números primos em hashes está relacionado com a uniformidade da distribuição.

 
Konow tag:
Tivemos de aumentar o tamanho do array, porque as letras maiúsculas têm um código diferente e "desistir" do array.

O código do carácter "A" difere do código do carácter "a" por exactamente 32. De forma correspondente, todo o resto tem a diferença de 32 também.

Talvez o tamanho da matriz não devesse ter sido aumentado e o primeiro caracter deveria ter sido substituído.
 
Alexey Viktorov:

O código para o caractere "A" difere do código para o caractere "a" por exatamente 32. Assim, todos os outros também têm uma diferença de 32.

Talvez o tamanho da matriz não devesse ter sido aumentado e o primeiro caracter deveria ter sido substituído.

Eu concordo. O algoritmo está incompleto a este respeito.

O tamanho da matriz é muito grande. Ontem não percebi bem os códigos das letras.

 
Tag Konow:

Aqui está o código junto com o campo de entrada. (Pode vir a ser útil para alguém. Você pode refiná-lo).

Mas funciona perfeitamente bem no 4. O campo não aparece no cinco. Procurei a razão e não a consegui encontrar.

Mais uma observação: No exemplo de Vasiliy, há uma menção a uma série

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

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

Vasiliy Sokolov, 2017.12.07 14:30

Muito simples na matriz associativa #1

Muitos algoritmos que são apresentados em genérico são baseados em matriz associativa ou dicionário. É também um dos dois algoritmos mais comumente usados. Acho que estou perto de ter razão quando digo que 90% de todas as tarefas de programação são cobertas com matrizes e dicionários. Antes de passarmos à prática, vamos descrever o trabalho do dicionário da forma mais clara e direta possível, simplificando deliberadamente alguns dos detalhes.

Mostraremos o dicionário em um exemplo muito simples: uma lista de palavras comum. Suponha que temos apenas algumas palavras, todas começando com letras diferentes do alfabeto:

string words[] = {"apple", "cat", "fog", "dog", "walk", "zero"};

O alfabeto inglês contém 26 caracteres. Vamos criar um conjunto de cordas, de tamanho 26 elementos:

string dictionary[26];

Agora, se concordarmos em armazenar palavras em índices correspondentes à sua primeira letra, vamos obter um dicionário simples. Vamos indexar a partir do zero. A palavra 'maçã' será armazenada em nosso dicionário no índice 0, pois o caracter 'a' é a primeira letra do alfabeto, 'gato' - no índice 1, 'cachorro' - no índice 3, neblina - ocupará o índice 4, caminhada - índice 24 e zero - o último índice 25.

Note que os índices de 5 a 23 não serão utilizados. Isto é um desperdício adicional de memória, mas podemos aceder instantaneamente, por exemplo, à palavra "andar", porque sabemos que se ela existe, está localizada no índice 24.

Vamos escrever o nosso primeiro dicionário vazio:



E no seu exemplo. 

#define  Max_possible_collisions    100
#define  Max_letters_in_word        100
#define  All_letters_in_alphabet    255 
//------------------------------------
string Dictionary[Max_possible_collisions][All_letters_in_alphabet][Max_letters_in_word];

Quanta memória é necessária para uma matriz tridimensional? E se tiveres de aumentar a dimensionalidade?

 
Alexey Viktorov:

Mais uma nota: No exemplo de Vasiliy há uma menção de um array


E no seu exemplo.

Quanta memória é necessária para uma matriz tridimensional? E se tivermos de aumentar a dimensionalidade?

Otamanho da matriz é muito grande porque:

1. Eu decidi que o número máximo de letras em uma palavra pode ser 100. Isto é obviamente demais. Podíamos reduzi-lo para 30.

2. O número de letras possíveis também se revelou excessivo. Eu decidi ocupar espaço para o maior número possível de personagens diferentes. Pode ser reduzido.

3. O número de "colisões", ou seja, palavras correspondentes pela primeira letra e pelo número de letras na palavra, é definido como 100. Isto também é demais. Podias ir até aos 50.


Não vejo a razão para o aumentar. Você pode apenas adicionar um dicionário.

 
Tag Konow:

O tamanho da matriz é muito grande porque:

1. Eu decidi que o número máximo de letras numa palavra pode ser 100. Isto é claramente um exagero. Pode ser reduzido para 30.

2. O número de letras possíveis também se revelou excessivo. Eu decidi ocupar espaço para o maior número possível de personagens diferentes. Pode ser reduzido.

3. O número de "colisões", ou seja, palavras correspondentes pela primeira letra e pelo número de letras na palavra é definido como 100. Isto também é demais. Podes reduzi-lo para 50.


Não vejo nenhuma razão para aumentar o tamanho. Podes apenas fazer outro dicionário.

A questão não é sobre o dicionário. O dicionário é apenas um exemplo de como construir um algoritmo. Pode haver não 100 itens como no seu exemplo, mas 1e10 e mais... Qual é o tamanho do conjunto num caso destes?

Por exemplo, colete todo o histórico de carrapatos disponíveis em um array. Pode haver mais de um tick em um milissegundo, por isso a matriz não pode ser unidimensional... Quantos carrapatos havia em um milissegundo, no máximo?? Dois ou cinco??? Qual deveria ser a dimensionalidade da matriz neste caso??? Quanta memória seria desperdiçada?

 
Alexey Viktorov:

Por exemplo, colete todo o histórico de carrapatos disponíveis em um array.

Depois de escrever tudo isso, ocorreu-me que não há tarefa prática para armazenar carrapatos na forma discutida no fio. Eles são ordenados pelo tempo e armazenados em uma matriz simples.

É o mesmo com os Pedidos/Negócios de História. E, a julgar pela HistorySelect, eles são armazenados em um array pelo tempo. E eu acho que não há nada (na implementação actual) que permita procurar registos por bilhete ou identificação.

E tudo porque, no caso da história nomeada, não é razoável fazer algo assim. Um simples conjunto para praticar é o suficiente.

É por isso que estou interessado na formulação prática das tarefas no campo do comércio.


Quando você está tentando acelerar o HistorySelect, tenho certeza que você resolveu o problema com o cache, não com hashes e dicionários.

 
fxsaber:

Depois de escrever tudo isso, ocorreu-me que não há tarefa prática para armazenar carrapatos na forma discutida no fio. Eles são ordenados pelo tempo e armazenados em uma matriz simples.

O mesmo se passa com os Pedidos/Negócios de História. E, a julgar pela HistorySelect, eles são armazenados em um array pelo tempo. E eu acho que não há nada (na implementação actual) que permita procurar registos por bilhete ou identificação.

E tudo porque, no caso da história nomeada, não é razoável fazer algo assim. Um simples conjunto para praticar é o suficiente.

É por isso que estou interessado na formulação prática das tarefas no campo da negociação.


Quando você acelera o HistorySelect, você provavelmente o resolveu com cache, não com dicionários de hash.

Sem discussão, mas se alguém quer implementar alguma tarefa dessa forma, então sinalize no local...

Alguém pensa que não vale a pena, alguém não consegue dominá-lo... E, em ambos os casos, há implementações mais simples. Mas quem sabe como o comércio se desenvolverá "amanhã"... É provavelmente melhor tê-lo e não reclamá-lo do que tê-lo na ausência dele.

 
Alexey Viktorov:

A questão não é sobre o dicionário. O dicionário é apenas um exemplo de construção de algoritmos. E pode haver não 100 itens como no seu exemplo, mas 1e10 e mais... Qual é o tamanho do conjunto num caso destes?

Por exemplo, junte todo o histórico de carrapatos disponíveis em um array. Pode haver mais de um tick em um milissegundo, por isso a matriz não pode ser unidimensional... mas quantos carrapatos havia num milissegundo, no máximo??? Dois ou cinco??? Qual deveria ser a dimensionalidade da matriz neste caso??? Quanta memória vai ser desperdiçada?

Eu estava a resolver a tarefa de construir um dicionário conveniente.

Os bilhetes ou outros elementos têm as suas próprias propriedades específicas, que podem ser indexados com sucesso para um acesso rápido ao local de armazenamento.

A essência da tarefa de acesso rápido aos dados, é identificar várias propriedades classificáveis de um elemento e indexá-las.

Um elemento é tomado, as propriedades convenientes das quais se pode obter índices são encontradas, e o acesso ao local de armazenamento é obtido através dos índices.

Se índices não forem suficientes (por exemplo, podemos indexar a primeira letra e o número de letras, mas outras propriedades não fornecem índices convenientes), nós fazemos força bruta direta de elementos dentro da área ao seu redor.

O princípio é universal, as implementações podem variar.

123456789101112131415...38
Novo comentário