¿Es posible simplificar (x == 0 || x == 1) en una sola operación?

106

Así que estaba tratando de escribir el número n 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 de cambio de bits elegante que pueda hacer esto?

user6048670
fuente
111
¿Por qué? Es legible, la intención es muy clara y no es cara. ¿Por qué cambiarlo a una coincidencia de patrones de bits "inteligente" que sea más difícil de entender y no identifique claramente la intención?
D Stanley
9
Esto no es realmente fibonaci, ¿verdad?
n8wrl
9
fibonaci suma los dos valores anteriores. ¿Quisiste decir en fibn(N-1) + fibn(N-2) lugar de N * fibn(N-1)?
juharr
46
Estoy a favor de reducir los nanosegundos, pero si tienes una comparación simple en un método que usa la recursividad, ¿por qué gastar esfuerzo en la eficiencia de la comparación y dejar la recursividad ahí?
Jon Hanna
25
Utiliza una forma recursiva para calcular el número de Fabonacci, ¿entonces quiere mejorar el rendimiento? ¿Por qué no convertirlo en un bucle? o usa potencia rápida?
notbad

Respuestas:

-9

Este también funciona

Math.Sqrt(N) == N 

La raíz cuadrada de 0 y 1 devolverá 0 y 1 respectivamente.

Rahul
fuente
20
Math.Sqrtes una función complicada de punto flotante. ¡Se ejecuta lentamente en comparación con las alternativas de solo enteros!
Nayuki
1
Esto parece limpio, pero hay mejores formas que esto si marca las otras respuestas.
Mafii
9
Si me encontrara con esto en cualquier código en el que estuviera trabajando, probablemente, como mínimo, me acercaría al escritorio de esa persona y le preguntaría qué sustancia estaba consumiendo en ese momento.
a CVn
¿Quién en su sano juicio marcó esta como la respuesta? Sin palabras.
squashed.bugaboo
212

Hay varias formas de implementar su prueba aritmética usando 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 en la práctica, estos formularios son los más legibles, y la pequeña diferencia en el rendimiento no vale la pena usar aritmética bit a bit:

  • x == 0 || x == 1
  • x <= 1(porque xes un entero sin signo)
  • x < 2(porque xes un entero sin signo)
Nayuki
fuente
6
No lo olvides(x & ~1) == 0
Lee Daniel Crocker
71
Pero no apueste a que ninguno de ellos sea "más eficiente". gcc en realidad genera menos código x == 0 || x == 1para (x & ~1) == 0o para (x | 1) == 1. Para el primero, es lo suficientemente inteligente como para reconocerlo como equivalente x <= 1y generar un archivo cmpl; setbe. Los demás lo confunden y hacen que genere peor código.
hobbs
13
x <= 1 o x <2 es más simple.
gnasher729
9
@Kevin True para C ++, porque ese estándar se esfuerza muchísimo por hacer imposible la escritura de código compatible. Afortunadamente, esta es una pregunta sobre C #;)
Voo
5
La mayoría de los compiladores modernos ya pueden optimizar comparaciones como esta, aunque no sé qué tan inteligentes son el compilador C # y .NET JITter. Solo se necesita una única comparación en el código real
phuclv
78

Dado que el argumento está uint( sin firmar ) puede poner

  return (N <= 1) ? 1 : N * fibn(N-1);

Menos legible (en mi humilde opinión) pero si cuentas cada carácter ( Code 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);
Dmitry Bychenko
fuente
12
Si fuera Code Golf, lo sería return N<2?1:f(N-1)+f(n-2). : P
Conor O'Brien
36

También puede verificar que todos los demás bits sean 0 así:

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 los paréntesis porque los operadores bit a bit tienen una prioridad menor que ==.

René Vogt
fuente
¡Me gusta! Gracias.
user6048670
15
1 carácter menos:(N|1)==1
Matt
1
@atk 3 | 1 es 3 porque b0011 | b0001 es b0011
René Vogt
3
@atk Esto es bit a bit o no es lógico o. No hay cortocircuito.
isaacg
2
@Hoten Correcto, pero Matt dijo 1 carácter menos , no 1 operación menos .
Ivan Stoev
20

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. Por supuesto, también hace que escribir la función sea trivial.

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.

Adán
fuente
14

Cómo hacerlo con bitshift

Si desea usar bitshift y hacer que el código sea algo oscuro (pero corto), puede hacer:

public uint fibn ( uint N ) {
   return N >> 1 != 0? fibn(N-1) + finb(N-2): 1;
}

Para un entero sin signo Nen el lenguaje c, N>>1descarta el bit de orden inferior. Si ese resultado es distinto de 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 MUCHO más rápido

Calcule una pasada en lugar de construir implícitamente un árbol del tamaño de 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 han mencionado algunas personas, no se tarda mucho en desbordar incluso un entero de 64 bits sin signo. Dependiendo de qué tan grande esté tratando de llegar, deberá usar números enteros de precisión arbitrarios.

Matthew Gunn
fuente
1
No solo evita el árbol de crecimiento exponencial, sino que también evita la posible ramificación del operador ternario que podría obstruir las tuberías de CPU modernas.
mathreadler
2
Su código 'mucho más rápido' no funcionará en C # porque uintno se puede convertir implícitamente en bool, y la pregunta está etiquetada específicamente como C #.
Pharap
1
@pharap entonces hazlo en su --N != 0lugar. El punto es que algo O (n) es preferible a O (fibn (n)).
Matthew Gunn
1
para ampliar el punto de @ MatthewGunn, O (fib (n)) es O (phi ^ n) (consulte esta derivación stackoverflow.com/a/360773/2788187 )
Connor Clark
@ RenéVogt No soy un desarrollador de ac #. Principalmente estaba tratando de comentar sobre el completo absurdo de un algoritmo O (fibn (N)). ¿Se compila ahora? (Agregué! = 0 ya que c # no trata los resultados distintos de cero como verdaderos). Funciona (y funcionó) en c directo si reemplaza uint con algo estándar como uint64_t.
Matthew Gunn
10

Como 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 recursividad adicional.

derpirscher
fuente
4
@CatthalMF: pero el resultado es el mismo, porque1 * fibn(0) = 1 * 1 = 1
derpirscher
3
¿Tu función no calcula factorial, no fibonacci?
Barmar
2
@Barmar sí, de hecho eso es factorial, porque esa era la pregunta original
derpirscher
3
Sería mejor no llamarlo fibnentonces
pie3636
1
@ pie3636 lo llamé fibn porque así es como se llamó en la pregunta original y no actualicé la respuesta más tarde
derpirscher
6

Simplemente verifique si Nes <= 1 ya que sabe que N no está firmado, solo puede haber 2 condiciones que den N <= 1como resultado TRUE: 0 y 1

public uint fibn ( uint N ) 
{
   return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}
James
fuente
¿Importa siquiera si está firmado o no? El algoritmo produce una recursión infinita con entradas negativas, por lo que no hay nada de malo en tratarlas equivalentes a 0 o 1.
Barmar
@Barmar seguro que importa, sobre todo en este caso concreto. El OP preguntó si podía simplificar exactamente (N == 0 || N == 1). Sabes que no será menor que 0 (¡porque entonces estaría firmado!), Y el máximo podría ser 1. lo N <= 1simplifica. Supongo que el tipo sin firmar no está garantizado, pero eso debería manejarse en otro lugar, diría yo.
james
Mi punto es que si se declarara int Ny se mantuviera la condición original, se repetirá infinitamente cuando N sea negativo con su condición original. Dado que ese es un comportamiento indefinido, en realidad no tenemos que preocuparnos por ello. Entonces podemos asumir que N no es negativo, independientemente de la declaración.
Barmar
O podemos hacer lo que queramos con entradas negativas, incluso tratarlas como el caso base de la recursividad.
Barmar
@Barmar está bastante seguro de que uint siempre se convertirá a unsigned si intenta establecerlo en negativo
james
6

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 [...] a una sola comparación ...

No es necesario el cambio de bits o algo así, 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, existe 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 ninguna mutación, lo que lo hace utilizable en un enfoque funcional puro.

fede s.
fuente
4

Aquí está mi solución, no hay mucho para 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.

ingrese la descripción de la imagen aquí

Llevándolo más lejos para forzar a la caja del interruptor a 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);
    }
}
Khaled.K
fuente
1
La ventaja de su solución es que solo se calcula cuando es necesario. Lo mejor sería una tabla de búsqueda. bonificación alternativa: f (n-1) = someCalcOf (f (n-2)), por lo que no se necesita la repetición completa.
Karsten
@Karsten He agregado suficientes valores para que el interruptor cree una tabla de búsqueda para él. No estoy seguro de cómo funciona el bono alternativo.
Khaled.K
1
¿Cómo responde esto a la pregunta?
Clark Kent
@SaviourSelf se reduce a una tabla de búsqueda, y está el aspecto visual explicado en la respuesta. stackoverflow.com/a/395965/2128327
Khaled.K
¿Por qué usarías un switchcuando puedes tener una variedad de respuestas?
Nayuki
4

para N es uint, solo use

N <= 1
Yanghaogn
fuente
Exactamente lo que estaba pensando; ¡N es uint! Esta debería ser la respuesta, de verdad.
squashed.bugaboo
1

La respuesta de Dmitry es la mejor, pero si fuera un tipo de retorno Int32 y tuviera un conjunto más grande de enteros para elegir, podría hacer esto.

return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);
CathalMF
fuente
2
¿Cómo es eso más corto que el original?
MCMastery
2
@MCMastery No es más corto. Como mencioné, es mejor si el tipo de retorno original es un int32 y está seleccionando entre un gran conjunto de números válidos. En lugar de tener que escribir (N == -1 || N == 0 || N == 1 || N == 2)
CathalMF
1
Las razones de OP parecen estar relacionadas con la optimización. Esta es una mala idea por varias razones: 1) instanciar un nuevo objeto dentro de cada llamada recursiva es una muy mala idea, 2) List.Containses O (n), 3) simplemente hacer dos comparaciones en su lugar ( N > -3 && N < 3) daría un código más corto y más legible.
Groo
@Groo ¿Y si los valores fueran -10, -2, 5, 7, 13?
CathalMF
No es lo que pidió OP. Pero de todos modos, todavía 1) no querría crear una nueva instancia en cada llamada, 2) sería mejor usar un (único) hashset en su lugar, 3) para un problema específico, también podría optimizar la función hash para Sea puro, o incluso use operaciones bit a bit inteligentemente organizadas como se sugiere en otras respuestas.
Groo
0

La secuencia de Fibonacci es una serie de números donde un número se encuentra 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 Nen este caso comienza desde 1, no es 0-basedcomo un índice de matriz.

Usando la función de cuerpo de expresión de 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);
Artru
fuente
-2

Un poco tarde para la fiesta, pero también podrías hacerlo (x==!!x)

!!xconvierte el valor a 1si no lo es 0, y lo deja 0si lo es.
Utilizo mucho este tipo de cosas en la ofuscación de C.

Nota: Esto es C, no estoy seguro si funciona en C #

Una noche normal
fuente
4
No estoy seguro de por qué se votó a favor. Incluso superficial de intentar esto como uint n = 1; if (n == !!n) { }da Operator '!' cannot be applied to operand of type 'uint'en el !nen C #. El hecho de que algo funcione en C no significa que funcione en C #; incluso #include <stdio.h>no funciona en C #, porque C # no tiene la directiva de preprocesador "incluir". Los lenguajes son más diferentes que C y C ++.
a CVn
2
Oh. Bueno. Lo siento :(
Una noche normal
@OneNormalNight (x == !! x) Cómo funcionará esto. Considere que mi entrada es 5. (5 == !! 5). Dará resultado como verdadero
VINOTH ENERGETIC
1
@VinothKumar !! 5 evalúa a 1. (5 == !! 5) evalúa (5 == 1) que evalúa a falso.
Una noche normal
@OneNormalNight, sí, lo tengo ahora. ! (5) da 1 nuevamente aplicado da 0. No 1.
VINOTH ENERGETIC
-3

Así que creé uno Listde estos enteros especiales y verifiqué si Npertenece a él.

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 Containsse 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)

Puede que esta no sea la forma más rápida de hacerlo, pero para mí, parece ser un estilo mejor.

KnorxThieus
fuente