相关疑难解决方法(0)

所以我试图在Fibonacci序列中尽可能紧凑地写出第n个数:

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

但我想知道我是否可以通过改变来使其更加紧凑和高效

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

进入单一比较.是否有一些奇特的位移操作可以做到这一点？

我正在玩F#和C#,并希望从C#调用F#代码.

我设法让它在Visual Studio中以相反的方式工作,方法是在同一个解决方案中有两个项目,并在F#项目中添加C#代码的引用.这样做之后,我可以调用C#代码,甚至在调试时逐步执行它.

我想要做的是F#代码来自C#而不是来自F#的C#代码.我在C#项目中添加了对F#项目的引用,但它的工作方式与以前不同.我想知道如果不手动完成这是否可行.

我试图弄清楚C#编译器如何处理尾调用.

(答案:他们不是.但是64位JIT会做TCE(尾部呼叫消除).限制适用.)

所以我使用递归调用编写了一个小测试,它打印了在StackOverflowException杀死进程之前调用它的次数.

class Program
{
    static void Main(string[] args)
    {
        Rec();
    }

    static int sz = 0;
    static Random r = new Random();
    static void Rec()
    {
        sz++;

        //uncomment for faster, more imprecise runs
        //if (sz % 100 == 0)
        {
            //some code to keep this method from being inlined
            var zz = r.Next();  
            Console.Write("{0} Random: {1}\r", sz, zz);
        }

        //uncommenting this stops TCE from happening
        //else
        //{
        //    Console.Write("{0}\r", sz); …

出于好奇,我试图使用C#生成尾调用操作码.Fibinacci是一个简单的,所以我的c#示例如下所示:

    private static void Main(string[] args)
    {
        Console.WriteLine(Fib(int.MaxValue, 0));
    }

    public static int Fib(int i, int acc)
    {
        if (i == 0)
        {
            return acc;
        }

        return Fib(i - 1, acc + i);
    }

如果我在发布中构建并在没有调试的情况下运行它,我就不会出现堆栈溢出.在没有优化的情况下调试或运行它,我确实得到了堆栈溢出,这意味着尾部调用在发布时具有优化功能(这是我的预期).

这个MSIL看起来像这样:

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x205e
    // Code Size 17 (0x11)
    .maxstack 8
    L_0000: ldarg.0 
    L_0001: brtrue.s L_0005
    L_0003: ldarg.1 
    L_0004: ret 
    L_0005: ldarg.0 
    L_0006: ldc.i4.1 
    L_0007: sub 
    L_0008: ldarg.1 
    L_0009: ldarg.0 
    L_000a: …

我是F#的新手,正在阅读有关尾递归函数的内容,希望有人可以给我两个不同的函数foo实现 - 一个是尾递归的,另一个不是我可以更好地理解这个原理.

可能重复:
为什么.net/C#不会消除尾递归？

C#会做尾注吗？

我找不到任何文件告诉我它是否有.

可能重复:
为什么.net/C#不会消除尾递归？

请使用以下C#代码:

using System;

namespace TailTest
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Counter(0);
        }

        static void Counter(int i)
        {
            Console.WriteLine(i);
            if (i < int.MaxValue) Counter(++i);
        }
    }
}

C#编译器(无论如何)我会将Counter方法编译成以下CIL:

.method private static hidebysig default void Counter (int32 i) cil managed 
{
.maxstack 8
IL_0000:  ldarg.0 
IL_0001:  call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006:  ldarg.0 
IL_0007:  ldc.i4 2147483647
IL_000c:  bge IL_0019
IL_0011:  ldarg.0 
IL_0012:  ldc.i4.1 
IL_0013:  add 
IL_0014:  call void class TailTest.MainClass::Counter(int32)
IL_0019:  ret 
}

上面代码的问题是它会导致堆栈溢出(在我的硬件上约为i = …

在许多使用递归的函数式语言中被认为是一种很好的实践.我认为这很好,因为编译器优化了函数式语言的代码.

但是在创建算法时,在C#中使用递归是一种好习惯吗？就C#而言,是否正确,递归算法将导致您的堆栈增长非常显着(如果调用量非常大)并且这根本不会快,并且可能导致堆栈溢出.或者还有一些优化可以使递归函数高效？

如果您在使用函数语言中的递归和C#的算法之间进行一些比较(速度,内存,可读性),我将不胜感激.

我一直在阅读文章,描述如何通过使用尾递归版本来减少快速排序的空间复杂性,但我无法理解这是怎么回事.以下是两个版本:

QUICKSORT(A, p, r)
       q = PARTITION(A, p, r)
       QUICKSORT(A, p, q-1)
       QUICKSORT(A, q+1, r)


TAIL-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
      p = q+1

(来源 - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html)

据我所知,这两个都会导致数组的左半部分和右半部分的递归调用.在这两种情况下,一次只处理一半,因此在任何时候只有一个递归调用将使用堆栈空间.我无法看到尾递归快速排序如何节省空间.

上面的伪代码取自文章 - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html文章中 提供的解释让我更加困惑 -

Quicksort对给定的子数组进行分区并继续递归两次; 一个在左子阵列上,一个在右侧.这些递归调用中的每一个都需要其自己的堆栈空间流.此空间用于在某种递归级别存储数组的索引变量.如果我们想象这是从执行的开始到结束发生的,我们可以看到堆栈空间在每一层加倍.

那么Tail-Recursive-Quicksort如何修复所有这些呢？

好吧,我们现在只对一个子阵列进行递归,而不是在两个子阵列上递归.这消除了在每个执行层加倍堆栈空间的需要.我们通过使用while循环作为执行相同任务的迭代控件来解决这个问题.我们只需更改同一组变量并对新变量使用单个递归调用,而不是需要堆栈为两个递归调用保存变量集.

在常规快速排序的情况下,我没有看到堆栈空间在每个执行层都是如何加倍的.

注意: - 文章中没有提到编译器优化.

是否有一个属性可以告诉编译器必须始终优化方法,即使/o+未设置全局编译器开关？

我问的原因是因为我想要动态创建一个基于现有方法的IL代码的方法; 当代码被优化时,我想要做的操作相当容易,但由于编译器生成了额外的指令,因此在非优化代码中变得非常困难.

编辑:关于非优化的更多细节困扰我...

让我们考虑以下阶乘函数的实现:

static long FactorialRec(int n, long acc)
{
    if (n == 0)
        return acc;
    return FactorialRec(n - 1, acc * n);
}

(注意:我知道有更好的方法来计算阶乘,这只是一个例子)

在启用优化的情况下生成的IL非常简单:

IL_0000:  ldarg.0     
IL_0001:  brtrue.s    IL_0005
IL_0003:  ldarg.1     
IL_0004:  ret         
IL_0005:  ldarg.0     
IL_0006:  ldc.i4.1    
IL_0007:  sub         
IL_0008:  ldarg.1     
IL_0009:  ldarg.0     
IL_000A:  conv.i8     
IL_000B:  mul         
IL_000C:  call        UserQuery.FactorialRec
IL_0011:  ret         

但是未经优化的版本是完全不同的

IL_0000:  nop         
IL_0001:  ldarg.0     
IL_0002:  ldc.i4.0    
IL_0003:  ceq         
IL_0005:  ldc.i4.0    
IL_0006:  ceq         
IL_0008:  stloc.1     
IL_0009:  ldloc.1     
IL_000A:  brtrue.s    IL_0010
IL_000C:  ldarg.1 …