cref - remarks c#
¿Es posible simplificar(x== 0 || x== 1) en una sola operación? (15)
Entonces estaba tratando de escribir el enésimo número en la secuencia de Fibonacci en una función lo más compacta posible:
public uint fibn ( uint N )
{
return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}
Pero me pregunto si puedo hacer esto aún más compacto y eficiente cambiando
(N == 0 || N == 1)
en una sola comparación. ¿Hay alguna operación elegante de cambio de bits que pueda hacer esto?
Cómo hacerlo con bitshift
Si desea utilizar bitshift y hacer que el código sea algo oscuro (pero corto), puede hacer lo siguiente:
public uint fibn ( uint N ) {
return N >> 1 != 0? fibn(N-1) + finb(N-2): 1;
}
Para un entero sin signo
N
en el lenguaje c,
N>>1
arroja el bit de orden inferior.
Si ese resultado no es cero, implica que N es mayor que 1.
Nota: este algoritmo es terriblemente ineficiente ya que recalcula innecesariamente valores en la secuencia que ya se han calculado.
Algo mucho más rápido
Calcule una pasada en lugar de construir implícitamente un árbol de tamaño fibonaci (N):
uint faster_fibn(uint N) { //requires N > 1 to work
uint a = 1, b = 1, c = 1;
while(--N != 0) {
c = b + a;
a = b;
b = c;
}
return c;
}
Como algunas personas han mencionado, no lleva mucho tiempo desbordar incluso un entero sin signo de 64 bits. Dependiendo de qué tan grande intente ir, necesitará usar enteros de precisión arbitrarios.
A medida que usa un uint, que no puede ser negativo, puede verificar si
n < 2
EDITAR
O para ese caso de función especial, podría escribirlo de la siguiente manera:
public uint fibn(uint N)
return (N == 0) ? 1 : N * fibn(N-1);
}
lo que conducirá al mismo resultado, por supuesto a costa de un paso de recursión adicional.
Aquí está mi solución, no hay mucho en optimizar esta función simple, por otro lado, lo que estoy ofreciendo aquí es la legibilidad como una definición matemática de la función recursiva.
public uint fibn(uint N)
{
switch(N)
{
case 0: return 1;
case 1: return 1;
default: return fibn(N-1) + fibn(N-2);
}
}
La definición matemática del número de Fibonacci de manera similar.
Llevándolo más allá para forzar la caja del interruptor para construir una tabla de búsqueda.
public uint fibn(uint N)
{
switch(N)
{
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 3;
case 4: return 5;
case 5: return 8;
case 6: return 13;
case 7: return 21;
case 8: return 34;
case 9: return 55;
case 10: return 89;
case 11: return 144;
case 12: return 233;
case 13: return 377;
case 14: return 610;
case 15: return 987;
case 16: return 1597;
case 17: return 2584;
case 18: return 4181;
case 19: return 6765;
case 20: return 10946;
case 21: return 17711;
case 22: return 28657;
case 23: return 46368;
case 24: return 75025;
case 25: return 121393;
case 26: return 196418;
case 27: return 317811;
case 28: return 514229;
case 29: return 832040;
case 30: return 1346269;
case 31: return 2178309;
case 32: return 3524578;
case 33: return 5702887;
case 34: return 9227465;
case 35: return 14930352;
case 36: return 24157817;
case 37: return 39088169;
case 38: return 63245986;
case 39: return 102334155;
case 40: return 165580141;
case 41: return 267914296;
case 42: return 433494437;
case 43: return 701408733;
case 44: return 1134903170;
case 45: return 1836311903;
case 46: return 2971215073;
default: return fibn(N-1) + fibn(N-2);
}
}
Así que creé una
List
de estos enteros especiales y verifiqué si
N
pertenece.
static List<uint> ints = new List<uint> { 0, 1 };
public uint fibn(uint N)
{
return ints.Contains(N) ? 1 : fibn(N-1) + fibn(N-2);
}
También puede usar un método de extensión para diferentes propósitos donde
Contains
se llama solo una vez (por ejemplo, cuando su aplicación está iniciando y cargando datos).
Esto proporciona un estilo más claro y aclara la relación principal con su valor (
N
):
static class ObjectHelper
{
public static bool PertainsTo<T>(this T obj, IEnumerable<T> enumerable)
{
return (enumerable is List<T> ? (List<T>) enumerable : enumerable.ToList()).Contains(obj);
}
}
Apliquelo:
N.PertainsTo(ints)
Esta podría no ser la forma más rápida de hacerlo, pero para mí, parece ser un mejor estilo.
Como el argumento es
uint
(
sin signo
), puede poner
return (N <= 1) ? 1 : N * fibn(N-1);
Menos legible (en mi humilde opinión) pero si cuenta cada personaje ( código de golf o similar)
return N < 2 ? 1 : N * fibn(N-1);
Editar : para su pregunta editada :
return (N <= 1) ? 1 : fibn(N-1) + fibn(N-2);
O
return N < 2 ? 1 : fibn(N-1) + fibn(N-2);
Este también funciona
Math.Sqrt(N) == N
raíz cuadrada de 0 y 1 devolverá 0 y 1 respectivamente.
Hay varias formas de implementar su prueba aritmética utilizando aritmética bit a bit. Tu expresión:
-
x == 0 || x == 1
es lógicamente equivalente a cada uno de estos:
-
(x & 1) == x -
(x & ~1) == 0 -
(x | 1) == 1 -
(~x | 1) == (uint)-1 -
x >> 1 == 0
Prima:
-
x * x == x(la prueba requiere un poco de esfuerzo)
Pero prácticamente hablando, estas formas son las más legibles, y la pequeña diferencia en el rendimiento realmente no vale la pena usar aritmética bit a bit:
-
x == 0 || x == 1 -
x <= 1(porquexes un entero sin signo) -
x < 2(porquexes un entero sin signo)
La respuesta de Dmitry es la mejor, pero si se tratara de un tipo de retorno Int32 y tuviera un conjunto más grande de números enteros para elegir, podría hacerlo.
return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);
La secuencia de Fibonacci es una serie de números donde se encuentra un número sumando los dos números anteriores. Hay dos tipos de puntos de partida: ( 0,1 , 1,2, ..) y ( 1,1 , 2,3).
-----------------------------------------
Position(N)| Value type 1 | Value type 2
-----------------------------------------
1 | 0 | 1
2 | 1 | 1
3 | 1 | 2
4 | 2 | 3
5 | 3 | 5
6 | 5 | 8
7 | 8 | 13
-----------------------------------------
La posición
N
en este caso comienza desde
1
, no está
0-based
como un índice de matriz.
Usando la función de cuerpo de expresión C # 6 y la sugerencia de Dmitry sobre el operador ternario, podemos escribir una función de una línea con el cálculo correcto para el tipo 1:
public uint fibn(uint N) => N<3? N-1: fibn(N-1)+fibn(N-2);
y para el tipo 2:
public uint fibn(uint N) => N<3? 1: fibn(N-1)+fibn(N-2);
Si lo que desea hacer es hacer que la función sea más eficiente, utilice una tabla de búsqueda. La tabla de búsqueda es sorprendentemente pequeña con solo 47 entradas: la siguiente entrada desbordaría un entero sin signo de 32 bits. También, por supuesto, hace que la función sea trivial para escribir.
class Sequences
{
// Store the complete list of values that will fit in a 32-bit unsigned integer without overflow.
private static readonly uint[] FibonacciSequence = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073
};
public uint fibn(uint N)
{
return FibonacciSequence[N];
}
}
Obviamente, puedes hacer lo mismo con los factoriales.
Simplemente verifique si
N
es <= 1 ya que sabe que N no está firmado, solo puede haber 2 condiciones en las que
N <= 1
resulte
TRUE
: 0 y 1
public uint fibn ( uint N )
{
return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}
También puede verificar que todos los demás bits sean 0 como este:
return (N & ~1) == 0 ? 1 : N * fibn(N-1);
Para completar gracias a Matt la solución aún mejor:
return (N | 1) == 1 ? 1 : N * fibn(N-1);
En ambos casos, debe cuidar el paréntesis porque los operadores bit a bit tienen menor prioridad que
==
.
Un poco tarde para la fiesta, pero también podrías hacerlo
(x==!!x)
!!x
convierte el valor a en
1
si no es
0
, y lo deja en
0
si lo es.
Utilizo mucho este tipo de ofuscación en C.
Nota: Esto es C, no estoy seguro si funciona en C #
para N es uint, solo use
N <= 1
Descargo de responsabilidad: no sé C #, y no probé este código:
Pero me pregunto si puedo hacer esto aún más compacto y eficiente cambiando [...] en una sola comparación ...
No es necesario realizar cambios de bits ni nada parecido, esto usa solo una comparación, y debería ser mucho más eficiente (¿O (n) vs O (2 ^ n), creo?). El cuerpo de la función es más compacto , aunque termina siendo un poco más largo con la declaración.
(Para eliminar la sobrecarga de la recursividad, está la versión iterativa, como en la respuesta de Mathew Gunn )
public uint fibn ( uint N, uint B=1, uint A=0 )
{
return N == 0 ? A : fibn( N--, A+B, B );
}
fibn( 5 ) =
fibn( 5, 1, 0 ) =
return 5 == 0 ? 0 : fibn( 5--, 0+1, 1 ) =
fibn( 4, 1, 1 ) =
return 4 == 0 ? 1 : fibn( 4--, 1+1, 1 ) =
fibn( 3, 2, 1 ) =
return 3 == 0 ? 1 : fibn( 3--, 1+2, 2 ) =
fibn( 2, 3, 2 ) =
return 2 == 0 ? 2 : fibn( 2--, 2+3, 3 ) =
fibn( 1, 5, 3 ) =
return 1 == 0 ? 3 : fibn( 1--, 3+5, 5 ) =
fibn( 0, 8, 5 ) =
return 0 == 0 ? 5 : fibn( 0--, 5+8, 8 ) =
5
fibn(5)=5
PD: este es un patrón funcional común para la iteración con acumuladores.
Si reemplaza
N--
con
N-1
, efectivamente no está usando mutación, lo que lo hace utilizable en un enfoque funcional puro.