practicar - matrices en c# ejercicios resueltos

¿Por qué es más rápido calcular el producto de una matriz consecutiva de enteros al realizar el cálculo en pares?

Question

Estaba intentando crear mi propia función factorial cuando descubrí que el cálculo es el doble de rápido si se calcula en pares. Me gusta esto:

Grupos de 1: 2 * 3 * 4 ... 50000 * 50001 = 4.1 segundos

Grupos de 2: (2 * 3) * (4 * 5) * (6 * 7) ... (50000 * 50001) = 2.0 segundos

Grupos de 3: (2 * 3 * 4) * (5 * 6 * 7) ... (49999 * 50000 * 50001) = 4.8 segundos

Aquí está el c # que solía probar esto.

Stopwatch timer = new Stopwatch();
timer.Start();

// Seperate the calculation into groups of this size.
int k = 2;

BigInteger total = 1;

// Iterates from 2 to 50002, but instead of incrementing ''i'' by one, it increments it ''k'' times,
// and the inner loop calculates the product of ''i'' to ''i+k'', and multiplies ''total'' by that result.
for (var i = 2; i < 50000 + 2; i += k)
{
    BigInteger partialTotal = 1;
    for (var j = 0; j < k; j++)
    {
        // Stops if it exceeds 50000.
        if (i + j >= 50000) break;
        partialTotal *= i + j;
    }
    total *= partialTotal;
}

Console.WriteLine(timer.ElapsedMilliseconds / 1000.0 + "s");

Probé esto en diferentes niveles y puse los tiempos promedio de algunas pruebas en un gráfico de barras. Esperaba que fuera más eficiente a medida que aumentaba el número de grupos, pero 3 era el menos eficiente y 4 no tenían mejoría que los grupos de 1.

Enlace a First Data

Enlace a Second Data

¿Qué causa esta diferencia, y hay una manera óptima de calcular esto?

Answer 1

Creo que tienes un error (''+'' en lugar de ''*'').

parcial Total = = i + j;

Es bueno comprobar que está obteniendo la respuesta correcta, no solo métricas de rendimiento interesantes.

Pero tengo curiosidad por lo que te motivó a probar esto. Si encuentra una diferencia, esperaría que tuviera que ver con las optimidades en el registro y / o la asignación de memoria. Y yo esperaría que fuera 0-30% o algo así, no 50%.

Answer 2

El tiempo requerido para hacer una multiplicación de BigInteger depende del tamaño del producto.

Ambos métodos toman el mismo número de multiplicaciones, pero si multiplicas los factores en pares, entonces el tamaño promedio del producto es mucho menor de lo que es si multiplicas cada factor con el producto de todos los más pequeños.

Puede hacerlo aún mejor si siempre multiplica los dos factores más pequeños (factores originales o productos intermedios) que aún no se han multiplicado, hasta que llegue al producto completo.

Answer 3

BigInteger tiene un caso rápido para números de 31 bits o menos. Cuando haces una multiplicación por pares, esto significa que se toma una ruta rápida específica, que multiplica los valores en un solo ulong y establece el valor de manera más explícita:

public void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2) {
  ...
  if (reg1._iuLast == 0) {
    if (reg2._iuLast == 0)
      Set((ulong)reg1._uSmall * reg2._uSmall);
    else {
      ...
    }
  }
  else if (reg2._iuLast == 0) {
    ...
  }
  else {
    ...
  }
}

public void Set(ulong uu) {
  uint uHi = NumericsHelpers.GetHi(uu);
  if (uHi == 0) {
    _uSmall = NumericsHelpers.GetLo(uu);
    _iuLast = 0;
  }
  else {
    SetSizeLazy(2);
    _rgu[0] = (uint)uu;
    _rgu[1] = uHi;
  }
  AssertValid(true);
}

Una rama 100% predecible como esta es perfecta para un JIT, y esta ruta rápida debería optimizarse extremadamente bien. Es posible que _rgu[0] y _rgu[1] estén incluso en línea. Esto es extremadamente barato, por lo que efectivamente reduce el número de operaciones reales en un factor de dos.

Entonces, ¿por qué un grupo de tres es mucho más lento? Es obvio que debería ser más lento que para k = 2 ; Tienes muchas menos multiplicaciones optimizadas. Más interesante es por qué es más lento que k = 1 . Esto se explica fácilmente por el hecho de que la multiplicación externa del total ahora alcanza el camino lento. Para k = 2 este impacto se mitiga al reducir a la mitad el número de multiplicaciones y el potencial de alineación de la matriz.

Sin embargo, estos factores no ayudan a k = 3 , y de hecho, el caso lento duele k = 3 mucho más. La segunda multiplicación en el caso k = 3 golpea este caso

  if (reg1._iuLast == 0) {
    ...
  }
  else if (reg2._iuLast == 0) {
    Load(ref reg1, 1);
    Mul(reg2._uSmall);
  }
  else {
    ...
  }

que asigna

  EnsureWritable(1);

  uint uCarry = 0;
  for (int iu = 0; iu <= _iuLast; iu++)
    uCarry = MulCarry(ref _rgu[iu], u, uCarry);

  if (uCarry != 0) {
    SetSizeKeep(_iuLast + 2, 0);
    _rgu[_iuLast] = uCarry;
  }

¿Por qué importa esto? Bueno, EnsureWritable(1) causa

uint[] rgu = new uint[_iuLast + 1 + cuExtra];

entonces rgu convierte en longitud 3 . El número de pases en el código total se decide en

public void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2)

como

    for (int iu1 = 0; iu1 < cu1; iu1++) {
      ...
      for (int iu2 = 0; iu2 < cu2; iu2++, iuRes++)
        uCarry = AddMulCarry(ref _rgu[iuRes], uCur, rgu2[iu2], uCarry);
      ...
    }

lo que significa que tenemos un total de operaciones len(total._rgu) * 3 . ¡Esto no nos ha salvado nada! Solo hay len(total._rgu) * 1 pases para k = 1 , ¡solo lo hacemos tres veces!

En realidad, existe una optimización en el bucle externo que reduce esto a len(total._rgu) * 2 :

      uint uCur = rgu1[iu1];
      if (uCur == 0)
        continue;

Sin embargo, "optimizan" esta optimización de una manera que duele mucho más que antes:

if (reg1.CuNonZero <= reg2.CuNonZero) {
  rgu1 = reg1._rgu; cu1 = reg1._iuLast + 1;
  rgu2 = reg2._rgu; cu2 = reg2._iuLast + 1;
}
else {
  rgu1 = reg2._rgu; cu1 = reg2._iuLast + 1;
  rgu2 = reg1._rgu; cu2 = reg1._iuLast + 1;
}

Para k = 2 , eso hace que el bucle externo sea superior al total , ya que reg2 no contiene valores cero con alta probabilidad. Esto es genial porque el total es mucho más largo que el total partialTotal , por lo tanto, partialTotal menos pases, mejor. Para k = 3 , el EnsureWritable(1) siempre causará un espacio libre porque la multiplicación de tres números de no más de 15 bits nunca puede exceder de 64 bits. Esto significa que, aunque todavía solo hacemos una pasada sobre el total para k = 2 , ¡hacemos dos para k = 3 !

Esto comienza a explicar por qué la velocidad vuelve a aumentar más allá de k = 3 : el número de pasadas por adición aumenta más lentamente que el número de adiciones disminuye, ya que solo se agregan ~ 15 bits al valor interno cada vez. Las multiplicaciones internas son rápidas en relación con las multiplicaciones total masivas, de modo que cuanto más tiempo se invierte en consolidar los valores, más tiempo se ahorra en pases sobre el total . Además, la optimización es menos frecuente un pesimismo.

También explica por qué los valores impares tardan más tiempo: agregan un entero de 32 bits adicional a la matriz _rgu . Esto no sucederá tan limpiamente si los ~ 15 bits no estuvieran tan cerca de la mitad de 32.

Vale la pena señalar que hay muchas maneras de mejorar este código; Los comentarios aquí son acerca de por qué , no cómo solucionarlo. La mejora más fácil sería lanzar los valores en un montón y multiplicar solo los dos valores más pequeños a la vez.