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

[Реter Konow]

Vasiliy Sokolov:

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 funciona. Í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):

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). Isto é exatamente o que acontece em dicionários e funções reais que são usadas lá são à prova de colisão, então podemos definitivamente dizer que o acesso aos elementos destas coleções é muito rápido e quase não tem pesquisa.

Vou tentar dar a minha solução a este exemplo. Sem indicações. Um pouco mais tarde.

[[Excluído]]

Eu li recentemente um livro sobre o assunto. Chama-se"Algoritmos de Rattling". Tudo está muito claramente exposto, com exemplos.

[fxsaber]

Vasiliy Sokolov:

No próximo exemplo, vamos melhorá-lo para que possa armazenar palavras que começam com a mesma letra.

Por favor, escreva-o de forma sucinta, sem cabeçalhos ou entidades desnecessárias.

Por exemplo, este

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}

poderia ser escrito de uma forma muito mais clara.

bool Contains(string word)
{
   return words[word[0]-'a'] != NULL;
}

E ainda assim este código pode funcionar de forma diferente para MT4/5 porque em MT4 a matriz é inicializada com valores NULL, e em MT5 pode ser lixo.

[Vladimir Karputov]

fxsaber:

Por favor escreva sucintamente, sem a confusão de chapéus e entidades supérfluas.

...

Categoricamente CONTRA! O código deve ser escrito, de preferência, por extenso. Olha para todos os códigos MQ - há "bonés" por todo o lado. Este é o padrão.

fxsaber:

...

E ainda assim este código para MT4/5 pode funcionar de forma diferente porque em MT4 a matriz é inicializada com valores NULL, e em MT5 pode ser lixo.

O que é que isto tem a ver com o terminal antigo? Se você é preguiçoso e ainda usa o antigo, este é o seu próprio problema. A comunidade não deve abrandar por causa de tais preguiçosos.

[fxsaber]

Vladimir Karputov:

Olha para todos os códigos MQ - há 'bonés' por todo o lado. Este é o padrão.

Que se lixe o padrão, a essência é importante aqui, não o estilo que leva 50% do código.

[Vladimir Karputov]

fxsaber:

Que se lixe o padrão, é a essência que conta, não o estilo que absorve 50% do código.

A principal tarefa do fórum é a EDUCAÇÃO. Portanto, o código deve ser expandido e claro com o máximo de aproximação possível ao padrão.

[fxsaber]

Vasiliy Sokolov:

Isto é exactamente o que acontece em dicionários reais; as funções aí utilizadas são resistentes a colisões, por isso podemos definitivamente dizer que o acesso aos itens destas colecções é muito rápido e quase sem exageros.

Isto é, para cada tarefa é necessário encontrar o meio termo entre o tamanho do dicionário (RAM) e a complexidade computacional da função hash (CPU).

[fxsaber]

Vladimir Karputov:

O principal objetivo do fórum é educar. Portanto, o código deve ser expandido e compreendido

isto é suficiente.

o mais próximo possível do padrão.

Você pode inserir os seus próprios cabeçalhos. A100 emitiu centenas de relatórios no SD sem limites - esse é o padrão! Porque a essência é o que importa, não os enfeites.

[Реter Konow]

Há uma solução. No entanto, para preservar temporariamente a intriga, eu gostaria de colocar o executável aqui. Além disso, pessoas capazes irão comparar o desempenho da minha solução e a solução fornecida pelo autor acima. O que será que funciona mais rápido?

[Реter Konow]

ReTeg Konow:
Há uma solução. No entanto, para manter a intriga viva temporariamente, eu gostaria de colocar o esforço aqui. Além disso, pessoas capazes irão comparar o desempenho da minha solução e a solução fornecida pelo autor acima. O que será que funciona mais rápido?

Precisas de executar o executável. Um campo de entrada irá aparecer. A seguir, você pode digitar palavras diferentes. Se houver uma correspondência, você será notificado pela impressora que a palavra está no dicionário. Se não houver nenhuma palavra, você receberá uma notificação de que a palavra é adicionada ao dicionário.