Est-il possible de simplifier (x == 0 || x == 1) en une seule opération?

106

J'essayais donc d'écrire le n ème nombre dans la séquence de Fibonacci dans une fonction aussi compacte que possible:

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

Mais je me demande si je peux rendre cela encore plus compact et efficace en changeant

(N == 0 || N == 1)

en une seule comparaison. Existe-t-il une opération de décalage de bits sophistiquée qui peut faire cela?

utilisateur6048670
la source
111
Pourquoi? C'est lisible, l'intention est très claire et ce n'est pas cher. Pourquoi le remplacer par une correspondance de motif de bits "intelligente" qui est plus difficile à comprendre et n'identifie pas clairement l'intention?
D Stanley
9
Ce n'est pas vraiment fibonaci, non?
n8wrl
9
fibonaci ajoute les deux valeurs précédentes. Voulez-vous dire fibn(N-1) + fibn(N-2) au lieu de N * fibn(N-1)?
juharr
46
Je suis tout à fait pour raser les nanosecondes, mais si vous avez une comparaison simple dans une méthode qui utilise la récursivité, pourquoi dépenser des efforts sur l'efficacité de la comparaison et laisser la récursivité là-bas?
Jon Hanna
25
Vous utilisez une méthode récursive pour calculer le nombre de Fabonacci, alors vous souhaitez améliorer les performances? Pourquoi ne pas le changer en boucle? ou utiliser une puissance rapide?
notbad

Réponses:

-9

Celui-ci fonctionne également

Math.Sqrt(N) == N 

la racine carrée de 0 et 1 renverra respectivement 0 et 1.

Rahul
la source
20
Math.Sqrtest une fonction à virgule flottante compliquée. Il fonctionne lentement par rapport aux alternatives uniquement entiers !!
Nayuki
1
Cela semble propre, mais il existe de meilleures façons que cela si vous vérifiez les autres réponses.
Mafii
9
Si je rencontrais cela dans un code sur lequel je travaillais, je me rendrais probablement au moins au bureau de cette personne et lui demanderais ostensiblement quelle substance elle consommait à ce moment-là.
un CVn le
Qui, sain d'esprit, a indiqué que c'était la réponse? Muet.
squashed.bugaboo
212

Il existe plusieurs façons d'implémenter votre test arithmétique en utilisant l'arithmétique au niveau du bit. Votre expression:

  • x == 0 || x == 1

est logiquement équivalent à chacun de ceux-ci:

  • (x & 1) == x
  • (x & ~1) == 0
  • (x | 1) == 1
  • (~x | 1) == (uint)-1
  • x >> 1 == 0

Prime:

  • x * x == x (la preuve demande un peu d'effort)

Mais en pratique, ces formulaires sont les plus lisibles, et la petite différence de performances ne vaut pas vraiment la peine d'utiliser l'arithmétique au niveau du bit:

  • x == 0 || x == 1
  • x <= 1(car xest un entier non signé)
  • x < 2(car xest un entier non signé)
Nayuki
la source
6
N'oubliez pas(x & ~1) == 0
Lee Daniel Crocker
71
Mais ne pariez pas que l'un d'entre eux soit "plus efficace". gcc génère en fait moins de code pour x == 0 || x == 1que pour (x & ~1) == 0ou (x | 1) == 1. Pour le premier, il est assez intelligent pour le reconnaître comme étant équivalent à x <= 1un simple cmpl; setbe. Les autres le confondent et le font générer un code pire.
hobbs
13
x <= 1 ou x <2 est plus simple.
gnasher729
9
@Kevin True pour C ++, car ce standard essaie vraiment, vraiment très fort de rendre impossible l'écriture de code conforme. Heureusement, c'est une question sur C #;)
Voo
5
La plupart des compilateurs modernes peuvent déjà optimiser des comparaisons comme celle-ci bien que je ne sache pas à quel point le compilateur C # et .NET JITter sont intelligents. Une seule comparaison est nécessaire dans le code réel
phuclv
78

Puisque l'argument est uint( non signé ), vous pouvez mettre

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

Moins lisible (IMHO) mais si vous comptez chaque caractère ( Code Golf ou similaire)

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

Modifier : pour votre question modifiée :

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

Ou

  return N < 2 ? 1 : fibn(N-1) + fibn(N-2);
Dmitry Bychenko
la source
12
Si c'était Code Golf, ça le serait return N<2?1:f(N-1)+f(n-2). : P
Conor O'Brien
36

Vous pouvez également vérifier que tous les autres bits sont à 0 comme ceci:

return (N & ~1) == 0 ? 1 : N * fibn(N-1);

Pour être complet grâce à Matt, la solution encore meilleure:

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

Dans les deux cas, vous devez faire attention aux parenthèses car les opérateurs au niveau du bit ont une priorité inférieure à ==.

René Vogt
la source
Je l'aime! Merci.
user6048670
15
1 caractère de moins:(N|1)==1
Matt
1
@atk 3 | 1 est 3 parce que b0011 | b0001 est b0011
René Vogt
3
@atk C'est au niveau du bit ou, pas logique ou. Il n'y a pas de court-circuit.
isaacg le
2
@Hoten Correct, mais Matt a dit 1 caractère de moins , pas 1 opération de moins .
Ivan Stoev
20

Si vous souhaitez rendre la fonction plus efficace, utilisez une table de recherche. La table de recherche est étonnamment petite avec seulement 47 entrées - l'entrée suivante déborderait d'un entier non signé de 32 bits. Cela rend également la fonction facile à écrire.

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];
    }
}

Vous pouvez évidemment faire la même chose pour les factorielles.

Adam
la source
14

Comment le faire avec bitshift

Si vous voulez utiliser bitshift et rendre le code quelque peu obscur (mais court), vous pouvez faire:

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

Pour un entier non signé Ndans la langue c, N>>1jette le bit de poids faible. Si ce résultat est non nul, cela implique que N est supérieur à 1.

Remarque: cet algorithme est horriblement inefficace car il recalcule inutilement les valeurs de la séquence qui ont déjà été calculées.

Quelque chose de beaucoup plus rapide

Calculez-le en une seule passe plutôt que de construire implicitement un arbre de taille 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;
}

Comme certains l'ont mentionné, il ne faut pas longtemps pour déborder même un entier non signé de 64 bits. En fonction de la taille que vous essayez d'atteindre, vous devrez utiliser des entiers de précision arbitraires.

Matthew Gunn
la source
1
Non seulement en évitant l'arbre à croissance exponentielle, mais vous évitez également la ramification potentielle de l'opérateur ternaire qui pourrait obstruer les pipelines de CPU modernes.
mathreadler le
2
Votre code `` bien plus rapide '' ne fonctionnera pas en C # car il uintn'est pas implicitement convertible en bool, et la question est spécifiquement marquée comme C #.
Pharap
1
@pharap alors faites-le à la --N != 0place. Le fait est que quelque chose de O (n) est préférable à O (fibn (n)).
Matthew Gunn
1
pour développer le point de @ MatthewGunn, O (fib (n)) est O (phi ^ n) (voir cette dérivation stackoverflow.com/a/360773/2788187 )
Connor Clark
@ RenéVogt Je ne suis pas développeur ac #. J'essayais surtout de commenter l'absurdité complète d'un algorithme O (fibn (N)). Compile-t-il maintenant? (J'ai ajouté! = 0 car c # ne traite pas les résultats non nuls comme vrais.) Cela fonctionne (et a fonctionné) en c droit si vous remplacez uint par quelque chose de standard comme uint64_t.
Matthew Gunn
10

Lorsque vous utilisez un uint, qui ne peut pas être négatif, vous pouvez vérifier si n < 2

ÉDITER

Ou pour ce cas de fonction spécial, vous pouvez l'écrire comme suit:

public uint fibn(uint N)
    return (N == 0) ? 1 : N * fibn(N-1);
}

ce qui conduira au même résultat, bien entendu au prix d'une étape de récursion supplémentaire.

derpirscher
la source
4
@CatthalMF: mais le résultat est le même, car1 * fibn(0) = 1 * 1 = 1
derpirscher
3
Votre fonction n'est-elle pas calculatrice factorielle, pas fibonacci?
Barmar le
2
@Barmar oui, en effet c'est factoriel, car c'était la question d'origine
derpirscher
3
Il serait peut-être préférable de ne pas l'appeler fibnalors
pie3636
1
@ pie3636 je l'ai appelé fibn parce que c'est comme ça qu'il a été appelé dans la question d'origine et je n'ai pas mis à jour la réponse plus tard
derpirscher
6

Vérifiez simplement si Nest <= 1 puisque vous savez que N est non signé, il ne peut y avoir que 2 conditions N <= 1qui aboutissent à TRUE: 0 et 1

public uint fibn ( uint N ) 
{
   return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}
James
la source
Est-ce même important qu'il soit signé ou non signé? L'algorithme produit une récursivité infinie avec des entrées négatives, il n'y a donc aucun mal à les traiter équivalentes à 0 ou 1.
Barmar
@Barmar est sûr que cela compte, surtout dans ce cas précis. Le PO a demandé s'il pouvait simplifier exactement (N == 0 || N == 1). Vous savez qu'il ne sera pas inférieur à 0 (car alors il serait signé!), Et le maximum pourrait être 1. N <= 1simplifie les choses. Je suppose que le type non signé n'est pas garanti, mais cela devrait être traité ailleurs, je dirais.
james
Mon point est que si elle était déclarée int N, et que vous gardiez la condition d'origine, elle se répéterait indéfiniment lorsque N est négatif avec sa condition d'origine. Puisque ce comportement n'est pas défini, nous n'avons pas vraiment besoin de nous en préoccuper. On peut donc supposer que N est non négatif, quelle que soit la déclaration.
Barmar le
Ou nous pouvons faire tout ce que nous voulons avec des entrées négatives, y compris les traiter comme le cas de base de la récursivité.
Barmar
@Barmar à peu près sûr que uint sera toujours converti en non signé si vous essayez de le définir sur négatif
James
6

Avertissement: je ne connais pas C # et n'ai pas testé ce code:

Mais je me demande si je peux rendre cela encore plus compact et efficace en [...] changeant en une seule comparaison ...

Pas besoin de bitshifting ou autre, cela n'utilise qu'une seule comparaison, et cela devrait être beaucoup plus efficace (O (n) vs O (2 ^ n) je pense?). Le corps de la fonction est plus compact , bien qu'il finisse par être un peu plus long avec la déclaration.

(Pour supprimer la surcharge de la récursivité, il y a la version itérative, comme dans la réponse 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

PS: Il s'agit d'un modèle fonctionnel courant pour l'itération avec des accumulateurs. Si vous remplacez N--par, N-1vous n'utilisez effectivement aucune mutation, ce qui le rend utilisable dans une approche purement fonctionnelle.

fede s.
la source
4

Voici ma solution, il n'y a pas grand chose à optimiser cette fonction simple, par contre ce que je propose ici, c'est la lisibilité en tant que définition mathématique de la fonction récursive.

public uint fibn(uint N) 
{
    switch(N)
    {
        case  0: return 1;

        case  1: return 1;

        default: return fibn(N-1) + fibn(N-2);
    }
}

La définition mathématique du nombre de Fibonacci d'une manière similaire.

entrez la description de l'image ici

En allant plus loin pour forcer le boîtier de commutation à créer une table de recherche.

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
la source
1
L'avantage de votre solution est qu'elle n'est calculée qu'en cas de besoin. Le mieux serait une table de consultation. bonus alternatif: f (n-1) = someCalcOf (f (n-2)), donc pas la réexécution complète n'est nécessaire.
Karsten
@Karsten J'ai ajouté suffisamment de valeurs pour que le commutateur crée une table de recherche pour celui-ci. Je ne sais pas comment fonctionne le bonus alternatif.
Khaled.K
1
Comment cela répond-il à la question?
Clark Kent
@SaviourSelf, cela se résume à une table de consultation, et il y a l'aspect visuel expliqué dans la réponse. stackoverflow.com/a/395965/2128327
Khaled.K
Pourquoi utiliseriez-vous un switchlorsque vous pouvez avoir un éventail de réponses?
Nayuki
4

car N est uint, il suffit d'utiliser

N <= 1
Yanghaogn
la source
Exactement ce à quoi je pensais; N est uint! Cela devrait être la réponse, vraiment.
squashed.bugaboo
1

La réponse de Dmitry est la meilleure, mais s'il s'agissait d'un type de retour Int32 et que vous disposiez d'un plus grand ensemble d'entiers, vous pourriez le faire.

return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);
CathalMF
la source
2
En quoi est-ce plus court que l'original?
MCMastery
2
@MCMastery Ce n'est pas plus court. Comme je l'ai mentionné, ce n'est mieux si le type de retour d'origine est un int32 et qu'il sélectionne parmi un grand ensemble de nombres valides. Au lieu d'avoir à écrire (N == -1 || N == 0 || N == 1 || N == 2)
CathalMF
1
Les raisons d'OP semblent être liées à l'optimisation. C'est une mauvaise idée pour plusieurs raisons: 1) instancier un nouvel objet à l'intérieur de chaque appel récursif est une très mauvaise idée, 2) List.Containsest O (n), 3) simplement faire deux comparaisons à la place ( N > -3 && N < 3) donnerait un code plus court et plus lisible.
Groo
@Groo Et si les valeurs étaient -10, -2, 5, 7, 13
CathalMF
Ce n'est pas ce que OP a demandé. Mais de toute façon, vous ne voudriez toujours pas 1) créer une nouvelle instance à chaque appel, 2) mieux utiliser un (unique) hashset à la place, 3) pour un problème spécifique, vous seriez également en mesure d'optimiser la fonction de hachage pour être pur, ou même utiliser des opérations au niveau du bit intelligemment arrangées comme suggéré dans d'autres réponses.
Groo
0

La séquence de Fibonacci est une série de nombres où un nombre est trouvé en additionnant les deux nombres qui le précèdent. Il existe deux types de points de départ: ( 0,1 , 1,2, ..) et ( 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 position Ndans ce cas commence à partir de 1, ce n'est pas 0-basedcomme un index de tableau.

En utilisant la fonction Expression-body C # 6 et la suggestion de Dmitry sur l' opérateur ternaire, nous pouvons écrire une fonction sur une ligne avec un calcul correct pour le type 1:

public uint fibn(uint N) => N<3? N-1: fibn(N-1)+fibn(N-2);

et pour le type 2:

public uint fibn(uint N) => N<3? 1: fibn(N-1)+fibn(N-2);
Artru
la source
-2

Un peu tard à la fête, mais tu pourrais aussi faire (x==!!x)

!!xconvertit la valeur a en 1si ce n'est pas le cas 0et la laisse à 0si elle l'est.
J'utilise beaucoup ce genre de chose dans l'obfuscation C.

Remarque: c'est C, je ne sais pas si cela fonctionne en C #

Une nuit normale
la source
4
Je ne sais pas pourquoi cela a été voté. Même une tentative superficielle de cela comme uint n = 1; if (n == !!n) { }donne Operator '!' cannot be applied to operand of type 'uint'sur le !nen C #. Ce n'est pas parce que quelque chose fonctionne en C que cela fonctionne en C #; #include <stdio.h>ne fonctionne même pas en C #, car C # n'a pas la directive de préprocesseur "include". Les langages sont plus différents que le C et le C ++.
un CVn le
2
Oh. D'accord. Je suis désolé :(
Une nuit normale
@OneNormalNight (x == !! x) Comment cela fonctionnera. Considérez que mon entrée est 5. (5 == !! 5). Cela donnera un résultat vrai
VINOTH ENERGETIC
1
@VinothKumar !! 5 évalue à 1. (5 == !! 5) évalue (5 == 1) qui évalue à faux.
Une nuit normale le
@OneNormalNight ouais je l'ai maintenant. ! (5) donne 1 à nouveau appliqué il donne 0. Pas 1.
VINOTH ENERGETIC
-3

J'ai donc créé un Listde ces nombres entiers spéciaux et vérifié si cela s'y Nrapporte.

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);
}

Vous pouvez également utiliser une méthode d'extension à des fins différentes où elle Containsn'est appelée qu'une seule fois (par exemple lorsque votre application démarre et charge des données). Cela fournit un style plus clair et clarifie la relation principale avec votre valeur ( 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);
    }
}

Appliquez-le:

N.PertainsTo(ints)

Ce n'est peut-être pas le moyen le plus rapide de le faire, mais pour moi, cela semble être un meilleur style.

KnorxThieus
la source