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

Novo comentário
 
Sergey Dzyublik:

Hashes O(1) médio se o tamanho do dicionário para o número de elementos esperados permitir.
E depois depende de implementações de tratamento de colisões, pode ser através de uma lista, talvez mais subhash....

A minha ignorância terminológica dificulta o processo de entrar nele. Eu vou esperar por exemplos. Gostaria de ser sucinto e directo - mandados, carrapatos e afins.

 
fxsaber:

A minha ignorância terminológica dificulta o processo de entrar nele. Eu vou esperar por exemplos. Gostaria de ser sucinto e directo - mandados, carrapatos e afins.


Os mandados estão fora de questão. Eu estou interessado em acordos.

 
fxsaber:

Eu li na wiki. O tipo de caso em que não se compreende de todo a lógica do raciocínio intuitivo.


365 dias é o limite para o tamanho do dicionário
número de alunos na sala de aula é o número esperado de itens na coleção
coincidência de aniversários é uma colisão

 
Sergey Dzyublik:

365 dias é um limite para o tamanho do dicionário.
número de alunos na sala de aula é o número esperado de itens na coleção
coincidência de aniversários é uma colisão

Obrigado, essa definição terminológica é mais clara. Eu só não entendo o que esse "paradoxo" tem a ver com o tópico do fio?

 
Sergey Dzyublik:

365 dias é o limite para o tamanho do dicionário
número de alunos na sala de aula é esperado número de itens na coleção
coincidência de aniversários é uma colisão


Neste exemplo o haxixe é o aniversário do aluno.
Temos um armário com 365 prateleiras onde são guardadas as agendas dos alunos.
Colocamos cada diário em uma 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 encontrar facilmente o diário de Petrov, assim como o diário de qualquer outro estudante.
A exceção é quando dois alunos têm o mesmo aniversário - isso é chamado de colisão.

Resolver uma colisão é usar a informação extra para descobrir qual dos dois ou mais periódicos precisamos.
Resolver uma colisão através de uma lista é simplesmente percorrer todas as entradas na colisão uma a uma para encontrar uma correspondência. Arranca cada diário e vê de quem é.
Um subtítulo é organizar uma tabela de hash dos itens envolvidos na colisão, mas por um critério diferente. Por exemplo, na hora em que o aluno nasceu.


Se você está interessado no tópico, sugiro um curso no youtube do MailRu sobre algoritmos e estruturas de dados.

 
Sergey Dzyublik:

Neste exemplo o haxixe é o aniversário do aluno.
Temos um armário com 365 prateleiras que contém as agendas dos alunos.
Colocamos cada diário na prateleira que corresponde ao aniversário do aluno.

Precisamos do diário de Petrov e sabemos quando ele nasceu.
Agora pela data de nascimento em O(1) podemos facilmente encontrar a revista de Petrov, bem como outro estudante.
A exceção é quando dois alunos têm o mesmo aniversário - isso é chamado de colisão.

Resolver uma colisão é usar a informação extra para descobrir qual dos dois ou mais periódicos precisamos.
Resolver uma lista é simplesmente percorrer todas as entradas da colisão uma a uma para encontrar uma correspondência. Rasgue cada diário e veja de quem é.
Um subtítulo é organizar uma tabela de hash dos itens envolvidos na colisão, mas por um critério diferente. Por exemplo, na hora em que um aluno nasceu.


Se você está interessado no tópico, sugiro um curso no youtube do MailRu sobre algoritmos e estruturas de dados.

Foi assim que eu o imaginei originalmente. Só não entendo o destacado. Hash não é um índice, então você pode encontrá-lo por offset em um conjunto de ponteiros. Mesmo assim, devíamos procurar na lista. E isto é uma pesquisa binária com uma classificação adequada.

 
fxsaber:

Foi assim que eu imaginei desde o início. Só não entendo o destacado. Hash não é um índice, então você pode encontrá-lo por offset em um conjunto de ponteiros. Mas tens de procurar numa lista. E isto é uma pesquisa binária com uma classificação adequada.


Destacam-se os erros tipográficos verbais)) E já corrigido.
O haxixe é um índice. É dada ao tamanho do dicionário.

Cada prateleira tem a mesma altura e pelo número da prateleira você pode saber exatamente a que altura procurá-la. O(1)

 

O mais simples possível sobre a matriz associativa #1

Muitos algoritmos que são apresentados em genérico são baseados de uma forma ou de outra em um array associativo ou dicionário. É também um dos dois algoritmos mais comumente utilizados. 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:

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
string words[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   if(words[index] == NULL)
   {
      words[index] = word;
      return true;
   }
   return false;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   Add("apple");
   if(Contains("apple"))
      printf("Словарь содержит слово apple");
   else
      printf("Словарь не содержит слово apple");
  }
//+------------------------------------------------------------------+

Se lhe adicionarmos a palavra "maçã" e depois a encontrarmos, a operação de busca para aceder a esta palavra será instantânea. Porque sabemos antecipadamente o índice pelo qual esta palavra pode ser encontrada. Não pode haver outras variantes de índice, por isso não é necessário procurar em toda a lista. Esta é, grosso modo, a base de todos os dicionários.

No exemplo seguinte vamos melhorá-lo para que ele possa armazenar palavras que começam com a mesma letra.

 

O mais simples possível sobre a matriz associativa #2

Às vezes acontece que palavras diferentes começam com a mesma letra do alfabeto. Se colocarmos "maçã" no nosso dicionário anterior, e depois tentarmos colocar "aplicação" lá, não vai funcionar. Índice 0 será ocupado pela palavra maçã. Neste caso, falamos de uma colisão de função hash. Nossa função hash é muito simples - retorna o número do primeiro caracter da palavra, portanto colisões nesta função serão muito frequentes. Para armazenar palavras diferentes, começando com a mesma letra, faremos adições: armazenaremos elementos não em array, mas em array de arrays. Neste caso, o índice 0 conterá outro array com duas palavras: "apple" (maçã) e "application" (aplicação):

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words = WordsArray[index];
   if(words == NULL)
      return false;
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return true;
   return false;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words;
   if(WordsArray[index] == NULL)
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return false;
   words.Add(word);
   return true;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add("apple");
   Add("application");
   if(Contains("application"))
      printf("Словарь содержит слово application");
   else
      printf("Словарь не содержит слово application");
  }
//+------------------------------------------------------------------+

Agora o nosso dicionário armazena palavras mesmo começando com a mesma letra. Mas o custo de acesso às palavras com a mesma primeira letra aumenta. Porque agora precisamos de uma pesquisa completa de todas as palavras que começam com 'a' para descobrir se a palavra 'aplicação' está ou não no dicionário. Se a nossa função hash produzisse números diferentes mesmo que as palavras diferissem por um caracter, então a probabilidade de tentar palavras com os mesmos índices tenderia a zero, e o acesso a um elemento arbitrário tenderia a o(1). Em dicionários reais isto é exatamente o que acontece, funções que são usadas lá são à prova de colisão, então podemos dizer com segurança que o acesso aos itens destas coleções é muito rápido e quase sem força bruta.

 
Vasiliy Sokolov:

Manter a matriz associativa tão simples quanto possível

Muitos dos algoritmos que são apresentados em genérico são, de uma forma ou de outra, baseados na matriz associativa ou no dicionário. É também um dos dois algoritmos mais comumente usados. Acho que estaria perto da verdade se dissesse que 90% de todas as tarefas de programação são cobertas por 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:

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

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 no nosso índice 0, porque o caracter 'a' é a primeira letra do alfabeto, 'gato' será armazenado no índice 1, 'cão' no índice 3, nevoeiro será armazenado no índice 4, caminhada no índice 24 e zero no ú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:

Se lhe adicionarmos a palavra "maçã" e depois a encontrarmos, a operação de encontrar acesso a esta palavra será instantânea. Porque sabemos antecipadamente o índice pelo qual esta palavra pode ser encontrada. Não pode haver outras variantes de índice, por isso não é necessário procurar em toda a lista. Esta é, grosso modo, a base de todos os dicionários.

No próximo exemplo vamos melhorá-lo para que possamos armazenar palavras que comecem com a mesma letra.

Esta solução é perfeita. Tudo é tão simples quanto possível. Somente funções, matrizes e organização correta dos dados. É disso que estou a falar.
123456789101112...38
Novo comentário
Razão: