Biblioteca de clases genéricas - errores, descripción, preguntas, características de uso y sugerencias - página 17

Nuevo comentario
 
Alexey Oreshkin:

¡Un gran ejemplo teórico! En la práctica, ¿alguien ha operado alguna vez miles de transacciones?

p.d. no estoy tratando de demostrar que es una mierda y que nadie lo necesita. Estoy tratando de entender el valor para el comercio real. No soy un teórico en general, sino un puro practicante.

No se trata de 1000 operaciones o sólo 10. La cuestión es que escribimos un código corto, que funciona con la misma eficacia tanto con 10 como con 1000000..... operaciones.
 

Brevemente sobre la implementación actual deCHashMap:

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;

     .................................

     .................................

  }

En primer lugar, vamos a averiguar qué esEntry<TKey,TValue>.
Esencialmente es un Nodo como en CLinkedList que contiene:

- colocados en un contenedor de claves y valores
- valor hash en caché para la clave - código_hash
- next - "puntero" a la siguienteEntry<TKey,TValue> para resolver las colisiones a través de la lista unidireccional


m_entries[] - matriz de "celdas" donde se colocan la clave y el valor añadidos, hash_code, next. El tamaño de la matriz corresponde a la Capacidad.
m_count - especifica el índice de la primera celda no utilizada en m_entries. El valor inicial es 0, creciendo hasta la Capacidad, lo siguiente es reconstruir todas las matrices con el aumento de la Capacidad y el tamaño de todas las matrices.
m_buckets[] - matriz de índices en m_entries[]. El valor por defecto es -1. El tamaño de la matriz corresponde a la capacidad.


Sin colisión, añadiendo un valor único al contenedorCHashMap:

  1. Calcular el hash por clave, obtener hash_code
  2. Poner clave, valor, código_hash en m_entradas[] por índice m_count. (next = -1 porque el ejemplo no tiene colisiones)
  3. Poner en m_cubos[] por hash_code % (ArraySize(m_cubos)) el valor del índice del elemento que se acaba de añadir en m_entradas[] (esto es m_count).
  4. Aumentar m_count en +1

Sin colisiones, obtener el valor por clave en el contenedorCHashMap:

  1. Calcular el hash de la clave, obtener el código hash
  2. De m_buckets[], por hash_code % (ArraySize(m_buckets)) obtener el valor que es un índice del array m_entries[]
  3. Usando el índice obtenido m_buckets[hash_code % (ArraySize(m_buckets))], obtenemos nuestro valor del array m_entries[].

Resolución de colisiones:

Para claves diferentes, puede ocurrir que hash_code_key_1 % (ArraySize(m_buckets)) sea igual a hash_code_key_2 % (ArraySize(m_buckets)) Esto se llama colisión.
Todos los elementos con colisión añadidos a m_entries[] se enlazan a través de la lista conectada con next (ver estructuraEntry<TKey,TValue>)
Y m_buckets[] siempre apunta al índice del primer elemento de cabeza de esta lista de colisión.
No obtenemos una gran lista con colisiones, sino muchas listas pequeñas.


Colisión, obtener el valor por clave en el contenedorCHashMap:

  1. Sobre la clave calculamos el hash, obtenemos hash_code
  2. Usando el índice hash_code % (ArraySize(m_buckets)), obtén el valor del array m_entries[]
  3. Podemos ver que el valor de next no es igual a -1, lo que indica que hay una colisión
  4. Recorre la lista de una sola entrada formada por elementos de m_entries[] y compara el valor buscado y la clave guardada para comprobar la igualdad


Eliminación de un valor del contenedorCHashMap:

- Cuando se borra una celda en m_entradas[], no se realiza ningún borrado; la celda se marca como libre y hash_code = -1.
- las celdas libres forman su propia lista de celdas libres (usando el mismo siguiente de Entry<TKey,TValue>),m_free_list
- las celdas libres se usan primero para añadir nuevos valores al contenedor.
-m_free_count se utiliza para controlar el número actual de celdas libres


Reconstruir la tabla hash (proceso para aumentar la capacidad) :

- reconstruir sólo cuando la capacidad está llena al 100%.
- El siguiente tamaño de capacidad se toma de la 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
  };

- Las matrices m_entries[] y m_buckets[] se incrementan.
- m_buckets[] se limpia y se rellena completamente, basándose en los datos de m_entries[] (valor hash almacenado para la clave - hash_code)



Foro sobre comercio, sistemas de comercio automatizados y pruebas de estrategias

Biblioteca de clases genéricas - errores, descripción, preguntas, uso y sugerencias

Sergey Dzyublik, 2017.12.09 01:12

Me familiaricé con la implementación deCHashMap
 Honestamente, me gustó.


Hay varias sugerencias de posibles mejoras:

1) En mi humilde opinión, la implementación contiene una selección no del todo correcta de la capacidad - tanto del tamaño inicial 3 como de los posteriores al reconstruir la tabla hash.
Sí, es correcto que se elija un número primo para la uniformidad de la distribución.
Sin embargo, la implementación de CPrimeGenerator no cumple con las expectativas y contiene omisiones de números primos.
El objetivo de este "generador" es claro: proporcionar un factor de incremento del orden de 1,2 con la generación automática de números primos.
Sin embargo, ¿no es un coeficiente demasiado pequeño? En C++, para los vectores, el coeficiente suele ser de 1,5-2,0, dependiendo de la biblioteca (ya que afecta mucho a la complejidad media de la operación).
La salida podría ser un coeficiente constante seguido del redondeo del número a primo mediante una búsqueda binaria de una lista de números primos.
Y un tamaño inicial de 3 es demasiado pequeño, no vivimos en el siglo pasado.

2) Actualmente la tabla hash se reconstruye (Resize) sólo cuando la capacidad está llena al 100% (todas las m_entradas[] están llenas).
Debido a esto, puede haber muchas colisiones para las claves que no están distribuidas de manera muy uniforme.
Como opción, considere la posibilidad de introducir un factor de llenado que reduzca el 100% en el límite necesario para realizar una reconstrucción de la tabla hash.


 
Alexey Oreshkin:

En la práctica, ¿alguien ha operado alguna vez con miles de transacciones?

Sí, millones de llamadas de historia en una pasada son practicadas por muchos.

 
Vasiliy Sokolov:

En los fuertes cada primero.

Está claro.

Enviar órdenes por el algoritmo hft y recogerlas para analizarlas son cosas diferentes. Estos hashes no son necesarios para el envío, y tampoco lo son para el análisis, ya que se analizan de forma diferente.

Así que, no te ofendas. También se necesita la teoría.

 
Alexey Oreshkin:

Está claro.

Enviar órdenes por el algoritmo hft y recogerlas después para analizarlas son cosas diferentes. No necesitas estos hashtags para el envío, y tampoco los necesitas para el análisis, porque eso no es lo que se está analizando.

Así que, no te ofendas. También necesitamos la teoría.


No uso el lavavajillas, uso la esponja.
Sin ánimo de ofender. Los lavavajillas son patéticos, para qué sirven.

 
Alexey Oreshkin:

Está claro.

Enviar órdenes por el algoritmo hft y elevarlas posteriormente para su análisis son cosas diferentes. No necesitas estos hashtags para enviarlos y no los necesitas para el análisis ya que analizamos algo más después.

Así que, no te ofendas. También necesitamos la teoría.

¿Qué rencores? Sigue escribiendo tus muletillas.

 
Sergey Dzyublik:

Breve descripción de la implementación actual deCHashMap

Gracias, lo utilizaré cuando analice el código fuente.

 
Vasiliy Sokolov:

¿Qué rencores? Sigue escribiendo tus muletillas.

El caso es que no estoy utilizando el tema que se ofrece aquí, y estoy tratando de entender si tengo razón o no. Estoy satisfecho con las matrices asociativas ordinarias, pero siempre quiero ser mejor.
 
fxsaber:

Gracias, lo usaré cuando analice las fuentes.


Se ha omitido la comprobación de la existencia de la clave en el contenedor al añadir un nuevo par clave-valor, ejecutado en primer lugar.
Pero no es importante.

 
Se enfrentó a un mensaje de error causado por la ausencia de este
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value) const

Por favor, arreglen algo así en todo el genérico.

1...101112131415161718192021222324...37
Nuevo comentario