模仿 C# 的 List<List<int>> 的 C 数据结构？

C data structure to mimic C#'s List<List<int>>?

提问by jheppinstall

I am looking to refactor a c# method into a c function in an attempt to gain some speed, and then call the c dll in c# to allow my program to use the functionality.

我希望将 ac# 方法重构为 ac 函数以试图获得一些速度，然后在 c# 中调用 c dll 以允许我的程序使用该功能。

Currently the c# method takes a list of integers and returns a list of lists of integers. The method calculated the power set of the integers so an input of 3 ints would produce the following output (at this stage the values of the ints is not important as it is used as an internal weighting value)

目前，c# 方法接受一个整数列表并返回一个整数列表列表。该方法计算整数的幂集，因此 3 个整数的输入将产生以下输出（在此阶段，整数的值并不重要，因为它用作内部权重值）

1
2
3
1,2
1,3
2,3
1,2,3

Where each line represents a list of integers. The output indicates the index (with an offset of 1) of the first list, not the value. So 1,2 indicates that the element at index 0 and 1 are an element of the power set.

其中每一行代表一个整数列表。输出指示第一个列表的索引（偏移量为 1），而不是值。所以 1,2 表示索引 0 和 1 处的元素是幂集的元素。

I am unfamiliar with c, so what are my best options for data structures that will allow the c# to access the returned data?

我不熟悉 c，那么对于允许 c# 访问返回数据的数据结构，我的最佳选择是什么？

Thanks in advance

提前致谢

Update

更新

Thank you all for your comments so far. Here is a bit of a background to the nature of the problem.

感谢大家到目前为止的评论。这是问题本质的一些背景。

The iterative method for calculating the power set of a set is fairly straight forward. Two loops and a bit of bit manipulation is all there is to it really. It just get called..a lot (in fact billions of times if the size of the set is big enough).

计算集合的幂集的迭代方法相当简单。两个循环和一些位操作实际上就是全部。它只是被调用......很多（如果集合的大小足够大，实际上会调用数十亿次）。

My thoughs around using c (c++ as people have pointed out) are that it gives more scope for performance tuning. A direct port may not offer any increase, but it opens the way for more involved methods to get a bit more speed out of it. Even a small increase per iteration would equate to a measurable increase.

我对使用 c（人们指出的 c++）的看法是它为性能调优提供了更多空间。直接端口可能不会提供任何增加，但它为更复杂的方法开辟了道路，以提高速度。即使每次迭代的小幅增加也等同于可测量的增加。

My idea was to port a direct version and then work to increase it. And then refactor it over time (with help from everyone here at SO).

我的想法是移植一个直接版本，然后努力增加它。然后随着时间的推移重构它（在 SO 的每个人的帮助下）。

Update 2

更新 2

Another fair point from jalf, I dont have to use list or equivelent. If there is a better way then I am open to suggestions. The only reason for the list was that each set of results is not the same size.

来自 jalf 的另一个公平点，我不必使用 list 或 equivelent。如果有更好的方法，那么我愿意接受建议。该列表的唯一原因是每组结果的大小不同。

The code so far...

到目前为止的代码...

public List<List<int>> powerset(List<int> currentGroupList)
{
    _currentGroupList = currentGroupList;
    int max;
    int count;

    //Count the objects in the group
    count = _currentGroupList.Count;
    max = (int)Math.Pow(2, count);

    //outer loop
    for (int i = 0; i < max; i++)
    {
        _currentSet = new List<int>();

        //inner loop
        for (int j = 0; j < count; j++)
        {              
            if ((i & (1 << j)) == 0)
            {
                _currentSetList.Add(_currentGroupList.ElementAt(j));                          
            }
        }
        outputList.Add(_currentSetList);
    }   
    return outputList;
}

As you can see, not a lot to it. It just goes round and round a lot!

正如你所看到的，不是很多。它只是绕来绕去很多！

I accept that the creating and building of lists may not be the most efficient way, but I need some way of providing the results back in a manageable way.

我承认创建和构建列表可能不是最有效的方式，但我需要某种方式以可管理的方式返回结果。

Update 2

更新 2

Thanks for all the input and implementation work. Just to clarify a couple of points raised: I dont need the output to be in 'natural order', and also I am not that interested in the empty set being returned.

感谢所有的投入和实施工作。只是为了澄清提出的几点：我不需要输出处于“自然顺序”，而且我对返回的空集也不感兴趣。

hughdbrown's implementation is intesting but i think that i will need to store the results (or at least a subset of them) at some point. It sounds like memory limitiations will apply long before running time becomes a real issue. Partly because of this, I think I can get away with using bytes instead of integers, giving more potential storage.

hughdbrown 的实现是 intesting，但我认为我需要在某个时候存储结果（或至少是其中的一个子集）。听起来内存限制将在运行时间成为真正问题之前很久就适用。部分是因为这个，我想我可以避免使用字节而不是整数，从而提供更多的潜在存储空间。

The question really is then: Have we reached the maximum speed for this calcualtion in C#? Does the option of unmanaged code provide any more scope. I know in many respects the answer is futile, as even if we havled the time to run, it would only allow an extra values in the original set.

那么真正的问题是：我们在 C# 中是否达到了此计算的最大速度？非托管代码选项是否提供更多范围。我知道在很多方面答案都是徒劳的，因为即使我们有足够的时间运行，它也只允许原始集合中的额外值。

采纳答案by hughdbrown

This returns one set of a powerset at a time. It is based on python code here. It works for powersets of over 32 elements. If you need fewer than 32, you can change long to int. It is pretty fast -- faster than my previous algorithm and faster than (my modified to use yield return version of) P Daddy's code.

这一次返回一组 powerset。它基于这里的python代码。它适用于超过 32 个元素的 powerset。如果您需要少于 32 个，您可以将 long 更改为 int。它非常快——比我以前的算法快，比（我修改为使用收益返回版本的）P Daddy 的代码快。

static class PowerSet4<T>
{
    static public IEnumerable<IList<T>> powerset(T[] currentGroupList)
    {
        int count = currentGroupList.Length;
        Dictionary<long, T> powerToIndex = new Dictionary<long, T>();
        long mask = 1L;
        for (int i = 0; i < count; i++)
        {
            powerToIndex[mask] = currentGroupList[i];
            mask <<= 1;
        }

        Dictionary<long, T> result = new Dictionary<long, T>();
        yield return result.Values.ToArray();

        long max = 1L << count;
        for (long i = 1L; i < max; i++)
        {
            long key = i & -i;
            if (result.ContainsKey(key))
                result.Remove(key);
            else
                result[key] = powerToIndex[key];
            yield return result.Values.ToArray();
        }
    }
}

You can download all the fastest versions I have tested here.

您可以在此处下载我测试过的所有最快版本。

I really think that using yield return is the change that makes calculating large powersets possible. Allocating large amounts of memory upfront increases runtime dramatically and causes algorithms to fail for lack of memory very early on. Original Poster should figure out how many sets of a powerset he needs at once. Holding all of them is not really an option with >24 elements.

我真的认为使用收益回报是使计算大功率集成为可能的变化。预先分配大量内存会显着增加运行时间，并导致算法很早就因内存不足而失败。原始海报应该弄清楚他一次需要多少套powerset。拥有所有这些并不是拥有 >24 个元素的真正选项。

回答by Smokey Bacon Esq.

Does it have to be C, or is C++ an option too? If C++, you can just its own listtype from the STL. Otherwise, you'll have to implement your own list - look up linked lists or dynamically sized arrays for pointers on how to do this.

它必须是 C，还是 C++ 也是一种选择？如果是 C++，则可以list从 STL 中获得它自己的类型。否则，您将必须实现自己的列表 - 查找链接列表或动态大小的数组以获取有关如何执行此操作的指针。

回答by Giovanni Galbo

If you are looking to use C for a performance gain, most likely you are planning to do so through the use of pointers. C# does allow for use of pointers, using the unsafe keyword. Have you considered that?

如果您希望使用 C 来提高性能，很可能您打算通过使用指针来实现。C# 允许使用指针，使用 unsafe 关键字。你考虑过吗？

Also how will you be calling this code.. will it be called often (e.g. in a loop?) If so, marshalling the data back and forth may more than offset any performance gains.

此外，您将如何调用此代码......它会经常被调用（例如在循环中？）如果是这样，来回编组数据可能会抵消任何性能提升。

---

---

Follow Up

跟进

Take a look at Native code without sacrificing .NET performancefor some interop options. There are ways to interop without too much of a performance loss, but those interops can only happen with the simplest of data types.

在不牺牲某些互操作选项的.NET 性能的情况下查看本机代码。有很多互操作方法不会造成太多性能损失，但这些互操作只能在最简单的数据类型中发生。

Though I still think that you should investigate speeding up your code using straight .NET.

虽然我仍然认为你应该研究使用直接的 .NET 来加速你的代码。

---

---

Follow Up 2

跟进 2

Also, may I suggest that if you have your heart set on mixing native code and managed code, that you create your library using c++/cli. Below is a simple example. Note that I am not a c++/cli guy, and this code doesn't do anything useful...its just meant to show how easily you can mix native and managed code.

另外，我是否可以建议，如果您一心想要混合本机代码和托管代码，那么您可以使用 c++/cli 创建您的库。下面是一个简单的例子。请注意，我不是一个 c++/cli 人，这段代码没有做任何有用的事情……它只是为了展示您可以多么轻松地混合本机和托管代码。

#include "stdafx.h"

using namespace System;

System::Collections::Generic::List<int> ^MyAlgorithm(System::Collections::Generic::List<int> ^sourceList);


int main(array<System::String ^> ^args)
{
    System::Collections::Generic::List<int> ^intList = gcnew System::Collections::Generic::List<int>();

    intList->Add(1);
    intList->Add(2);
    intList->Add(3);
    intList->Add(4);
    intList->Add(5);

    Console::WriteLine("Before Call");
    for each(int i in intList)
    {
        Console::WriteLine(i);
    }

    System::Collections::Generic::List<int> ^modifiedList = MyAlgorithm(intList);

    Console::WriteLine("After Call");
    for each(int i in modifiedList)
    {
        Console::WriteLine(i);
    }
}


System::Collections::Generic::List<int> ^MyAlgorithm(System::Collections::Generic::List<int> ^sourceList)
{
    int* nativeInts = new int[sourceList->Count];

    int nativeIntArraySize = sourceList->Count;

    //Managed to Native
    for(int i=0; i<sourceList->Count; i++)
    {
        nativeInts[i] = sourceList[i];
    }

    //Do Something to native ints
    for(int i=0; i<nativeIntArraySize; i++)
    {
        nativeInts[i]++;
    }


    //Native to Managed
    System::Collections::Generic::List<int> ^returnList = gcnew System::Collections::Generic::List<int>();
    for(int i=0; i<nativeIntArraySize; i++)
    {
        returnList->Add(nativeInts[i]);
    }


    return returnList;
}

回答by John Rudy

Also, be sure that moving to C/C++ is really what you need to do for speed to begin with. Instrument the original C# method (standalone, executed via unit tests), instrument the new C/C++ method (again, standalone via unit tests) and see what the real world difference is.

此外，请确保迁移到 C/C++ 确实是您开始时需要做的。检测原始 C# 方法（独立，通过单元测试执行），检测新的 C/C++ 方法（同样，通过单元测试独立），看看现实世界的区别是什么。

The reason I bring this up is that I fear it may be a pyrhhic victory -- using Smokey Bacon's advice, you get your list class, you're in "faster" C++, but there's still a cost to calling that DLL: Bouncing out of the runtime with P/Invoke or COM interop carries a fairly substantial performance cost.

我提出这个的原因是我担心这可能是一场巨大的胜利——使用 Smokey Bacon 的建议，你得到了你的列表类，你在“更快”的 C++ 中，但是调用那个 DLL 仍然需要付出代价：反弹使用 P/Invoke 或 COM 互操作的运行时会带来相当大的性能成本。

Be sure you're getting your "money's worth" out of that jump before you do it.

在你这样做之前，确保你从那次跳跃中获得了“金钱的价值”。

Update based on the OP's Update

基于 OP 的更新更新

If you're calling this loop repeatedly, you need to absolutely make sure that the entire loop logic is encapsulated in a single interop call -- otherwise the overhead of marshalling (as others here have mentioned) will definitely kill you.

如果你重复调用这个循环，你需要绝对确保整个循环逻辑被封装在一个互操作调用中——否则编组的开销（正如其他人提到的）肯定会杀死你。

I do think, given the description of the problem, that the issue isn't that C#/.NET is "slower" than C, but more likely that the code needs to be optimized. As another poster here mentioned, you can use pointers in C# to seriously boost performance in this kind of loop, without the need for marshalling. I'd look into that first, before jumping into a complex interop world, for this scenario.

我确实认为，鉴于问题的描述，问题不在于 C#/.NET 比 C“慢”，而更有可能是代码需要优化。正如这里的另一张海报所提到的，您可以在 C# 中使用指针来大幅提高这种循环中的性能，而无需进行编组。对于这种情况，在进入复杂的互操作世界之前，我会先研究一下。

回答by jalf

What makes you think you'll gain speed by calling into C code? C isn't magically faster than C#. It can be, of course, but it can also easily be slower (and buggier). Especially when you factor in the p/invoke calls into native code, it's far from certain that this approach will speed up anything.

是什么让您认为通过调用 C 代码可以提高速度？C 并不神奇地比 C# 快。当然可以，但它也很容易变慢（和错误）。尤其是当您将 p/invoke 调用考虑到本机代码中时，还远不能确定这种方法会加速任何事情。

In any case, C doesn't have anything like List. It has raw arrays and pointers (and you could argue that int** is more or less equivalent), but you're probably better off using C++, which does have equivalent datastructures. In particular, std::vector. There are no simple ways to expose this data to C# however, since it will be scattered pretty much randomly (each list is a pointer to some dynamically allocated memory somewhere)

无论如何，C 没有像 List 这样的东西。它具有原始数组和指针（您可能会争辩说 int** 或多或少是等价的），但您最好使用 C++，它确实具有等价的数据结构。特别是 std::vector。然而，没有简单的方法可以将这些数据暴露给 C#，因为它会随机分散（每个列表都是指向某处动态分配内存的指针）

However, I suspect the biggest performance improvement comes from improving the algorithm in C#.

但是，我怀疑最大的性能改进来自改进 C# 中的算法。

Edit:

编辑：

I can see several things in your algorithm that seem suboptimal. Constructing a list of lists isn't free. Perhaps you can create a single list and use different offsets to represent each sublist. Or perhaps using 'yield return' and IEnumerable instead of explicitly constructing lists might be faster.

我可以在你的算法中看到一些看起来不太理想的东西。构建列表列表不是免费的。也许您可以创建一个列表并使用不同的偏移量来表示每个子列表。或者也许使用“收益回报”和 IEnumerable 而不是显式构建列表可能会更快。

Have you profiled your code, found out where the time is being spent?

你有没有分析你的代码，找出时间花在哪里？

回答by Will Dean

I'm also going to put in a vote for tuning-up your C#, particularly by going to 'unsafe' code and losing what might be a lot of bounds-checking overhead.

我还将投票支持调整您的 C#，特别是通过使用“不安全”代码并丢失可能是大量边界检查开销的内容。

Even though it's 'unsafe', it's no less 'safe' than C/C++, and it's dramatically easier to get right.

尽管它是“不安全的”，但它的“安全性”并不比 C/C++ 差，而且要做到正确要容易得多。

回答by hughdbrown

Your list of results does not match the results your code would produce. In particular, you do not show generating the empty set.

您的结果列表与您的代码将产生的结果不匹配。特别是，您没有显示生成空集。

If I were producing powersets that could have a few billion subsets, then generating each subset separately rather than all at once might cut down on your memory requirements, improving your code's speed. How about this:

如果我生成的 powersets 可能有几十亿个子集，那么单独生成每个子集而不是一次生成所有子集可能会减少您的内存需求，提高您的代码速度。这个怎么样：

static class PowerSet<T>
{
    static long[] mask = { 1L << 0, 1L << 1, 1L << 2, 1L << 3, 
                           1L << 4, 1L << 5, 1L << 6, 1L << 7, 
                           1L << 8, 1L << 9, 1L << 10, 1L << 11, 
                           1L << 12, 1L << 13, 1L << 14, 1L << 15, 
                           1L << 16, 1L << 17, 1L << 18, 1L << 19, 
                           1L << 20, 1L << 21, 1L << 22, 1L << 23, 
                           1L << 24, 1L << 25, 1L << 26, 1L << 27, 
                           1L << 28, 1L << 29, 1L << 30, 1L << 31};
    static public IEnumerable<IList<T>> powerset(T[] currentGroupList)
    {
        int count = currentGroupList.Length;
        long max = 1L << count;
        for (long iter = 0; iter < max; iter++)
        {
            T[] list = new T[count];
            int k = 0, m = -1;
            for (long i = iter; i != 0; i &= (i - 1))
            {
                while ((mask[++m] & i) == 0)
                    ;
                list[k++] = currentGroupList[m];
            }
            yield return list;
        }
    }
}

Then your client code looks like this:

然后您的客户端代码如下所示：

    static void Main(string[] args)
    {
        int[] intList = { 1, 2, 3, 4 };
        foreach (IList<int> set in PowerSet<int>.powerset(intList))
        {
            foreach (int i in set)
                Console.Write("{0} ", i);
            Console.WriteLine();
        }
    }

I'll even throw in a bit-twiddling algorithm with templated arguments for free. For added speed, you can wrap the powerlist() inner loop in an unsafe block. It doesn't make much difference.

我什至会免费提供一个带有模板化参数的位处理算法。为了提高速度，您可以将 powerlist() 内循环包装在一个不安全的块中。它没有太大区别。

On my machine, this code is slightly slower than the OP's code until the sets are 16 or larger. However, all times to 16 elements are less than 0.15 seconds. At 23 elements, it runs in 64% of the time. The original algorithm does not run on my machine for 24 or more elements -- it runs out of memory.

在我的机器上，此代码比 OP 的代码稍慢，直到集合为 16 或更大。但是，所有 16 个元素的时间都小于 0.15 秒。在 23 个元素时，它运行的时间为 64%。原始算法没有在我的机器上运行 24 个或更多元素——它耗尽了内存。

This code takes 12 seconds to generate the power set for the numbers 1 to 24, omitting screen I/O time. That's 16 million-ish in 12 seconds, or about 1400K per second. For a billion (which is what you quoted earlier), that would be about 760 seconds. How long do you think this should take?

此代码需要 12 秒来生成数字 1 到 24 的电源集，省略屏幕 I/O 时间。这是 12 秒内 1600 万次，或每秒约 1400K。对于十亿（这是您之前引用的），这大约是 760 秒。您认为这需要多长时间？

回答by P Daddy

Below is a C# algorithm that should be much faster (and use less memory) than the algorithm you posted. It doesn't use the neat binary trick yours uses, and as a result, the code is a good bit longer. It has a few more forloops than yours, and might take a time or two stepping through it with the debugger to fully grok it. But it's actually a simpler approach, once you understand what it's doing.

下面是一个 C# 算法，它应该比您发布的算法快得多（并且使用更少的内存）。它没有使用您使用的简洁的二进制技巧，因此，代码要长一些。它for比你的循环多一些，可能需要一两段时间用调试器逐步完成它才能完全理解它。但它实际上是一种更简单的方法，一旦你了解它在做什么。

As a bonus, the returned sets are in a more "natural" order. It would return subsets of the set {1 2 3} in the same order you listed them in your question. That wasn't a focus, but is a side effect of the algorithm used.

作为奖励，返回的集合以更“自然”的顺序排列。它会按照您在问题中列出的顺序返回集合 {1 2 3} 的子集。这不是重点，而是所用算法的副作用。

In my tests, I found this algorithm to be approximately 4 times faster than the algorithm you posted for a large set of 22 items (which was as large as I could go on my machine without excessive disk-thrashing skewing the results too much). One run of yours took about 15.5 seconds, and mine took about 3.6 seconds.

在我的测试中，我发现这个算法比你为 22 个项目发布的算法快大约 4 倍（这是我在我的机器上可以运行的最大的算法，而没有过多的磁盘抖动使结果扭曲太多）。你的一次运行大约需要 15.5 秒，而我的运行大约需要 3.6 秒。

For smaller lists, the difference is less pronounced. For a set of only 10 items, yours ran 10,000 times in about 7.8 seconds, and mine took about 3.2 seconds. For sets with 5 or fewer items, they run close to the same time. With many iterations, yours runs a little faster.

对于较小的列表，差异不太明显。对于只有 10 个项目的一组，你的在大约 7.8 秒内运行了 10,000 次，而我的大约需要 3.2 秒。对于包含 5 个或更少项目的集合，它们几乎同时运行。通过多次迭代，您的运行速度会更快一些。

Anyway, here's the code. Sorry it's so long; I tried to make sure I commented it well.

无论如何，这是代码。抱歉这么长；我试图确保我评论得很好。

/* 
 * Made it static, because it shouldn't really use or modify state data.
 * Making it static also saves a tiny bit of call time, because it doesn't
 * have to receive an extra "this" pointer.  Also, accessing a local
 * parameter is a tiny bit faster than accessing a class member, because
 * dereferencing the "this" pointer is not free.
 * 
 * Made it generic so that the same code can handle sets of any type.
 */
static IList<IList<T>> PowerSet<T>(IList<T> set){
    if(set == null)
        throw new ArgumentNullException("set");

    /*
     * Caveat:
     * If set.Count > 30, this function pukes all over itself without so
     * much as wiping up afterwards.  Even for 30 elements, though, the
     * result set is about 68 GB (if "set" is comprised of ints).  24 or
     * 25 elements is a practical limit for current hardware.
     */
    int   setSize     = set.Count;
    int   subsetCount = 1 << setSize; // MUCH faster than (int)Math.Pow(2, setSize)
    T[][] rtn         = new T[subsetCount][];
    /* 
     * We don't really need dynamic list allocation.  We can calculate
     * in advance the number of subsets ("subsetCount" above), and
     * the size of each subset (0 through setSize).  The performance
     * of List<> is pretty horrible when the initial size is not
     * guessed well.
     */

    int subsetIndex = 0;
    for(int subsetSize = 0; subsetSize <= setSize; subsetSize++){
        /*
         * The "indices" array below is part of how we implement the
         * "natural" ordering of the subsets.  For a subset of size 3,
         * for example, we initialize the indices array with {0, 1, 2};
         * Later, we'll increment each index until we reach setSize,
         * then carry over to the next index.  So, assuming a set size
         * of 5, the second iteration will have indices {0, 1, 3}, the
         * third will have {0, 1, 4}, and the fifth will involve a carry,
         * so we'll have {0, 2, 3}.
         */
        int[] indices = new int[subsetSize];
        for(int i = 1; i < subsetSize; i++)
            indices[i] = i;

        /*
         * Now we'll iterate over all the subsets we need to make for the
         * current subset size.  The number of subsets of a given size
         * is easily determined with combination (nCr).  In other words,
         * if I have 5 items in my set and I want all subsets of size 3,
         * I need 5-pick-3, or 5C3 = 5! / 3!(5 - 3)! = 10.
         */
        for(int i = Combination(setSize, subsetSize); i > 0; i--){
            /*
             * Copy the items from the input set according to the
             * indices we've already set up.  Alternatively, if you
             * just wanted the indices in your output, you could
             * just dup the index array here (but make sure you dup!
             * Otherwise the setup step at the bottom of this for
             * loop will mess up your output list!  You'll also want
             * to change the function's return type to
             * IList<IList<int>> in that case.
             */
            T[] subset = new T[subsetSize];
            for(int j = 0; j < subsetSize; j++)
                subset[j] = set[indices[j]];

            /* Add the subset to the return */
            rtn[subsetIndex++] = subset;

            /*
             * Set up indices for next subset.  This looks a lot
             * messier than it is.  It simply increments the
             * right-most index until it overflows, then carries
             * over left as far as it needs to.  I've made the
             * logic as fast as I could, which is why it's hairy-
             * looking.  Note that the inner for loop won't
             * actually run as long as a carry isn't required,
             * and will run at most once in any case.  The outer
             * loop will go through as few iterations as required.
             * 
             * You may notice that this logic doesn't check the
             * end case (when the left-most digit overflows).  It
             * doesn't need to, since the loop up above won't
             * execute again in that case, anyway.  There's no
             * reason to waste time checking that here.
             */
            for(int j = subsetSize - 1; j >= 0; j--)
                if(++indices[j] <= setSize - subsetSize + j){
                    for(int k = j + 1; k < subsetSize; k++)
                        indices[k] = indices[k - 1] + 1;
                    break;
                }
        }
    }
    return rtn;
}

static int Combination(int n, int r){
    if(r == 0 || r == n)
        return 1;

    /*
     * The formula for combination is:
     *
     *       n!
     *   ----------
     *   r!(n - r)!
     *
     * We'll actually use a slightly modified version here.  The above
     * formula forces us to calculate (n - r)! twice.  Instead, we only
     * multiply for the numerator the factors of n! that aren't canceled
     * out by (n - r)! in the denominator.
     */

    /*
     * nCr == nC(n - r)
     * We can use this fact to reduce the number of multiplications we
     * perform, as well as the incidence of overflow, where r > n / 2
     */
    if(r > n / 2) /* We DO want integer truncation here (7 / 2 = 3) */
        r = n - r;

    /*
     * I originally used all integer math below, with some complicated
     * logic and another function to handle cases where the intermediate
     * results overflowed a 32-bit int.  It was pretty ugly.  In later
     * testing, I found that the more generalized double-precision
     * floating-point approach was actually *faster*, so there was no
     * need for the ugly code.  But if you want to see a giant WTF, look
     * at the edit history for this post!
     */

    double denominator = Factorial(r);
    double numerator   = n;
    while(--r > 0)
        numerator *= --n;

    return (int)(numerator / denominator + 0.1/* Deal with rounding errors. */);
}

/*
 * The archetypical factorial implementation is recursive, and is perhaps
 * the most often used demonstration of recursion in text books and other
 * materials.  It's unfortunate, however, that few texts point out that
 * it's nearly as simple to write an iterative factorial function that
 * will perform better (although tail-end recursion, if implemented by
 * the compiler, will help to close the gap).
 */
static double Factorial(int x){
    /*
     * An all-purpose factorial function would handle negative numbers
     * correctly - the result should be Sign(x) * Factorial(Abs(x)) -
     * but since we don't need that functionality, we're better off
     * saving the few extra clock cycles it would take.
     */

    /*
     * I originally used all integer math below, but found that the
     * double-precision floating-point version is not only more
     * general, but also *faster*!
     */

    if(x < 2)
        return 1;

    double rtn = x;
    while(--x > 1)
        rtn *= x;

    return rtn;
}

回答by Paul Nathan

I concur with the "optimize .NET first" opinion. It's the most painless. I imagine that if you wrote some unmanaged .NET code using C# pointers, it'd be identical to C execution, except for the VM overhead.

我同意“首先优化 .NET”的意见。这是最无痛的。我想如果您使用 C# 指针编写一些非托管 .NET 代码，它与 C 执行相同，除了 VM 开销。

回答by hughdbrown

P Daddy:

P爸爸：

You could change your Combination() code to this:

您可以将 Combination() 代码更改为：

    static long Combination(long n, long r)
    {
        r = (r > n - r) ? (n - r) : r;
        if (r == 0)
            return 1;
        long result = 1;
        long k = 1;
        while (r-- > 0)
        {
            result *= n--;
            result /= k++;
        }

        return result;
    }

This will reduce the multiplications and the chance of overflow to a minimum.

这将减少乘法和溢出的机会到最小。