Можно ли упростить (x == 0 || x == 1) в одну операцию?

106

Поэтому я пытался записать n- е число в последовательности Фибоначчи как можно более компактной функцией:

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

Но мне интересно, смогу ли я сделать это еще более компактным и эффективным, изменив

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

в одно сравнение. Есть ли какая-нибудь необычная операция битового сдвига, которая может это сделать?

user6048670
источник
111
Зачем? Он читабелен, цель очень ясна, и это не дорого. Зачем менять его на какое-то «умное» сопоставление битовых шаблонов, которое труднее понять и не ясно определяет намерение?
D Stanley
9
Это не совсем фибоначи, верно?
n8wrl 01
9
fibonaci складывает два предыдущих значения. Вы имели в виду fibn(N-1) + fibn(N-2) вместо N * fibn(N-1)?
juharr 01
46
Я полностью за сокращение наносекунд, но если у вас есть простое сравнение в методе, использующем рекурсию, зачем тратить усилия на эффективность сравнения и оставлять рекурсию на месте?
Джон Ханна
25
Вы используете рекурсивный способ вычисления числа Фабоначчи, а затем хотите повысить производительность? Почему бы не превратить его в цикл? или использовать быструю мощность?
notbad 01

Ответы:

-9

Этот тоже работает

Math.Sqrt(N) == N 

квадратный корень из 0 и 1 вернет 0 и 1 соответственно.

Рахул
источник
20
Math.Sqrt- сложная функция с плавающей запятой. Он работает медленно по сравнению с альтернативами только для целых чисел !!
Наюки
1
Это выглядит чистым, но есть способы получше, если вы проверите другие ответы.
Mafii
9
Если бы я натолкнулся на это в любом коде, над которым я работал, я бы, вероятно, как минимум подошел бы к столу этого человека и многозначительно спросил бы его, какое вещество он употреблял в то время.
CVn
Кто в здравом уме отметил, что это ответ? Безмолвный.
squashed.bugaboo
212

Есть несколько способов реализовать арифметический тест с использованием побитовой арифметики. Ваше выражение:

  • 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это целое число без знака)
Наюки
источник
6
Не забывайте(x & ~1) == 0
Ли Дэниэл Крокер
71
Но не делайте ставки на то, что какой-то конкретный из них будет «более эффективным». gcc на самом деле генерирует меньше кода, x == 0 || x == 1чем для (x & ~1) == 0или (x | 1) == 1. Для первого достаточно умен, чтобы распознать его как эквивалент x <= 1и вывести простой cmpl; setbe. Другие путают его и заставляют генерировать худший код.
hobbs
13
x <= 1 или x <2 проще.
gnasher729 02
9
@Kevin Верно для C ++, потому что этот стандарт очень, очень старается сделать невозможным написание совместимого кода. К счастью, это вопрос о C #;)
Voo
5
Большинство современных компиляторов уже могут оптимизировать подобные сравнения, хотя я не знаю, насколько умны компилятор C # и .NET JITter. В реальном коде нужно только одно сравнение
phuclv
78

Поскольку аргумент uint( без знака ), вы можете положить

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

Менее читабельно (IMHO), но если посчитать каждый символ ( Code Golf или ему подобные)

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

Изменить : для вашего отредактированного вопроса :

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

Или

  return N < 2 ? 1 : fibn(N-1) + fibn(N-2);
Дмитрий Быченко
источник
12
Если бы это был Code Golf, так и было бы return N<2?1:f(N-1)+f(n-2). : P
Конор О'Брайен
36

Вы также можете проверить, что все остальные биты равны 0, например:

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

Для полноты картины спасибо Мэтту за еще лучшее решение:

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

В обоих случаях вам нужно позаботиться о скобках, потому что побитовые операторы имеют более низкий приоритет, чем ==.

Рене Фогт
источник
Мне это нравится! Спасибо.
user6048670 01
15
На 1 персонаж меньше:(N|1)==1
Мэтт
1
@atk 3 | 1 равно 3, потому что b0011 | b0001 - это b0011
Рене Фогт,
3
@atk Это побитовое или, не логическое или. Короткого замыкания нет.
isaacg 01
2
@Hoten Верно, но Мэтт сказал, что на 1 символ меньше , а не на 1 операцию .
Иван Стоев
20

Если вы хотите сделать функцию более эффективной, используйте таблицу поиска. Таблица поиска на удивление мала, всего 47 записей - следующая запись будет переполнять 32-битное целое число без знака. Это также, конечно, упрощает написание функции.

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

Очевидно, вы можете сделать то же самое с факториалами.

Адам
источник
14

Как это сделать с битшифтом

Если вы хотите использовать битовый сдвиг и сделать код несколько непонятным (но коротким), вы можете сделать:

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

Для целого числа без знака Nна языке c,N>>1 отбрасывает младший бит. Если этот результат отличен от нуля, это означает, что N больше 1.

Примечание: этот алгоритм ужасно неэффективен, поскольку он без нужды пересчитывает значения в последовательности, которые уже были вычислены.

Что-то ПУТЬ быстрее

Вычислите его за один проход, вместо того, чтобы неявно строить дерево размером с Фибоначи (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;
}

Как отмечали некоторые люди, переполнение даже 64-битного целого числа без знака не займет много времени. В зависимости от того, насколько большим вы пытаетесь достичь, вам нужно будет использовать целые числа произвольной точности.

Мэтью Ганн
источник
1
Вы не только избегаете экспоненциально растущего дерева, но также избегаете потенциального разветвления тернарного оператора, который может засорить современные конвейеры ЦП.
mathreadler 02
2
Ваш «намного более быстрый» код не будет работать на C #, потому что uintон не может быть неявно приведен к bool, и вопрос специально помечен как C #.
Pharap
1
@pharap, тогда сделайте это --N != 0. Дело в том, что что-то O (n) предпочтительнее O (fibn (n)).
Мэтью Ганн
1
чтобы расширить точку @ MatthewGunn, O (fib (n)) is O (phi ^ n) (см. этот вывод stackoverflow.com/a/360773/2788187 )
Коннор Кларк
@ RenéVogt Я не разработчик C #. В основном я пытался прокомментировать полную абсурдность алгоритма O (fibn (N)). Сейчас он компилируется? (Я добавил! = 0, поскольку C # не обрабатывает ненулевые результаты как истинные.) Он работает (и работает) в прямом c, если вы замените uint чем-то стандартным, например uint64_t.
Мэтью Ганн
10

Поскольку вы используете uint, который не может быть отрицательным, вы можете проверить, n < 2

РЕДАКТИРОВАТЬ

Или для этого случая специальной функции вы можете написать это следующим образом:

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

что приведет к тому же результату, конечно, за счет дополнительного шага рекурсии.

дерпиршер
источник
4
@CatthalMF: но результат тот же, потому что1 * fibn(0) = 1 * 1 = 1
derpirscher 01
3
Разве ваша функция не вычисляет факториал, а не фибоначчи?
Barmar 05
2
@Barmar да, это действительно факториал, потому что это был исходный вопрос,
derpirscher
3
fibnТогда будет лучше не называть это
pie3636
1
@ pie3636, я назвал это фибн, потому что так он назывался в исходном вопросе, и я не обновлял ответ позже
derpirscher
6

Просто проверьте, не Nравно ли <= 1, поскольку вы знаете, что N без знака, может быть только 2 условия, N <= 1которые приводят к TRUE: 0 и 1

public uint fibn ( uint N ) 
{
   return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}
Джеймс
источник
Имеет ли значение, подписан он или нет? Алгоритм производит бесконечную рекурсию с отрицательными входными данными, поэтому нет ничего плохого в том, чтобы рассматривать их как эквивалент 0 или 1.
Бармар
@Barmar уверен, что это важно, особенно в данном конкретном случае. ОП спросил, может ли он точно упростить (N == 0 || N == 1). Вы знаете, что он не будет меньше 0 (потому что тогда он будет подписан!), А максимальное значение может быть 1. N <= 1упрощает это. Я предполагаю, что тип без знака не гарантируется, но я бы сказал, что это должно быть обработано в другом месте.
Джеймс
Я int Nхочу сказать, что если бы он был объявлен , и вы сохранили исходное состояние, оно будет повторяться бесконечно, когда N отрицательно с его исходным условием. Поскольку это неопределенное поведение, нам не о чем беспокоиться. Таким образом, мы можем предположить, что N неотрицательно, независимо от объявления.
Бармар
Или мы можем делать все, что захотим, с отрицательными входными данными, в том числе рассматривать их как базовый случай рекурсии.
Бармар
@Barmar уверен, что uint всегда будет преобразован в неподписанный, если вы попытаетесь установить отрицательное значение
Джеймс
6

Отказ от ответственности: я не знаю C # и не тестировал этот код:

Но мне интересно, смогу ли я сделать это еще более компактным и эффективным, преобразовав [...] в одно сравнение ...

Нет необходимости в сдвиге битов или тому подобном, здесь используется только одно сравнение, и оно должно быть намного более эффективным (O (n) vs O (2 ^ n), я думаю?). Тело функции более компактное , хотя заканчивается объявлением немного длиннее.

(Чтобы удалить накладные расходы из рекурсии, есть итеративная версия, как в ответе Мэтью Ганна )

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: Это общий функциональный шаблон для итераций с аккумуляторами. Если вы замените N--на, N-1вы фактически не используете мутацию, что делает его пригодным для использования в чисто функциональном подходе.

федерация с.
источник
4

Вот мое решение, в оптимизации этой простой функции не так много, с другой стороны, я предлагаю здесь удобочитаемость как математическое определение рекурсивной функции.

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

        case  1: return 1;

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

Математическое определение числа Фибоначчи аналогично.

введите описание изображения здесь

Продолжая, чтобы заставить коммутатор создать таблицу поиска.

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);
    }
}
Халед К.
источник
1
Преимущество вашего решения в том, что оно рассчитывается только при необходимости. Лучше всего будет справочная таблица. альтернативный бонус: f (n-1) = someCalcOf (f (n-2)), поэтому не требуется полный повторный запуск.
Карстен
@Karsten Я добавил достаточно значений для переключателя, чтобы создать для него таблицу поиска. Я не уверен, как работает альтернативный бонус.
Khaled.K
1
Как это отвечает на вопрос?
Кларк Кент,
@SaviourSelf сводится к поисковой таблице, и в ответе есть объяснение визуального аспекта. stackoverflow.com/a/395965/2128327
Khaled.K 06
Зачем использовать, switchесли можно получить множество ответов?
Наюки
4

для N - uint, просто используйте

N <= 1
Янхаогн
источник
В точности то, о чем я думал; N uint! На самом деле это должен быть ответ.
squashed.bugaboo
1

Ответ Дмитрия лучше всего, но если бы это был тип возвращаемого значения Int32 и у вас был бы больший набор целых чисел на выбор, вы могли бы это сделать.

return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);
КаталМФ
источник
2
Как это короче оригинала?
MCMaster 01
2
@MCMaster Не короче. Как я уже упоминал, лучше, если исходный тип возвращаемого значения - int32, и он выбирает из большого набора действительных чисел. Вместо необходимости писать (N == -1 || N == 0 || N == 1 || N == 2)
CathalMF 02
1
Причины OP, похоже, связаны с оптимизацией. Это плохая идея по нескольким причинам: 1) создание экземпляра нового объекта внутри каждого рекурсивного вызова - действительно плохая идея, 2) List.ContainsO (n), 3) простое выполнение двух сравнений вместо этого ( N > -3 && N < 3) даст более короткий и читаемый код.
Groo
@Groo А что, если бы значения были -10, -2, 5, 7, 13
CathalMF
Это не то, о чем спрашивал ОП. Но в любом случае вы по-прежнему 1) не хотите создавать новый экземпляр при каждом вызове, 2) вместо этого лучше использовать (один) хэш-набор, 3) для конкретной проблемы, вы также сможете оптимизировать хеш-функцию для быть чистым или даже использовать грамотно организованные побитовые операции, как это предлагается в других ответах.
Groo
0

Последовательность Фибоначчи - это последовательность чисел, в которой число находится путем сложения двух чисел перед ним. Есть два типа начальных точек: ( 0,1 , 1,2, ..) и ( 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
-----------------------------------------

Позиция Nв этом случае начинается с 1, это не0-based как индекс массива.

С помощью C # 6 Expression-body и предложение Дмитрия о тернарном операторе, мы можем написать однострочную функцию с правильным вычислением для типа 1:

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

а для типа 2:

public uint fibn(uint N) => N<3? 1: fibn(N-1)+fibn(N-2);
Artru
источник
-2

Немного поздно на вечеринку, но ты тоже можешь (x==!!x)

!!xпреобразует значение в, 1если это не так 0, и оставляет его равным, 0если это так.
Я часто использую подобные вещи в обфускации C.

Примечание: это C, не уверен, что он работает на C #.

Одна нормальная ночь
источник
4
Не уверен, почему за это проголосовали. Даже беглый пытается это как uint n = 1; if (n == !!n) { }дает Operator '!' cannot be applied to operand of type 'uint'на !nC #. То, что что-то работает в C, не означает, что это работает в C #; Даже #include <stdio.h>не работает в C #, потому что в C # нет директивы препроцессора include. Языки более разные, чем C и C ++.
CVn
2
Ой. Ладно. Извините :(
One Normal Night
@OneNormalNight (x == !! x) Как это будет работать. Считайте, что я ввел 5. (5 == !! 5). Результат будет истинным
VINOTH ENERGETIC 02
1
@VinothKumar !! 5 оценивается как 1. (5 == !! 5) оценивает (5 == 1), которое оценивается как ложное.
One Normal Night
@OneNormalNight да, теперь я понял. ! (5) дает 1 снова применяется, это дает 0. Не 1.
VINOTH ENERGETIC 03
-3

Итак, я создал одно Listиз этих специальных целых чисел и проверил, Nотносится ли оно к нему.

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

Вы также можете использовать метод расширения для разных целей, когда он Containsвызывается только один раз (например, когда ваше приложение запускается и загружает данные). Это обеспечивает более ясный стиль и проясняет первичное отношение к вашему значению ( 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);
    }
}

Примените это:

N.PertainsTo(ints)

Возможно, это не самый быстрый способ сделать это, но мне кажется, что это лучший стиль.

KnorxThieus
источник