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

Novo comentário
 
Alexey Oreshkin:

Um grande exemplo teórico! Na prática, alguém já operou milhares de transacções?

p.s. não estou a tentar provar que é uma porcaria e ninguém precisa dela. Estou a tentar compreender o valor de uma negociação a sério. Eu não sou um teórico em geral, mas um puro praticante.

Não são cerca de 1000 negócios ou apenas 10. A questão é que nós escrevemos código curto, que funciona de forma igualmente eficaz com 10 ou 1000000..... negociações.
 

Brevemente sobre a implementação atual 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 num contentor de chaves e valores
- valor de hash em cache para chave - hash_code
- next - "pointer" to the nextEntry<TKey,TValue> para resolver colisões através da lista unidireccional


m_entries[] - array de "células" onde a chave e o valor acrescentado, hash_code, são colocados 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 padrão é -1. O tamanho da matriz corresponde à Capacidade.


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

  1. Calcular hash por chave, obter hash_code
  2. Coloque chave, valor, hash_code em m_entries[] por índice m_count. (seguinte = -1 porque o exemplo não tem colisões)
  3. Coloque em m_buckets[] por hash_code % (ArraySize(m_buckets)) o valor do índice do elemento adicionado em m_entries[] (isto é m_count).
  4. Aumentar m_count em +1

Sem colisões, obtenha valor por chave no recipienteCHashMap:

  1. Calcule o hash a partir da chave, obtenha o hash_code
  2. De m_buckets[], por hash_code % (ArraySize(m_buckets)) obtêm o valor que é um índice do array m_entries[]
  3. Usando 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 hash_code_key_1 % (ArraySize(m_buckets)) é igual a hash_code_key_2 % (ArraySize(m_buckets)) Isto é chamado de colisão.
Todos os elementos com colisão adicionados a m_entries[] sã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.
Não recebemos uma lista grande com colisões, mas muitas listas pequenas.


Colisão, obter valor por chave no recipienteCHashMap:

  1. Na chave que calculamos o hash, obter o hash_code
  2. Usando o índice hash_code % (ArraySize(m_buckets)), obtenha o valor do array m_entries[]
  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 gravada para a igualdade


Remoção de um valor do recipienteCHashMap:

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


Reconstruir tabela de hash (processo para aumentar a 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, baseado em dados de m_entries[] (cached hash value for key - hash_code)



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

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

Sergey Dzyublik, 2017.12.09 01:12

Conheci a implementação doCHashMap
 Honestamente, eu gostei.


Há várias sugestões para possíveis melhorias:

1) Na minha humilde opinião, a implementação não contém uma seleção correta da capacidade - tanto o tamanho inicial 3 como os tamanhos subseqüentes 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[] estã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 reduz 100% pelo limite necessário para realizar a reconstrução de uma tabela de hash.


 
Alexey Oreshkin:

Na prática, alguém já operou em milhares de transacções?

Sim, milhões de chamadas históricas em um passe são praticadas por muitos.

 
Vasiliy Sokolov:

Em Forts todos os primeiros.

Está claro.

Oenvio de ordens por algoritmo de balanço e a sua recolha para análise são coisas diferentes. Estes hashes não são necessários para envio, e também não são necessários para análise, porque são analisados de uma forma diferente.

Então, sem ofensa. Você também precisa de teoria.

 
Alexey Oreshkin:

Está claro.

O envio de ordens por algoritmo de balanço e a sua recolha mais tarde para análise são coisas diferentes. Você não precisa desses hashes para enviar, e também não precisa deles para análise, porque não é isso que está sendo analisado.

Então, sem ofensa. Também precisamos de teoria.


Eu não uso máquina de lavar louça, eu uso uma esponja.
Sem ofensa nenhuma. As máquinas de lavar louça são foleiras, para que servem.

 
Alexey Oreshkin:

Está claro.

O envio de ordens por algoritmo de balanço e sua posterior elevação para análise são coisas diferentes. Você não precisa desses hashes para submetê-los e não precisa deles para análise, já que analisamos outra coisa depois.

Então, sem ofensa. Também precisamos de teoria.

Que ressentimentos? Continue a escrever as suas muletas.

 
Sergey Dzyublik:

Brevemente sobre a implementação actual doCHashMap

Obrigado, eu vou usá-lo quando analisar o código fonte.

 
Vasiliy Sokolov:

Que ressentimentos? Continue a escrever as suas muletas.

A questão é que não estou a usar o assunto aqui oferecido, e estou a tentar perceber se estou certo ou não. Estou satisfeita com os conjuntos associativos comuns, mas quero ser sempre melhor.
 
fxsaber:

Obrigado, vou usá-lo quando analisar as fontes.


Omitida a verificação da existência da chave no contentor ao adicionar um novo par de valores de chave, executado primeiro.
Mas isso não é importante.

 
Enfrentou uma mensagem de erro causada pela ausência deste
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value) const

Por favor, conserte algo como isto em todo o genérico.

1...101112131415161718192021222324...38
Novo comentário