用C语言数据结构模拟C#的List<List<int>>？

Question

我想将一个C#方法重构为C函数，以提高速度，然后在C#中调用C DLL，使我的程序能够使用该功能。目前，C#方法接收整数列表并返回整数列表的列表。该方法计算整数的幂集，因此3个整数的输入将产生以下输出（在此阶段，整数的值并不重要，因为它是作为内部加权值使用的）。

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

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

我对c不熟悉，那么哪些数据结构是让c#可以访问返回数据的最佳选择？

提前感谢您。

更新

非常感谢大家迄今为止的评论。以下是问题性质的一些背景信息。

计算集合的幂集的迭代方法非常简单。实际上只需要两个循环和一些位操作即可。它被频繁调用（事实上，如果集合大小足够大，它会被调用数十亿次）。

我认为使用c（正如人们指出的c++）可以更好地进行性能调优。直接移植可能不会提供任何增加，但它为获得更多速度提供了更多参与的方法。即使每次迭代只有小幅度增加，也会导致可衡量的增加。

我的想法是先移植一个直接的版本，然后努力提高它的性能。然后随着时间的推移进行重构（在SO的所有人的帮助下）。

更新2

jalf提出了另一个合理的观点，我不必使用列表或等效物。如果有更好的方法，我愿意听取建议。使用列表的唯一原因是每组结果的大小不同。

到目前为止的代码...

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

正如您所看到的，这并不是很复杂。它只是一直在循环！

我知道创建和构建列表可能不是最有效的方法，但我需要一种以可管理的方式提供结果的方法。

更新2

感谢所有的输入和实现工作。为了澄清一些问题：我不需要输出按照“自然顺序”，而且我对返回空集不是那么感兴趣。

hughdbbrown的实现很有趣，但我认为我需要在某个时候存储结果（或至少其中的一个子集）。听起来内存限制将在运行时间成为真正问题之前应用。

部分原因是这样，我认为我可以使用字节而不是整数，从而提供更多的存储空间。

问题真正在于：我们已经达到了C#计算的最大速度吗？非托管代码的选项是否提供了更多的余地。我知道在许多方面，答案是徒劳无功的，因为即使我们减少了运行时间，也只能允许原始集合中的额外值。

- jxh00u

---

不，它只是指向一个整数指针。这种简化会给我们亲爱的jxh00u带来许多调试痛苦的时间。 - Vinko Vrsalovic

这要看你具体用它来做什么了 :) - leppie

难道Interop的减速只会在调用时发生一次吗？ - jheppinstall

回复：我认为我需要存储结果（或至少其中的一个子集）您将在运行时确定某些子集是有趣/有价值的吗？您能告诉我们您正在构建什么类型的应用程序吗？以及您需要一次计算多少个元素的幂集？ - hughdbrown

在编程中，我们经常需要找到一个集合的子集，这些子集满足一定的条件。通常情况下，我们会使用递归来解决这个问题，但是这种方法可能会很慢。因此，我们可以尝试使用一些动态或启发式的方法来更快地得到结果。输入值将是一个“成本”。对于每个返回的幂集，将其值相加（或在循环中保持运行总数）将确定该集合是否“有效”。我同意yield return非常有用。 - jheppinstall

Answer 1

此外，确保转换到C/C++真的是为了提高速度而需要的。对原始的C#方法进行仪器化（作为独立的单元测试执行），对新的C/C++方法进行仪器化（同样是独立的单元测试），然后看看实际的差异。

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

在你这样做之前，请确保你得到了你的“物有所值”的回报。

根据OP的更新更新

如果你重复调用这个循环，你必须绝对确保整个循环逻辑被封装在一个单一的互操作调用中——否则，类型转换的开销（正如其他人在这里提到的）一定会让你崩溃。

我认为，根据问题的描述，问题不是C#/.NET比C“慢”，而更可能是代码需要优化。正如另一个帖子中提到的，你可以在C#中使用指针来严重提高这种循环的性能，而无需进行类型转换。在这种情况下，我建议首先研究这个，而不是跳入一个复杂的互操作世界。

- John Rudy

Answer 2

如果您想使用C语言来提高性能，很可能是通过使用指针来实现的。 C＃允许使用指针，使用unsafe关键字即可。您考虑过这一点吗？

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

---

跟进

查看原生代码而不牺牲.NET性能以获取一些交互选项。有一些方法可以进行交互而不会损失太多性能，但这些交互只能发生在最简单的数据类型中。

虽然我仍然认为您应该通过直接使用.NET来加快代码速度。

---

跟进2

另外，如果您想混合使用本地代码和托管代码，我建议您使用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;
}

- Giovanni Galbo

Answer 3

你为什么认为调用C代码会让你获得速度？C并不比C＃快，除非你优化好了。它当然可以更快，但也很容易变慢（且容易出现错误）。特别是在考虑到与本地代码的p/invoke调用时，这种方法是否能加速完全不确定。

无论如何，C没有像List这样的东西。它有原始数组和指针（您可以认为int **或多或少相当于List），但您可能最好使用具有等效数据结构的C ++。特别是std :: vector。

然而，将这些数据暴露给C＃没有简单的方法，因为它们可能会随机散布（每个List都是指向某处的动态分配内存的指针）。

无论如何，我怀疑提高C＃算法的性能会带来最大的性能改进。

编辑：

我看到你的算法中有几件事似乎不太优秀。构建一个列表的列表不是免费的。也许您可以创建一个单一的列表，并使用不同的偏移量来表示每个子列表。或者，使用“yield return”和IEnumerable而不是显式构造列表可能会更快。

您已经剖析了代码，在哪里花费时间了吗？

- jalf

Answer 4

我还要提醒您对C#进行调优，特别是使用“不安全”代码并减少可能存在的边界检查开销。

虽然这是“不安全”的，但与C/C++一样“安全”，而且更容易正确实现。

- Will Dean

Answer 5

这个函数每次返回一个幂集的子集。它基于这里的Python代码。它可以处理超过32个元素的幂集。如果您需要少于32个元素，可以将long更改为int。它非常快速--比我的先前算法和（我的修改后使用yield return版本的）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();
        }
    }
}

你可以在这里下载我测试过的所有最快版本：链接。

我认为使用yield return是计算大型幂集的关键。预先分配大量内存会显著增加运行时间，并导致算法因缺乏内存而很早就失败。原帖作者应该弄清楚他一次需要多少个幂集。对于超过24个元素，无法保持所有幂集。

- hughdbrown

---

我认为你说得对，是yield使得差异。我非常钦佩你提供最快速实现的坚韧精神，以及提出的几个非常有效的观点。同时也要表扬P Daddy和所有提供意见的人。 - jheppinstall

P Daddy有一个很酷的想法，我还没有提出来——分配固定大小的数组，使其长度合适。相比之下，调整列表的大小是昂贵的。我的其他代码制作了最大长度的列表，以免重新分配。 - hughdbrown

如果我在做这件事情，我会编写一个自定义的 IList<T> 类，它包装了一个大小固定为 currentGroupList.Length 的数组。你可以很容易地获得比基于字典的实现更好的性能。 - Qwertie

Answer 6

以下是一个C#算法，应该比您发布的算法快得多（并且使用的内存较少）。 它不使用您的二进制技巧，因此代码要长得多。 它比您的多了一些for循环，并且可能需要通过调试器逐步查看几次才能完全理解它。 但是，一旦您理解了它正在做什么，它实际上是一种更简单的方法。

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

在我的测试中，我发现对于包含22个项目的大型集合，与您发布的算法相比，此算法大约快4倍（这是我在我的计算机上可以达到的最大值，否则会导致过多的磁盘抖动而使结果产生偏差）。 您的运行需要约15.5秒，而我的只需要约3.6秒。

对于较小的列表，差异不太明显。 对于只有10个项目的集合，您的运行时间约为7.8秒，而我的运行时间约为3.2秒。 对于5个或更少的项目集，它们运行时间接近。 在许多迭代中，您的运行速度略快。

无论如何，这是代码。 很抱歉它太长了; 我试图确保我对其进行了良好的注释。

/* 
 * 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;
}

- P Daddy

---

好的，那是一些相当不错的代码。这里有我不理解的地方：当你把问题规模从n增加到n+1时，数据量应该翻倍，运行时间也应该翻倍。但我看到的情况并非如此：18个项目耗时0.16秒，24个项目耗时0.97秒。数据量增加了64倍，所需时间却增加了6倍。 - hughdbrown

数据增长超过一倍。子集数量翻倍，这些集合的成员总数增加了(n+1)*2/n，这意味着随着n从1变为2，它会增加到四倍，从2变为3时会增加到三倍，并且当n趋近于无穷大时，它会接近两倍的因子。(续...) - P Daddy

糟糕！我发现了一个bug...看起来我的组合中的分子溢出了。稍后我会进行更新。 - P Daddy

我重新运行了你基于浮点数的阶乘代码，它生成了你所说的结果。我不知道之前是怎么得到我引用的结果的。不过，我提供的组合函数更快。请查看： http://www.iwebthereforeiam.com/files/TestYieldReturn.zip 你的代码是Powerset3.cs。 - hughdbrown

而你的代码最多只能达到 n * (20 + b * 2)（其中 20 + b 是你的字典的大致存储空间），因此，尽管我的代码需要约 68 GB 的存储空间来存储一个由 30 个 4 字节项目组成的完整幂集，但你的代码在任何给定时间都只需要使用不到 1 KB 的存储空间。 - P Daddy

Answer 7

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

如果我要生成可能有数十亿个子集的幂集，则单独生成每个子集而不是一次性生成所有子集可能会减少内存需求，提高代码速度。以下是一个示例：

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

那么你的客户端代码看起来像这样：

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

我甚至可以免费为您提供一个带有模板参数的位操作算法。为了增加速度，您可以将powerlist（）内部循环包装在不安全块中。这并没有多大区别。

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

该代码需要12秒来生成数字1到24的幂集，省略屏幕I / O时间。那是大约1600万次计算在12秒内，每秒约1400K。对于10亿（您之前引用的数字），这将需要大约760秒。您认为这应该花多长时间？

- hughdbrown

---

这个解决方案得到了我的支持 - 虽然我有几个修改建议。将汉明重量计算移动到内部循环的开头，所以 T[] list = new T[weight]，而不是 T[count]。另外，你的 i & (i-1) 位操作是一种悲观的做法，可以直接进行简单操作。 - Jimmy

那么i & (i-1)怎么样？你的意思是在循环底部使用：i ^= mask？那应该可以。不清楚你所说的“汉明重量”是什么。在检查整个int之前，我无法知道有多少位被设置。分配最大内存要简单得多。更快。内存没有惩罚——逐个创建。 - hughdbrown

Answer 8

它必须是C语言吗？还是C++也可以？如果是C++，你可以使用STL中的list类型。否则，你就需要实现自己的列表 - 查找链表或动态大小的指针数组以获取如何实现的指导。

- Smokey Bacon Esq.

---

不要使用C++的list，它完全不同。在C++中，list是一个链表。相当于C#的List<T>的是std::vector。 - jalf

Answer 9

我同意“优先优化.NET”的观点。这是最轻松的方法。我想象一下，如果你使用C#指针编写了一些非托管的.NET代码，除了VM开销之外，它将与C执行完全相同。

- Paul Nathan

Answer 10

P Daddy：

你可以将你的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;
    }

这将把乘法和溢出的机会降到最低。

- hughdbrown

---

这是一个有趣的方法。但它有点偏离了重点。性能是主要目标，而不是通用性，而且这个的性能相当糟糕，很抱歉要说。此外，它也存在着与大输入相同的溢出问题（在n = 31和r = 13时出现）。(...继续) - P Daddy

在测试中，我发现一种更简单的实现方式，它使用双精度浮点数来存储中间结果，我知道这种方法更通用，而且速度更快！我要再次修改我的代码。 - P Daddy

你最新的修订版本确实好多了，但仍然比我帖子中的浮点数版本慢了大约3-4倍。你已经用除法代替了乘法，但是除法（即使是整数）比乘法慢得多。 - P Daddy

好的，在运行时生成一个组合表并将其放入您的代码中以进行查找。请参考以下Python代码： http://www.iwebthereforeiam.com/files/combination_table.py - hughdbrown