Поэтому я пытался записать n- е число в последовательности Фибоначчи как можно более компактной функцией:
public uint fibn ( uint N )
{
return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}
Но мне интересно, смогу ли я сделать это еще более компактным и эффективным, изменив
(N == 0 || N == 1)
в одно сравнение. Есть ли какая-нибудь необычная операция битового сдвига, которая может это сделать?
c#
algorithm
optimization
arithmetic-expressions
user6048670
источник
источник
fibn(N-1) + fibn(N-2)
вместоN * fibn(N-1)
?Ответы:
Этот тоже работает
квадратный корень из 0 и 1 вернет 0 и 1 соответственно.
источник
Math.Sqrt
- сложная функция с плавающей запятой. Он работает медленно по сравнению с альтернативами только для целых чисел !!Есть несколько способов реализовать арифметический тест с использованием побитовой арифметики. Ваше выражение:
x == 0 || x == 1
логически эквивалентен каждому из них:
(x & 1) == x
(x & ~1) == 0
(x | 1) == 1
(~x | 1) == (uint)-1
x >> 1 == 0
Бонус:
x * x == x
(доказательство требует немного усилий)Но с практической точки зрения эти формы наиболее читабельны, и небольшая разница в производительности на самом деле не стоит использования побитовой арифметики:
x == 0 || x == 1
x <= 1
(потому чтоx
это целое число без знака)x < 2
(потому чтоx
это целое число без знака)источник
(x & ~1) == 0
x == 0 || x == 1
чем для(x & ~1) == 0
или(x | 1) == 1
. Для первого достаточно умен, чтобы распознать его как эквивалентx <= 1
и вывести простойcmpl; setbe
. Другие путают его и заставляют генерировать худший код.Поскольку аргумент
uint
( без знака ), вы можете положитьМенее читабельно (IMHO), но если посчитать каждый символ ( Code Golf или ему подобные)
Изменить : для вашего отредактированного вопроса :
Или
источник
return N<2?1:f(N-1)+f(n-2)
. : PВы также можете проверить, что все остальные биты равны 0, например:
Для полноты картины спасибо Мэтту за еще лучшее решение:
В обоих случаях вам нужно позаботиться о скобках, потому что побитовые операторы имеют более низкий приоритет, чем
==
.источник
(N|1)==1
Если вы хотите сделать функцию более эффективной, используйте таблицу поиска. Таблица поиска на удивление мала, всего 47 записей - следующая запись будет переполнять 32-битное целое число без знака. Это также, конечно, упрощает написание функции.
Очевидно, вы можете сделать то же самое с факториалами.
источник
Как это сделать с битшифтом
Если вы хотите использовать битовый сдвиг и сделать код несколько непонятным (но коротким), вы можете сделать:
Для целого числа без знака
N
на языке c,N>>1
отбрасывает младший бит. Если этот результат отличен от нуля, это означает, что N больше 1.Примечание: этот алгоритм ужасно неэффективен, поскольку он без нужды пересчитывает значения в последовательности, которые уже были вычислены.
Что-то ПУТЬ быстрее
Вычислите его за один проход, вместо того, чтобы неявно строить дерево размером с Фибоначи (N):
Как отмечали некоторые люди, переполнение даже 64-битного целого числа без знака не займет много времени. В зависимости от того, насколько большим вы пытаетесь достичь, вам нужно будет использовать целые числа произвольной точности.
источник
uint
он не может быть неявно приведен кbool
, и вопрос специально помечен как C #.--N != 0
. Дело в том, что что-то O (n) предпочтительнее O (fibn (n)).Поскольку вы используете uint, который не может быть отрицательным, вы можете проверить,
n < 2
РЕДАКТИРОВАТЬ
Или для этого случая специальной функции вы можете написать это следующим образом:
что приведет к тому же результату, конечно, за счет дополнительного шага рекурсии.
источник
1 * fibn(0) = 1 * 1 = 1
fibn
Тогда будет лучше не называть этоПросто проверьте, не
N
равно ли <= 1, поскольку вы знаете, что N без знака, может быть только 2 условия,N <= 1
которые приводят кTRUE
: 0 и 1источник
(N == 0 || N == 1)
. Вы знаете, что он не будет меньше 0 (потому что тогда он будет подписан!), А максимальное значение может быть 1.N <= 1
упрощает это. Я предполагаю, что тип без знака не гарантируется, но я бы сказал, что это должно быть обработано в другом месте.int N
хочу сказать, что если бы он был объявлен , и вы сохранили исходное состояние, оно будет повторяться бесконечно, когда N отрицательно с его исходным условием. Поскольку это неопределенное поведение, нам не о чем беспокоиться. Таким образом, мы можем предположить, что N неотрицательно, независимо от объявления.Отказ от ответственности: я не знаю C # и не тестировал этот код:
Нет необходимости в сдвиге битов или тому подобном, здесь используется только одно сравнение, и оно должно быть намного более эффективным (O (n) vs O (2 ^ n), я думаю?). Тело функции более компактное , хотя заканчивается объявлением немного длиннее.
(Чтобы удалить накладные расходы из рекурсии, есть итеративная версия, как в ответе Мэтью Ганна )
PS: Это общий функциональный шаблон для итераций с аккумуляторами. Если вы замените
N--
на,N-1
вы фактически не используете мутацию, что делает его пригодным для использования в чисто функциональном подходе.источник
Вот мое решение, в оптимизации этой простой функции не так много, с другой стороны, я предлагаю здесь удобочитаемость как математическое определение рекурсивной функции.
Математическое определение числа Фибоначчи аналогично.
Продолжая, чтобы заставить коммутатор создать таблицу поиска.
источник
switch
если можно получить множество ответов?для N - uint, просто используйте
источник
Ответ Дмитрия лучше всего, но если бы это был тип возвращаемого значения Int32 и у вас был бы больший набор целых чисел на выбор, вы могли бы это сделать.
источник
List.Contains
O (n), 3) простое выполнение двух сравнений вместо этого (N > -3 && N < 3
) даст более короткий и читаемый код.Последовательность Фибоначчи - это последовательность чисел, в которой число находится путем сложения двух чисел перед ним. Есть два типа начальных точек: ( 0,1 , 1,2, ..) и ( 1,1 , 2,3).
Позиция
N
в этом случае начинается с1
, это не0-based
как индекс массива.С помощью C # 6 Expression-body и предложение Дмитрия о тернарном операторе, мы можем написать однострочную функцию с правильным вычислением для типа 1:
а для типа 2:
источник
Немного поздно на вечеринку, но ты тоже можешь
(x==!!x)
!!x
преобразует значение в,1
если это не так0
, и оставляет его равным,0
если это так.Я часто использую подобные вещи в обфускации C.
Примечание: это C, не уверен, что он работает на C #.
источник
uint n = 1; if (n == !!n) { }
даетOperator '!' cannot be applied to operand of type 'uint'
на!n
C #. То, что что-то работает в C, не означает, что это работает в C #; Даже#include <stdio.h>
не работает в C #, потому что в C # нет директивы препроцессора include. Языки более разные, чем C и C ++.Итак, я создал одно
List
из этих специальных целых чисел и проверил,N
относится ли оно к нему.Вы также можете использовать метод расширения для разных целей, когда он
Contains
вызывается только один раз (например, когда ваше приложение запускается и загружает данные). Это обеспечивает более ясный стиль и проясняет первичное отношение к вашему значению (N
):Примените это:
Возможно, это не самый быстрый способ сделать это, но мне кажется, что это лучший стиль.
источник