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

Nuevo comentario
 
Sergey Dzyublik:

Los hashes tienen un promedio de O(1) si el tamaño del diccionario al número de elementos esperados lo permite.
Y luego depende de las implementaciones de manejo de colisiones, puede ser a través de una lista, tal vez más subhash....

Mi ignorancia terminológica dificulta el proceso de entrar en él. Esperaré los ejemplos. Me gustaría que fuera sucinta y al grano: garantías, garrapatas y cosas por el estilo.

 
fxsaber:

Mi ignorancia terminológica dificulta el proceso de entrar en él. Esperaré los ejemplos. Me gustaría que fuera sucinta y al grano: garantías, garrapatas y cosas por el estilo.


Las órdenes de arresto están descartadas. Me interesan los tratos.

 
fxsaber:

Lo he leído en la wiki. El tipo de caso en el que no se entiende en absoluto la lógica del razonamiento intuitivo.


365 días es el límite del tamaño del diccionario
el número de alumnos de la clase es el número previsto de elementos de la colección
la coincidencia de cumpleaños es una colisión

 
Sergey Dzyublik:

365 días es un límite para el tamaño del diccionario.
el número de alumnos de la clase es el número previsto de elementos de la colección
la coincidencia de cumpleaños es una colisión

Gracias, esa definición terminológica es más clara. No entiendo qué tiene que ver esta "paradoja" con el tema del hilo.

 
Sergey Dzyublik:

365 días es el límite del tamaño del diccionario
el número de estudiantes en la clase es el número esperado de artículos en la colección
la coincidencia de cumpleaños es una colisión


En este ejemplo, el hash es la fecha de nacimiento del estudiante.
Tenemos un armario con 365 estantes donde se guardan las agendas de los alumnos.
Colocamos cada agenda en un estante correspondiente al cumpleaños del alumno.

Necesitamos el diario del alumno Petrov y sabemos cuándo nació.
Ahora por la fecha de nacimiento en O(1) podemos encontrar fácilmente el diario de Petrov, así como el de cualquier otro estudiante.
La excepción es cuando dos estudiantes cumplen años el mismo día, lo que se denomina colisión.

Resolver una colisión es utilizar la información extra para averiguar cuál de dos o más diarios necesitamos.
La resolución de colisiones a través de una lista consiste simplemente en recorrer todas las entradas de la colisión una por una para encontrar una coincidencia. Arranca cada diario y mira de quién es.
Un subtítulo es la organización de una tabla hash de los elementos implicados en la colisión, pero con un criterio diferente. Por ejemplo, por la hora de nacimiento del alumno.


Si te interesa el tema, te sugiero un curso en youtube de MailRu sobre algoritmos y estructuras de datos.

 
Sergey Dzyublik:

En este ejemplo, el hash es la fecha de nacimiento del estudiante.
Tenemos un armario con 365 estantes que contienen las agendas de los alumnos.
Colocamos cada agenda en la estantería que corresponde al cumpleaños del alumno.

Necesitamos el diario de Petrov y sabemos cuándo nació.
Ahora por la fecha de nacimiento en O(1) podemos encontrar fácilmente el diario de Petrov así como de otro estudiante.
La excepción es cuando dos estudiantes cumplen años el mismo día, lo que se denomina colisión.

Resolver una colisión es utilizar la información extra para averiguar cuál de dos o más diarios necesitamos.
La resolución de colisiones a través de una lista consiste simplemente en recorrer todas las entradas de la colisión una por una para encontrar una coincidencia. Arranca cada diario y mira de quién es.
Un subtítulo es la organización de una tabla hash de los elementos implicados en la colisión, pero con un criterio diferente. Por ejemplo, por la hora de nacimiento de un alumno.


Si te interesa el tema, te sugiero un curso en youtube de MailRu sobre algoritmos y estructuras de datos.

Así es como lo imaginé originalmente. No entiendo el resaltado. Hash no es un índice, por lo que se puede encontrar por desplazamiento en una matriz de punteros. De todos modos, debemos buscar en la lista. Y esto es una búsqueda binaria con una ordenación adecuada.

 
fxsaber:

Así es como lo imaginé desde el principio. No entiendo el resaltado. Hash no es un índice, por lo que se puede encontrar por desplazamiento en una matriz de punteros. Sin embargo, hay que buscar en una lista. Y esto es una búsqueda binaria con una ordenación adecuada.


Lo resaltado son erratas verbales)) Y ya está corregido.
El hash es un índice. Se da al tamaño del diccionario.

Cada estante tiene la misma altura y por el número de estante puedes saber exactamente a qué altura buscarlo. O(1)

 

Lo más sencillo posible sobre la matriz asociativa #1

Muchos de los algoritmos que se presentan en Generic se basan de una manera u otra en una matriz asociativa o en un diccionario. También es uno de los dos algoritmos más utilizados. Creo que estoy cerca de acertar cuando digo que el 90% de las tareas de programación se cubren con arrays y diccionarios. Antes de pasar a la práctica, vamos a describir el trabajo del diccionario de la forma más clara y sencilla posible, simplificando deliberadamente algunos detalles.

Mostraremos el diccionario en un ejemplo muy sencillo: una lista de palabras regulares. Supongamos que tenemos unas pocas palabras, que empiezan con diferentes letras del alfabeto:

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

El alfabeto inglés contiene 26 caracteres. Vamos a crear un array de cadenas, de tamaño 26 elementos:

string dictionary[26];

Ahora bien, si aceptamos almacenar las palabras en índices correspondientes a su primera letra, obtendremos un diccionario sencillo. Vamos a indexar desde cero. La palabra "manzana" se almacenará en nuestro diccionario en el índice 0, porque el carácter "a" es la primera letra del alfabeto, "gato" - en el índice 1, "perro" - en el índice 3, niebla - ocupará el índice 4, paseo - índice 24 y cero - el último índice 25.

Tenga en cuenta que los índices 5 a 23 no se utilizarán. Esto supone un gasto adicional de memoria, pero podemos acceder instantáneamente, por ejemplo, a la palabra "paseo", porque sabemos que si existe, se encuentra en el índice 24.

Vamos a escribir nuestro primer diccionario vací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"
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");
  }
//+------------------------------------------------------------------+

Si le añadimos la palabra "manzana" y la encontramos, la operación de búsqueda para acceder a esta palabra será instantánea. Porque conocemos de antemano el índice por el que se puede encontrar esta palabra. No puede haber otras variantes del índice, por lo que no es necesario recorrer toda la lista. Esta es aproximadamente la base de todos los diccionarios.

En el siguiente ejemplo lo mejoraremos para que pueda almacenar palabras que empiecen por la misma letra.

 

Lo más sencillo posible sobre la matriz asociativa #2

A veces ocurre que diferentes palabras comienzan con la misma letra del alfabeto. Si ponemos "manzana" en nuestro diccionario anterior y luego intentamos poner "aplicación", no funcionará. El índice 0 estará ocupado por la palabra manzana. En este caso hablamos de una colisión de la función hash. Nuestra función hash es muy sencilla: devuelve el número del primer carácter de la palabra, por lo que las colisiones en esta función serán muy frecuentes. Para almacenar diferentes palabras, que empiezan por la misma letra, haremos una adición: almacenaremos los elementos no en array, sino en array de arrays. En este caso, el índice 0 contendrá otra matriz con dos palabras: "manzana" y "aplicación":

//+------------------------------------------------------------------+
//|                                                         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");
  }
//+------------------------------------------------------------------+

Ahora nuestro diccionario almacena palabras que incluso empiezan por la misma letra. Pero el coste de acceder a palabras con la misma primera letra aumenta. Porque ahora necesitamos una búsqueda completa de todas las palabras que empiezan por 'a' para saber si la palabra 'aplicación' está en el diccionario o no. Si nuestra función hash produjera números diferentes aunque las palabras difirieran en un carácter, entonces la probabilidad de probar palabras con los mismos índices tendería a cero, y el acceso a un elemento arbitrario tendería a o(1). En los diccionarios reales esto es exactamente lo que ocurre, las funciones que se utilizan en ellos son a prueba de colisiones, por lo que podemos decir con seguridad que el acceso a los elementos de estas colecciones es muy rápido y casi sin fuerza bruta.

 
Vasiliy Sokolov:

Mantener la matriz asociativa lo más simple posible

Un gran número de algoritmos que se presentan en Generic se basan de una manera u otra en la matriz asociativa o el diccionario. También es uno de los dos algoritmos más utilizados. Creo que estaría cerca de la verdad si dijera que el 90% de las tareas de programación se cubren con arrays y diccionarios. Antes de pasar a la práctica, vamos a describir el trabajo del diccionario de la forma más clara y sencilla posible, simplificando deliberadamente algunos detalles.

Mostraremos el diccionario en un ejemplo muy sencillo: una lista de palabras regulares. Supongamos que tenemos unas pocas palabras, que empiezan con diferentes letras del alfabeto:

El alfabeto inglés contiene 26 caracteres. Vamos a crear un array de cadenas, de tamaño 26 elementos:

Ahora bien, si aceptamos almacenar las palabras en índices correspondientes a su primera letra, obtendremos un diccionario sencillo. Vamos a indexar desde cero. La palabra 'manzana' se almacenará en nuestro índice 0, porque el carácter 'a' es la primera letra del alfabeto, 'gato' se almacenará en el índice 1, 'perro' en el índice 3, niebla se almacenará en el índice 4, paseo en el índice 24 y cero en el último índice 25.

Tenga en cuenta que los índices 5 a 23 no se utilizarán. Esto supone un gasto adicional de memoria, pero podemos acceder instantáneamente, por ejemplo, a la palabra "paseo", porque sabemos que si existe, se encuentra en el índice 24.

Vamos a escribir nuestro primer diccionario vacío:

Si le añadimos la palabra "manzana" y la encontramos, la operación de búsqueda para acceder a esta palabra será instantánea. Porque conocemos de antemano el índice por el que se puede encontrar esta palabra. No puede haber otras variantes del índice, por lo que no es necesario recorrer toda la lista. Esta es aproximadamente la base de todos los diccionarios.

En el siguiente ejemplo lo mejoraremos para poder almacenar palabras que empiecen por la misma letra.

Esta solución es perfecta. Todo es lo más sencillo posible. Sólo funciones, matrices y una correcta organización de los datos. A eso me refiero.
123456789101112...37
Nuevo comentario