Ist es möglich, (x == 0 || x == 1) in einer einzigen Operation zu vereinfachen?

106

Also habe ich versucht, die n- te Zahl in der Fibonacci-Folge so kompakt wie möglich zu schreiben :

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

Aber ich frage mich, ob ich dies durch Ändern noch kompakter und effizienter machen kann

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

in einen einzigen Vergleich. Gibt es eine ausgefallene Bitverschiebungsoperation, die dies kann?

user6048670
quelle
111
Warum? Es ist lesbar, die Absicht ist sehr klar und es ist nicht teuer. Warum sollte es in einen "cleveren" Bitmusterabgleich geändert werden, der schwerer zu verstehen ist und die Absicht nicht eindeutig identifiziert?
D Stanley
9
Das ist nicht wirklich Fibonaci, oder?
n8wrl
9
fibonaci addiert die beiden vorherigen Werte. Meinten Sie fibn(N-1) + fibn(N-2) statt N * fibn(N-1)?
Juharr
46
Ich bin alles dafür, Nanosekunden zu sparen, aber wenn Sie einen einfachen Vergleich mit einer Methode haben, die Rekursion verwendet, warum sollten Sie sich dann um die Effizienz des Vergleichs bemühen und die Rekursion dort belassen?
Jon Hanna
25
Sie verwenden eine rekursive Methode zur Berechnung der Fabonacci-Zahl und möchten dann die Leistung verbessern? Warum nicht in eine Schleife verwandeln? oder schnelle Energie verbrauchen?
notbad

Antworten:

-9

Dieser funktioniert auch

Math.Sqrt(N) == N 

Die Quadratwurzel von 0 und 1 gibt 0 bzw. 1 zurück.

Rahul
quelle
20
Math.Sqrtist eine komplizierte Gleitkommafunktion. Es läuft langsam im Vergleich zu den Nur-Ganzzahl-Alternativen !!
Nayuki
1
Das sieht sauber aus, aber es gibt bessere Möglichkeiten, wenn Sie die anderen Antworten überprüfen.
Mafii
9
Wenn ich in einem Code, an dem ich arbeitete, darauf stoßen würde, würde ich wahrscheinlich zumindest zum Schreibtisch dieser Person gehen und sie gezielt fragen, welche Substanz sie zu der Zeit konsumierten.
Ein Lebenslauf
Wer hat dies bei klarem Verstand als Antwort markiert? Sprachlos.
squashed.bugaboo
212

Es gibt verschiedene Möglichkeiten, Ihren arithmetischen Test mit bitweiser Arithmetik zu implementieren. Dein Ausdruck:

  • x == 0 || x == 1

ist logisch äquivalent zu jedem dieser:

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

Bonus:

  • x * x == x (Der Beweis erfordert ein wenig Mühe)

In der Praxis sind diese Formen jedoch am besten lesbar, und der winzige Leistungsunterschied ist es nicht wirklich wert, bitweise zu rechnen:

  • x == 0 || x == 1
  • x <= 1(weil xeine vorzeichenlose Ganzzahl ist)
  • x < 2(weil xeine vorzeichenlose Ganzzahl ist)
Nayuki
quelle
6
Vergiss nicht(x & ~1) == 0
Lee Daniel Crocker
71
Aber wetten Sie nicht darauf, dass einer von ihnen "effizienter" ist. gcc generiert tatsächlich weniger Code für x == 0 || x == 1als für (x & ~1) == 0oder (x | 1) == 1. Für das erste ist es klug genug, es als gleichwertig zu erkennen x <= 1und ein einfaches auszugeben cmpl; setbe. Die anderen verwirren es und lassen es schlechteren Code erzeugen.
Hobbs
13
x <= 1 oder x <2 ist einfacher.
Gnasher729
9
@ Kevin True für C ++, da dieser Standard wirklich sehr, sehr bemüht ist, das Schreiben von kompatiblem Code unmöglich zu machen. Zum Glück ist dies eine Frage zu C #;)
Voo
5
Die meisten modernen Compiler können solche Vergleiche bereits optimieren, obwohl ich nicht weiß, wie intelligent C # -Compiler und .NET JITter sind. Im realen Code wird nur ein einziger Vergleich benötigt
phuclv
78

Da das Argument uint( ohne Vorzeichen ) ist, können Sie setzen

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

Weniger lesbar (IMHO), aber wenn Sie jeden Charakter zählen ( Code Golf oder ähnlich)

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

Bearbeiten : für Ihre bearbeitete Frage :

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

Oder

  return N < 2 ? 1 : fibn(N-1) + fibn(N-2);
Dmitry Bychenko
quelle
12
Wenn es Code Golf wäre, wäre es return N<2?1:f(N-1)+f(n-2). : P
Conor O'Brien
36

Sie können auch überprüfen, ob alle anderen Bits wie folgt 0 sind:

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

Der Vollständigkeit halber dank Matt die noch bessere Lösung:

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

In beiden Fällen müssen Sie sich um die Klammern kümmern, da bitweise Operatoren eine niedrigere Priorität als haben ==.

René Vogt
quelle
Ich mag das! Vielen Dank.
user6048670
15
1 weniger Charakter:(N|1)==1
Matt
1
@atk 3 | 1 ist 3, weil b0011 | b0001 b0011 ist
René Vogt
3
@atk Dies ist bitweise oder nicht logisch oder. Es gibt keinen Kurzschluss.
isaacg
2
@Hoten Richtig, aber Matt sagte 1 Zeichen weniger , nicht 1 Operation weniger .
Ivan Stoev
20

Wenn Sie die Funktion effizienter gestalten möchten, verwenden Sie eine Nachschlagetabelle. Die Nachschlagetabelle ist mit nur 47 Einträgen überraschend klein - der nächste Eintrag würde eine 32-Bit-Ganzzahl ohne Vorzeichen überlaufen. Es macht natürlich auch die Funktion trivial zu schreiben.

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

Sie können natürlich das Gleiche für Fakultäten tun.

Adam
quelle
14

Wie es mit Bitshift geht

Wenn Sie Bitshift verwenden und den Code etwas dunkel (aber kurz) machen möchten, können Sie Folgendes tun:

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

Bei einer vorzeichenlosen Ganzzahl Nin der Sprache c N>>1wird das Bit niedriger Ordnung weggeworfen. Wenn dieses Ergebnis ungleich Null ist, bedeutet dies, dass N größer als 1 ist.

Hinweis: Dieser Algorithmus ist schrecklich ineffizient, da er Werte in der bereits berechneten Sequenz unnötig neu berechnet.

Etwas viel schneller

Berechnen Sie es in einem Durchgang, anstatt implizit einen Fibonaci (N) -großen Baum zu bauen:

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

Wie einige Leute bereits erwähnt haben, dauert es nicht lange, bis eine 64-Bit-Ganzzahl ohne Vorzeichen überläuft. Je nachdem, wie groß Sie werden möchten, müssen Sie Ganzzahlen mit beliebiger Genauigkeit verwenden.

Matthew Gunn
quelle
1
Vermeiden Sie nicht nur den exponentiell wachsenden Baum, sondern auch die mögliche Verzweigung des ternären Operators, die moderne CPU-Pipelines verstopfen könnte.
Mathreadler
2
Ihr "viel schnellerer" Code funktioniert in C # nicht, da er uintnicht implizit in C # umgewandelt werden boolkann und die Frage speziell als C # gekennzeichnet ist.
Pharap
1
@pharap dann --N != 0stattdessen tun . Der Punkt ist, dass etwas O (n) O (fibn (n)) vorzuziehen ist.
Matthew Gunn
1
Um @ MatthewGunns Punkt zu erweitern, ist O (fib (n)) O (phi ^ n) (siehe diese Ableitung stackoverflow.com/a/360773/2788187 )
Connor Clark
@ RenéVogt Ich bin kein aktiver Entwickler. Ich habe hauptsächlich versucht, die völlige Absurdität eines O (fibn (N)) - Algorithmus zu kommentieren. Kompiliert es jetzt? (Ich habe hinzugefügt! = 0, da c # Ergebnisse ungleich Null nicht als wahr behandelt.) Es funktioniert (und hat funktioniert) in geradem c, wenn Sie uint durch einen Standard wie uint64_t ersetzen.
Matthew Gunn
10

Wenn Sie eine Uint verwenden, die nicht negativ werden kann, können Sie überprüfen, ob n < 2

BEARBEITEN

Oder für diesen speziellen Funktionsfall können Sie ihn wie folgt schreiben:

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

Dies führt natürlich zum gleichen Ergebnis auf Kosten eines zusätzlichen Rekursionsschritts.

Derpirscher
quelle
4
@CatthalMF: aber das Ergebnis ist das gleiche, weil1 * fibn(0) = 1 * 1 = 1
derpirscher
3
Berechnet Ihre Funktion nicht Fakultät, nicht Fibonacci?
Barmar
2
@Barmar ja, in der Tat ist das faktoriell, denn das war die ursprüngliche Frage
derpirscher
3
fibn
Könnte es
1
@ pie3636 Ich nannte es Fibn, weil es so in der ursprünglichen Frage genannt wurde und ich die Antwort später nicht aktualisiert habe
derpirscher
6

Überprüfen Sie einfach, ob N<= 1 ist, da Sie wissen, dass N ohne Vorzeichen ist. Es kann nur 2 Bedingungen geben, N <= 1die zu folgenden Ergebnissen führen TRUE: 0 und 1

public uint fibn ( uint N ) 
{
   return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}
James
quelle
Ist es überhaupt wichtig, ob es signiert oder nicht signiert ist? Der Algorithmus erzeugt eine unendliche Rekursion mit negativen Eingaben, so dass es nicht schadet, sie gleich 0 oder 1 zu behandeln.
Barmar
@Barmar sicher, dass es wichtig ist, besonders in diesem speziellen Fall. Das OP fragte, ob er genau vereinfachen könne (N == 0 || N == 1). Sie wissen, dass es nicht kleiner als 0 sein wird (denn dann würde es signiert sein!), Und das Maximum könnte 1 sein. N <= 1Vereinfacht es. Ich denke, der nicht signierte Typ ist nicht garantiert, aber das sollte woanders gehandhabt werden, würde ich sagen.
James
Mein Punkt ist, dass wenn es deklariert würde int Nund Sie den ursprünglichen Zustand beibehalten würden, es unendlich wiederkehren würde, wenn N mit seinem ursprünglichen Zustand negativ ist. Da dies ein undefiniertes Verhalten ist, müssen wir uns darüber keine Sorgen machen. Wir können also davon ausgehen, dass N unabhängig von der Deklaration nicht negativ ist.
Barmar
Oder wir können mit negativen Eingaben alles tun, was wir wollen, einschließlich der Behandlung als Basisfall der Rekursion.
Barmar
@Barmar ziemlich sicher, dass uint immer in unsigned konvertiert wird, wenn Sie versuchen, auf negativ zu setzen
James
6

Haftungsausschluss: Ich kenne C # nicht und habe diesen Code nicht getestet:

Aber ich frage mich, ob ich dies noch kompakter und effizienter machen kann, indem ich [...] in einen einzigen Vergleich umwandle ...

Keine Notwendigkeit für Bit-Shifting oder ähnliches, dies verwendet nur einen Vergleich und es sollte viel effizienter sein (O (n) gegen O (2 ^ n), denke ich?). Der Hauptteil der Funktion ist kompakter , endet jedoch mit der Deklaration etwas länger.

(Um Overhead von der Rekursion zu entfernen, gibt es die iterative Version, wie in Mathew Gunns Antwort )

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: Dies ist ein gängiges Funktionsmuster für die Iteration mit Akkumulatoren. Wenn Sie ersetzen N--mit N-1Sie keine Mutation effektiv verwenden, die sie verwendbar in einem reinen funktionalen Ansatz macht.

fede s.
quelle
4

Hier ist meine Lösung, es gibt nicht viel in der Optimierung dieser einfachen Funktion, andererseits biete ich hier Lesbarkeit als mathematische Definition der rekursiven Funktion an.

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

        case  1: return 1;

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

Die mathematische Definition der Fibonacci-Zahl in ähnlicher Weise.

Geben Sie hier die Bildbeschreibung ein

Nehmen Sie es weiter, um das Switch-Gehäuse zum Erstellen einer Nachschlagetabelle zu zwingen.

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
quelle
1
Der Vorteil Ihrer Lösung besteht darin, dass sie nur bei Bedarf berechnet wird. Am besten wäre eine Nachschlagetabelle. alternativer Bonus: f (n-1) = someCalcOf (f (n-2)), daher ist nicht die vollständige Wiederholung erforderlich.
Karsten
@Karsten Ich habe genügend Werte für den Switch hinzugefügt, um eine Nachschlagetabelle dafür zu erstellen. Ich bin mir nicht sicher, wie der alternative Bonus funktioniert.
Khaled.K
1
Wie beantwortet dies die Frage?
Clark Kent
@SaviourSelf Es kommt auf eine Nachschlagetabelle an, und in der Antwort wird der visuelle Aspekt erläutert. stackoverflow.com/a/395965/2128327
Khaled.K
Warum sollten Sie a verwenden, switchwenn Sie eine Reihe von Antworten haben können?
Nayuki
4

für N ist uint, benutze einfach

N <= 1
Yanghaogn
quelle
Genau das, was ich dachte; N ist uint! Dies sollte wirklich die Antwort sein.
squashed.bugaboo
1

Dmitrys Antwort ist am besten, aber wenn es sich um einen Int32-Rückgabetyp handelt und Sie einen größeren Satz von Ganzzahlen zur Auswahl haben, können Sie dies tun.

return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);
CathalMF
quelle
2
Wie ist das kürzer als das Original?
MCMastery
2
@MCMastery Es ist nicht kürzer. Wie ich bereits erwähnt habe, ist es nur besser, wenn der ursprüngliche Rückgabetyp ein int32 ist und er aus einer großen Anzahl gültiger Zahlen auswählt. Insead, schreiben zu müssen (N == -1 || N == 0 || N == 1 || N == 2)
CathalMF
1
Die Gründe von OP scheinen mit der Optimierung zu zusammenhängen. Dies ist aus mehreren Gründen eine schlechte Idee: 1) Das Instanziieren eines neuen Objekts in jedem rekursiven Aufruf ist eine wirklich schlechte Idee, 2) List.Containsist O (n), 3) einfach zwei Vergleiche durchzuführen ( N > -3 && N < 3) würde kürzeren und besser lesbaren Code ergeben.
Groo
@Groo Und was wäre, wenn die Werte -10, -2, 5, 7, 13
CathalMF
Es ist nicht das, was OP gefragt hat. Trotzdem möchten Sie immer noch 1) nicht bei jedem Aufruf eine neue Instanz erstellen, 2) stattdessen besser ein (einzelnes) Hashset verwenden, 3) für ein bestimmtes Problem, Sie könnten auch die Hash-Funktion optimieren Seien Sie rein oder verwenden Sie sogar geschickt angeordnete bitweise Operationen, wie in anderen Antworten vorgeschlagen.
Groo
0

Die Fibonacci-Sequenz ist eine Reihe von Zahlen, bei denen eine Zahl gefunden wird, indem die beiden Zahlen davor addiert werden. Es gibt zwei Arten von Ausgangspunkten: ( 0,1 , 1,2, ..) und ( 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
-----------------------------------------

Die Position Nbeginnt in diesem Fall ab 1, sie ist kein 0-basedArray-Index.

Mit der C # 6-Expression-Body-Funktion und Dmitrys Vorschlag zum ternären Operator können wir eine einzeilige Funktion mit korrekter Berechnung für den Typ 1 schreiben:

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

und für den Typ 2:

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

Etwas spät zur Party, aber du könntest es auch tun (x==!!x)

!!xkonvertiert den a-Wert in, 1wenn dies nicht der Fall ist 0, und belässt ihn bei, 0wenn dies der Fall ist.
Ich benutze diese Art von Dingen oft in der C-Verschleierung.

Hinweis: Dies ist C, nicht sicher, ob es in C # funktioniert

Eine normale Nacht
quelle
4
Ich bin mir nicht sicher, warum dies positiv bewertet wurde. Auch kursorisch dies als Versuch , uint n = 1; if (n == !!n) { }gibt Operator '!' cannot be applied to operand of type 'uint'auf den !n# in C. Nur weil etwas in C funktioniert, heißt das nicht, dass es in C # funktioniert. #include <stdio.h>funktioniert sogar nicht in C #, da C # nicht über die Präprozessor-Direktive "include" verfügt. Die Sprachen sind unterschiedlicher als C und C ++.
Ein Lebenslauf
2
Oh. In Ordnung. Es tut mir leid :(
Eine normale Nacht
@OneNormalNight (x == !! x) Wie das funktioniert. Betrachten Sie meine Eingabe ist 5. (5 == !! 5). Es wird Ergebnis als wahr geben
VINOTH ENERGETIC
1
@VinothKumar !! 5 ergibt 1. (5 == !! 5) ergibt (5 == 1), was falsch ergibt.
Eine normale Nacht
@ OneNormalNight Ja, ich habe es jetzt. ! (5) gibt 1 erneut angewendet es gibt 0. Nicht 1.
VINOTH ENERGETIC
-3

Also habe ich eine Listdieser speziellen Ganzzahlen erstellt und geprüft, ob Nsie dazu gehört.

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

Sie können auch eine Erweiterungsmethode für verschiedene Zwecke verwenden, Containsdie nur einmal aufgerufen wird (z. B. wenn Ihre Anwendung gestartet wird und Daten lädt). Dies bietet einen klareren Stil und verdeutlicht die primäre Beziehung zu Ihrem Wert ( 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);
    }
}

Wende es an:

N.PertainsTo(ints)

Dies ist vielleicht nicht der schnellste Weg, aber für mich scheint es ein besserer Stil zu sein.

KnorxThieus
quelle