Czy można uprościć (x == 0 || x == 1) do jednej operacji?

106

Próbowałem więc zapisać n- tą liczbę w ciągu Fibonacciego w możliwie zwartej funkcji:

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

Ale zastanawiam się, czy mogę uczynić to jeszcze bardziej kompaktowym i wydajnym, zmieniając

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

w jednym porównaniu. Czy jest jakaś fantazyjna operacja przesunięcia bitu, która może to zrobić?

user6048670
źródło
111
Czemu? Jest czytelny, cel jest bardzo jasny i nie jest drogi. Po co zmieniać to na jakieś „sprytne” dopasowanie wzorca bitowego, które jest trudniejsze do zrozumienia i nie określa jasno celu?
D Stanley
9
To nie jest tak naprawdę fibonaci, prawda?
n8wrl
9
fibonaci dodaje dwie poprzednie wartości. Czy miałeś na myśli fibn(N-1) + fibn(N-2) zamiast N * fibn(N-1)?
juharr
46
Jestem zwolennikiem skrócenia nanosekund, ale jeśli masz proste porównanie w metodzie wykorzystującej rekurencję, po co poświęcać wysiłek na efektywność porównania i zostawiać tam rekursję?
Jon Hanna
25
Korzystasz z rekurencyjnego sposobu obliczania liczby Fabonacciego, a następnie chcesz poprawić wydajność? Dlaczego nie zamienić go w pętlę? lub użyć szybkiej mocy?
notbad

Odpowiedzi:

-9

Ten też działa

Math.Sqrt(N) == N 

pierwiastek kwadratowy z 0 i 1 zwróci odpowiednio 0 i 1.

Rahul
źródło
20
Math.Sqrtjest skomplikowaną funkcją zmiennoprzecinkową. Działa wolno w porównaniu z alternatywami opartymi tylko na liczbach całkowitych !!
Nayuki
1
Wygląda to porządnie, ale są lepsze sposoby niż te, jeśli sprawdzisz inne odpowiedzi.
Mafii,
9
Gdybym natrafił na to w jakimkolwiek kodzie, nad którym pracowałem, prawdopodobnie podszedłbym przynajmniej do biurka tej osoby i wyraźnie zapytał, jaką substancję w tym czasie konsumowała.
CVn
Kto przy zdrowych zmysłach oznaczył to jako odpowiedź? Oniemiały.
squashed.bugaboo
212

Istnieje wiele sposobów implementacji testu arytmetycznego przy użyciu arytmetyki bitowej. Twoje wyrażenie:

  • x == 0 || x == 1

jest logicznie równoważne każdemu z poniższych:

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

Premia:

  • x * x == x (dowód wymaga trochę wysiłku)

Ale praktycznie rzecz biorąc, te formularze są najbardziej czytelne, a niewielka różnica w wydajności nie jest naprawdę warta stosowania arytmetyki bitowej:

  • x == 0 || x == 1
  • x <= 1(ponieważ xjest liczbą całkowitą bez znaku)
  • x < 2(ponieważ xjest liczbą całkowitą bez znaku)
Nayuki
źródło
6
Nie zapomnij(x & ~1) == 0
Lee Daniel Crocker
71
Ale nie licz na to, że któryś z nich będzie „bardziej wydajny”. gcc faktycznie generuje mniej kodu dla x == 0 || x == 1niż dla (x & ~1) == 0lub (x | 1) == 1. W przypadku pierwszego z nich jest wystarczająco inteligentny, aby rozpoznać go jako równoważny x <= 1i wyprowadzić prosty cmpl; setbe. Inni mylą go i sprawiają, że generuje gorszy kod.
hobbs
13
x <= 1 lub x <2 jest prostsze.
gnasher729
9
@Kevin True dla C ++, ponieważ ten standard bardzo, bardzo ciężko stara się uniemożliwić pisanie zgodnego kodu. Na szczęście jest to pytanie o C #;)
Voo
5
Większość współczesnych kompilatorów może już optymalizować takie porównania, chociaż nie wiem, jak inteligentny jest kompilator C # i .NET JITter. W prawdziwym kodzie potrzebne jest tylko jedno porównanie
phuclv
78

Ponieważ argument jest uint( bez znaku ), możesz wstawić

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

Mniej czytelne (IMHO), ale jeśli policzysz każdy znak ( Code Golf lub podobne)

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

Edytuj : dla edytowanego pytania :

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

Lub

  return N < 2 ? 1 : fibn(N-1) + fibn(N-2);
Dmitrij Bychenko
źródło
12
Gdyby to był Code Golf, byłby return N<2?1:f(N-1)+f(n-2). : P
Conor O'Brien
36

Możesz również sprawdzić, czy wszystkie inne bity mają wartość 0 w ten sposób:

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

Dla kompletności dzięki Mattowi jeszcze lepsze rozwiązanie:

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

W obu przypadkach należy zadbać o nawiasy, ponieważ operatory bitowe mają niższy priorytet niż ==.

René Vogt
źródło
Lubię to! Dzięki.
user6048670
15
1 znak mniej:(N|1)==1
Matt
1
@atk 3 | 1 to 3, ponieważ b0011 | b0001 to b0011
René Vogt
3
@atk To jest bitowe lub, nie logiczne lub. Nie ma zwarcia.
isaacg
2
@Hoten Dobrze, ale Matt powiedział, że o 1 znak mniej , a nie o 1 operację mniej .
Ivan Stoev
20

Jeśli chcesz zwiększyć wydajność funkcji, użyj tabeli przeglądowej. Tabela przeglądowa jest zaskakująco mała i zawiera tylko 47 wpisów - następny wpis spowodowałby przepełnienie 32-bitowej liczby całkowitej bez znaku. To oczywiście sprawia, że ​​napisanie tej funkcji jest banalne.

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

Oczywiście możesz zrobić to samo dla silni.

Adam
źródło
14

Jak to zrobić za pomocą Bitshift

Jeśli chcesz użyć przesunięcia bitów i sprawić, by kod był nieco niejasny (ale krótki), możesz zrobić:

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

Dla liczby całkowitej bez znaku Nw języku c,N>>1 odrzuca najmniej znaczący bit. Jeśli ten wynik jest różny od zera, oznacza to, że N jest większe niż 1.

Uwaga: ten algorytm jest strasznie nieefektywny, ponieważ niepotrzebnie przelicza wartości w sekwencji, które zostały już obliczone.

Coś WIĘCEJ szybciej

Oblicz to w jednym przejściu, zamiast pośrednio budować drzewo wielkości 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;
}

Jak wspominali niektórzy, przepełnienie nawet 64-bitowej liczby całkowitej bez znaku nie zajmuje dużo czasu. W zależności od tego, jak duży chcesz osiągnąć, musisz użyć liczb całkowitych o dowolnej dokładności.

Matthew Gunn
źródło
1
Nie tylko unikasz wykładniczego rosnącego drzewa, ale także unikasz potencjalnego rozgałęzienia operatora trójskładnikowego, które mogłoby zatykać nowoczesne potoki procesora.
mathreadler
2
Twój kod „o wiele szybszy” nie będzie działał w C #, ponieważ uintnie jest niejawnie rzutowany na bool, a pytanie jest specjalnie oznaczone jako C #.
Pharap
1
@pharap to zrób --N != 0zamiast tego. Chodzi o to, że coś O (n) jest lepsze niż O (fibn (n)).
Matthew Gunn
1
aby rozwinąć punkt @ MatthewGunn, O (fib (n)) to O (phi ^ n) (zobacz to wyprowadzenie stackoverflow.com/a/360773/2788187 )
Connor Clark
@ RenéVogt Nie jestem programistą ac #. Przede wszystkim starałem się skomentować całkowitą absurdalność algorytmu O (fibn (N)). Czy teraz się kompiluje? (Dodałem! = 0, ponieważ c # nie traktuje niezerowych wyników jako prawdy.) Działa (i działało) w prostym c, jeśli zamienisz uint na coś standardowego, takiego jak uint64_t.
Matthew Gunn,
10

Kiedy używasz uint, który nie może być ujemny, możesz sprawdzić, czy n < 2

EDYTOWAĆ

Lub dla tego specjalnego przypadku funkcji możesz napisać to w następujący sposób:

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

co doprowadzi do tego samego wyniku, oczywiście kosztem dodatkowego kroku rekurencji.

derpirscher
źródło
4
@CatthalMF: ale wynik jest taki sam, ponieważ1 * fibn(0) = 1 * 1 = 1
derpirscher
3
Czy twoja funkcja nie oblicza silni, a nie Fibonacciego?
Barmar
2
@Barmar Tak, rzeczywiście to silni, bo taki był pierwotny pytanie
derpirscher
3
Najlepiej byłoby fibnwtedy tego nie nazywać
pie3636
1
@ pie3636 Nazwałem to fibn, ponieważ tak zostało nazwane w pierwotnym pytaniu i nie zaktualizowałem odpowiedzi później
derpirscher
6

Po prostu sprawdź, czy Nwynosi <= 1, ponieważ wiesz, że N jest bez znaku, mogą istnieć tylko 2 warunki, N <= 1które skutkują TRUE: 0 i 1

public uint fibn ( uint N ) 
{
   return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}
James
źródło
Czy to w ogóle ma znaczenie, czy jest podpisane czy niepodpisane? Algorytm wytwarza nieskończoną rekursję z ujemnymi
danymi
@Barmar na pewno to ma znaczenie, szczególnie w tym konkretnym przypadku. OP zapytał, czy mógłby dokładnie uprościć (N == 0 || N == 1). Wiesz, że nie będzie mniej niż 0 (bo wtedy byłby podpisany!), A maksimum może wynosić 1. N <= 1upraszcza to. Wydaje mi się, że typ bez znaku nie jest gwarantowany, ale powiedziałbym, że powinno się to zająć gdzie indziej.
james
Chodzi mi o to, że gdyby został zadeklarowany int Ni zachowałbyś pierwotny stan, powtarzałby się w nieskończoność, gdy N jest ujemne przy jego pierwotnym stanie. Ponieważ jest to niezdefiniowane zachowanie, nie musimy się tym martwić. Możemy więc założyć, że N jest nieujemne, niezależnie od deklaracji.
Barmar
Lub możemy zrobić wszystko, co chcemy, z ujemnymi danymi wejściowymi, w tym traktować je jako podstawowy przypadek rekursji.
Barmar
@Barmar całkiem pewny, że uint zawsze zostanie przekonwertowany na bez znaku, jeśli spróbujesz ustawić wartość ujemną
james
6

Zastrzeżenie: nie znam języka C # i nie testowałem tego kodu:

Zastanawiam się jednak, czy mogę uczynić to jeszcze bardziej kompaktowym i wydajnym, zmieniając [...] w jedno porównanie ...

Nie ma potrzeby przesuwania bitów lub czegoś podobnego, to wykorzystuje tylko jedno porównanie i powinno być o wiele bardziej wydajne (myślę, że O (n) vs O (2 ^ n)?). Ciało funkcji jest bardziej zwarte , chociaż deklaracja kończy się nieco dłuższym opisem.

(Aby usunąć narzut z rekursji, istnieje wersja iteracyjna, jak w odpowiedzi Mathew Gunna )

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: Jest to typowy wzorzec funkcjonalny dla iteracji z akumulatorami. Jeśli zastąpisz N--je N-1, skutecznie nie używasz mutacji, co czyni ją użyteczną w czysto funkcjonalnym podejściu.

fede s.
źródło
4

Oto moje rozwiązanie, nie ma wiele w optymalizacji tej prostej funkcji, z drugiej strony oferuję tutaj czytelność jako matematyczną definicję funkcji rekurencyjnej.

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

        case  1: return 1;

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

Matematyczna definicja liczby Fibonacciego w podobny sposób.

wprowadź opis obrazu tutaj

Pójście dalej, aby zmusić obudowę przełącznika do zbudowania tabeli przeglądowej.

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
źródło
1
Zaletą twojego rozwiązania jest to, że jest obliczane tylko wtedy, gdy jest to potrzebne. Najlepsza byłaby tabela przeglądowa. premia alternatywna: f (n-1) = someCalcOf (f (n-2)), więc nie jest potrzebne całkowite powtórzenie.
Karsten
@Karsten Dodałem wystarczającą liczbę wartości dla przełącznika, aby utworzyć dla niego tabelę przeglądową. Nie jestem pewien, jak działa alternatywny bonus.
Khaled.K
1
Jak to odpowiada na pytanie?
Clark Kent
@SaviourSelf sprowadza się do tabeli przeglądowej, aw odpowiedzi wyjaśniono aspekt wizualny. stackoverflow.com/a/395965/2128327
Khaled.K
Dlaczego miałbyś używać, switchkiedy możesz mieć szereg odpowiedzi?
Nayuki
4

dla N jest uint, po prostu użyj

N <= 1
yanghaogn
źródło
Dokładnie to, o czym myślałem; N jest uint! To naprawdę powinna być odpowiedź.
squashed.bugaboo
1

Odpowiedź Dmitry'ego jest najlepsza, ale gdyby był to typ zwracany przez Int32 i miałbyś większy zestaw liczb całkowitych do wyboru, mógłbyś to zrobić.

return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);
CathalMF
źródło
2
Jak to jest krótsze niż oryginał?
MCMastery
2
@MCMastery Nie jest krótsze. Jak wspomniałem, lepiej jest tylko wtedy, gdy pierwotnym typem zwracanym jest int32 i wybiera z dużego zestawu prawidłowych liczb. Zamiast pisać (N == -1 || N == 0 || N == 1 || N == 2)
CathalMF
1
Wydaje się, że powody OP są związane z optymalizacją. Jest to zły pomysł z kilku powodów: 1) utworzenie instancji nowego obiektu w każdym wywołaniu rekurencyjnym jest naprawdę złym pomysłem, 2) List.Containsto O (n), 3) po prostu wykonanie dwóch porównań zamiast tego ( N > -3 && N < 3) dałoby krótszy i bardziej czytelny kod.
Groo
@Groo A co by było, gdyby wartości wynosiły -10, -2, 5, 7, 13
CathalMF
Nie o to pytał OP. Ale w każdym razie nadal 1) nie chciałbyś tworzyć nowej instancji w każdym wywołaniu, 2) lepiej zamiast tego używałbyś (pojedynczego) skrótu, 3) dla konkretnego problemu, mógłbyś również zoptymalizować funkcję skrótu, aby bądź czysty, a nawet używaj sprytnie zaaranżowanych operacji bitowych, jak sugerowano w innych odpowiedziach.
Groo
0

Ciąg Fibonacciego to ciąg liczb, w których liczba jest znajdowana poprzez zsumowanie dwóch liczb przed nią. Istnieją dwa rodzaje punktów początkowych: ( 0,1 , 1,2, ..) i ( 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
-----------------------------------------

Pozycja Nw tym przypadku zaczyna się od 1, nie jest 0-basedindeksem tablicy.

Korzystając z funkcji C # 6 Expression-body i sugestii Dmitry'ego na temat operatora trójskładnikowego, możemy napisać funkcję jednowierszową z poprawnymi obliczeniami dla typu 1:

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

a dla typu 2:

public uint fibn(uint N) => N<3? 1: fibn(N-1)+fibn(N-2);
Artru
źródło
-2

Trochę za późno na imprezę, ale możesz też to zrobić (x==!!x)

!!xkonwertuje wartość a na, 1jeśli tak nie jest 0, i pozostawia ją, 0jeśli tak nie jest.
Często używam tego rodzaju rzeczy w zaciemnianiu języka C.

Uwaga: to jest C, nie jestem pewien, czy działa w C #

Jedna normalna noc
źródło
4
Nie wiem, dlaczego głosowano za tym. Nawet pobieżne próbując to jak uint n = 1; if (n == !!n) { }daje Operator '!' cannot be applied to operand of type 'uint'w !njęzyku C #. To, że coś działa w C, nie oznacza, że ​​działa w C #; nawet #include <stdio.h>nie działa w C #, ponieważ C # nie ma dyrektywy preprocesora „include”. Języki są bardziej różne niż C i C ++.
CVn
2
O. W porządku. Przepraszam :(
One Normal Night
@OneNormalNight (x == !! x) Jak to będzie działać. Rozważ, że moje wejście to 5. (5 == !! 5). Wynik będzie prawdziwy
VINOTH ENERGETIC
1
@VinothKumar !! 5 zwraca wartość 1. (5 == !! 5) oblicza (5 == 1), co daje w wyniku fałsz.
Jedna normalna noc
@OneNormalNight yeah, mam to teraz. ! (5) daje 1 ponownie zastosowane daje 0. Nie 1.
VINOTH ENERGETIC
-3

Utworzyłem więc jedną Listz tych specjalnych liczb całkowitych i sprawdziłem, czy Nto dotyczy.

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

Możesz również użyć metody rozszerzającej do różnych celów, gdy Containsjest wywoływana tylko raz (np. Gdy aplikacja jest uruchamiana i ładuje dane). Zapewnia to jaśniejszy styl i wyjaśnia podstawowy związek z wartością ( 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);
    }
}

Zastosuj to:

N.PertainsTo(ints)

Może nie jest to najszybszy sposób, ale wydaje mi się, że jest to lepszy styl.

KnorxThieus
źródło