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ć?
c#
algorithm
optimization
arithmetic-expressions
user6048670
źródło
źródło
fibn(N-1) + fibn(N-2)
zamiastN * fibn(N-1)
?Odpowiedzi:
Ten też działa
pierwiastek kwadratowy z 0 i 1 zwróci odpowiednio 0 i 1.
źródło
Math.Sqrt
jest skomplikowaną funkcją zmiennoprzecinkową. Działa wolno w porównaniu z alternatywami opartymi tylko na liczbach całkowitych !!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żx
jest liczbą całkowitą bez znaku)x < 2
(ponieważx
jest liczbą całkowitą bez znaku)źródło
(x & ~1) == 0
x == 0 || x == 1
niż dla(x & ~1) == 0
lub(x | 1) == 1
. W przypadku pierwszego z nich jest wystarczająco inteligentny, aby rozpoznać go jako równoważnyx <= 1
i wyprowadzić prostycmpl; setbe
. Inni mylą go i sprawiają, że generuje gorszy kod.Ponieważ argument jest
uint
( bez znaku ), możesz wstawićMniej czytelne (IMHO), ale jeśli policzysz każdy znak ( Code Golf lub podobne)
Edytuj : dla edytowanego pytania :
Lub
źródło
return N<2?1:f(N-1)+f(n-2)
. : PMożesz również sprawdzić, czy wszystkie inne bity mają wartość 0 w ten sposób:
Dla kompletności dzięki Mattowi jeszcze lepsze rozwiązanie:
W obu przypadkach należy zadbać o nawiasy, ponieważ operatory bitowe mają niższy priorytet niż
==
.źródło
(N|1)==1
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.
Oczywiście możesz zrobić to samo dla silni.
źródło
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ć:
Dla liczby całkowitej bez znaku
N
w 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):
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.
źródło
uint
nie jest niejawnie rzutowany nabool
, a pytanie jest specjalnie oznaczone jako C #.--N != 0
zamiast tego. Chodzi o to, że coś O (n) jest lepsze niż O (fibn (n)).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:
co doprowadzi do tego samego wyniku, oczywiście kosztem dodatkowego kroku rekurencji.
źródło
1 * fibn(0) = 1 * 1 = 1
fibn
wtedy tego nie nazywaćPo prostu sprawdź, czy
N
wynosi <= 1, ponieważ wiesz, że N jest bez znaku, mogą istnieć tylko 2 warunki,N <= 1
które skutkująTRUE
: 0 i 1źródło
(N == 0 || N == 1)
. Wiesz, że nie będzie mniej niż 0 (bo wtedy byłby podpisany!), A maksimum może wynosić 1.N <= 1
upraszcza to. Wydaje mi się, że typ bez znaku nie jest gwarantowany, ale powiedziałbym, że powinno się to zająć gdzie indziej.int N
i 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.Zastrzeżenie: nie znam języka C # i nie testowałem tego kodu:
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 )
PS: Jest to typowy wzorzec funkcjonalny dla iteracji z akumulatorami. Jeśli zastąpisz
N--
jeN-1
, skutecznie nie używasz mutacji, co czyni ją użyteczną w czysto funkcjonalnym podejściu.źródło
Oto moje rozwiązanie, nie ma wiele w optymalizacji tej prostej funkcji, z drugiej strony oferuję tutaj czytelność jako matematyczną definicję funkcji rekurencyjnej.
Matematyczna definicja liczby Fibonacciego w podobny sposób.
Pójście dalej, aby zmusić obudowę przełącznika do zbudowania tabeli przeglądowej.
źródło
switch
kiedy możesz mieć szereg odpowiedzi?dla N jest uint, po prostu użyj
źródło
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ć.
źródło
List.Contains
to O (n), 3) po prostu wykonanie dwóch porównań zamiast tego (N > -3 && N < 3
) dałoby krótszy i bardziej czytelny kod.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).
Pozycja
N
w tym przypadku zaczyna się od1
, nie jest0-based
indeksem 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:
a dla typu 2:
źródło
Trochę za późno na imprezę, ale możesz też to zrobić
(x==!!x)
!!x
konwertuje wartość a na,1
jeśli tak nie jest0
, i pozostawia ją,0
jeś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 #
źródło
uint n = 1; if (n == !!n) { }
dajeOperator '!' cannot be applied to operand of type 'uint'
w!n
ję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 ++.Utworzyłem więc jedną
List
z tych specjalnych liczb całkowitych i sprawdziłem, czyN
to dotyczy.Możesz również użyć metody rozszerzającej do różnych celów, gdy
Contains
jest 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
):Zastosuj to:
Może nie jest to najszybszy sposób, ale wydaje mi się, że jest to lepszy styl.
źródło