c# - recorrer - para que sirve una matriz en programacion

¿Cuál es la forma más rápida de calcular la distribución de frecuencias para una matriz en C#?

Question

Me pregunto cuál es el mejor enfoque para ese cálculo. Supongamos que tengo un conjunto de valores de entrada y un conjunto de límites. Quería calcular / dividir la distribución de frecuencias para cada segmento en el conjunto de límites.

¿Es buena idea usar la búsqueda de cubos para eso?

En realidad, encontré esa pregunta Cálculo de la distribución de frecuencias de una colección con .Net / C #

Pero no entiendo cómo usar los cubos para ese propósito porque el tamaño de cada cubo puede ser diferente en mi situación.

EDITAR: Después de todas las discusiones tengo una solución de bucle interno / externo, pero igual quiero eliminar el bucle interno con un diccionario para obtener el rendimiento de O (n) en ese caso, si entendí correctamente, necesito modificar los valores de entrada en un índice de segmento . Entonces, ¿necesitamos algún tipo de función hash con O (1) complejidad? ¿Alguna idea de como hacerlo?

Answer 1

Bucket Sort ya es O (n ^ 2) el peor caso, así que simplemente haría un bucle interno / externo simple aquí. Dado que su matriz de cubos es necesariamente más corta que su matriz de entrada, manténgala en el lazo interno. Dado que está utilizando tamaños personalizados de cubeta, en realidad no existen trucos matemáticos que puedan eliminar ese bucle interno.

int[] freq = new int[buckets.length - 1];
foreach(int d in input)
{
    for(int i = 0; i < buckets.length - 1; i++)
    {
         if(d >= buckets[i] && d < buckets[i+1])
         {
             freq[i]++;
             break;
         }
    }
}

También es O (n ^ 2) el peor caso pero no se puede vencer a la simplicidad del código. No me preocuparía la optimización hasta que se convierta en un problema real. Si tiene una matriz de cubos más grande, puede usar una búsqueda binaria de algún tipo. Pero, como las distribuciones de frecuencia son típicamente <100 elementos, dudo que veas mucho beneficio en el rendimiento en el mundo real.

Answer 2

Si su matriz de entrada representa datos del mundo real (con sus patrones) y la matriz de límites es grande para repetirla una y otra vez en el ciclo interno, puede considerar el siguiente enfoque:

• En primer lugar, clasifique su matriz de entrada. Si trabajas con datos del mundo real, te recomendaría considerar Timsort - Wiki para esto. Proporciona muy buenas garantías de rendimiento para patrones que se pueden ver en datos del mundo real.

• Recorre el conjunto ordenado y compáralo con el primer valor en el conjunto de límites:

  • Si el valor en la matriz de entrada es menor que el límite, incremente el contador de frecuencia para este límite
  • Si el valor en la matriz de entrada es mayor que el límite, vaya al siguiente valor en la matriz de límites e incremente el contador para la nueva frontera.

En un código, puede verse así:

Timsort(myArray);
int boundPos; 
boundaries = GetBoundaries(); //assume the boundaries is a Dictionary<int,int>()

for (int i = 0; i<myArray.Lenght; i++) {
  if (myArray[i]<boundaries[boundPos]) { 
     boundaries[boubdPos]++;
  }
  else {
    boundPos++;
    boundaries[boubdPos]++;
  }
}