C数据结构模仿C＃的List <List >？
我希望将ac＃方法重构为ac函数以试图获得一些速度，然后在c＃中调用c dll以允许我的程序使用该function。
目前，c＃方法采用整数列表并返回整数列表的列表。 该方法计算了整数的幂集，因此3个int的输入将产生以下输出（在此阶段，int的值不重要，因为它用作内部加权值）
1 2 3 1,2 1,3 2,3 1,2,3 每行代表一个整数列表。 输出指示第一个列表的索引（偏移量为1），而不是值。 因此1,2表示索引0和1处的元素是幂集的元素。
我不熟悉c，那么对于允许c＃访问返回数据的数据结构，我最好的选择是什么？
提前致谢
更新
谢谢大家到目前为止的评论。 以下是问题本质的背景知识。
用于计算集合的幂集的迭代方法是相当直接的。 真正有两个循环和一点点操作。 它只是被称为..很多（事实上，如果集合的大小足够大，数十亿次）。
我对使用c（人们已经指出过的c ++）的看法是，它为性能调优提供了更多的空间。 直接端口可能不会提供任何增加，但它为更多涉及的方法开辟了道路，以便从中获得更高的速度。 即使每次迭代的小幅增加也等同于可测量的增长。
我的想法是移植直接版本，然后努力增加它。 然后随着时间的推移重构它（在SO的每个人的帮助下）。
更新2
来自jalf的另一个公平点，我不必使用list或equivelent。 如果有更好的方法，那么我愿意接受建议。 列表的唯一原因是每组结果的大小不同。
到目前为止的代码……
public List<List> powerset(List 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(); //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
感谢所有的输入和实施工作。 只是为了澄清提出的几点：我不需要输出处于’自然顺序’，而且我对返回的空集不感兴趣。
hughdbrown的实现是intesting但我认为我需要在某个时候存储结果（或至少是它们的一部分）。 听起来内存限制将在运行时间成为真正的问题之前很久就会应用。 部分原因是，我认为我可以使用字节而不是整数，从而提供更多潜在的存储空间。
那么问题是：我们在C＃中达到了这个计算的最大速度吗？ 非托管代码的选项是否提供更多范围。 我知道在很多方面答案是徒劳的，因为即使我们讨厌运行时间，它也只允许原始集合中的额外值。
这一次返回一组powerset。 它基于python代码。 它适用于超过32个元素的powersets。 如果需要少于32，则可以将long更改为int。 它非常快 – 比我之前的算法更快，并且比（我修改为使用yield return版本）P Daddy的代码更快。
static class PowerSet4 { static public IEnumerable> powerset(T[] currentGroupList) { int count = currentGroupList.Length; Dictionary powerToIndex = new Dictionary(); long mask = 1L; for (int i = 0; i < count; i++) { powerToIndex[mask] = currentGroupList[i]; mask <<= 1; } Dictionary result = new Dictionary(); 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(); } } }
您可以下载我在此测试的所有最快版本。
我真的认为使用收益率回报是使计算大型网络成为可能的变化。 预先分配大量内存会大大增加运行时间，并导致算法在很早的时候因内存不足而失败。 原始海报应该弄清楚他一次需要多少套电力。 拥有> 24个元素并不是真正的选择。
此外，确保转移到C / C ++真的是你需要做的速度开始。 使用原始C＃方法（独立，通过unit testing执行），检测新的C / C ++方法（再次，通过unit testing独立），看看现实世界的区别是什么。
我提出这个问题的原因是我担心这可能是一个很好的胜利 – 使用Smokey Bacon的建议，你得到你的列表类，你使用“更快”的C ++，但是调用那个DLL还是有成本的：弹出来使用P / Invoke或COM互操作的运行时具有相当大的性能成本。
在你做之前，一定要从跳跃中获得你的“金钱价值”。
根据OP的更新进行更新
如果你反复调用这个循环，你需要绝对确保整个循环逻辑被封装在一个互操作调用中 – 否则编组的开销（正如其他人提到的那样）肯定会杀了你。
我认为，考虑到问题的描述，问题不是C＃/ .NET比C慢“”，而是代码需要优化的可能性更大。 正如这里提到的另一张海报，你可以在C＃中使用指针来严重提升这种循环的性能，而不需要编组。 在进入复杂的互操作世界之前，我会首先研究一下这个场景。
如果您希望使用C来提高性能，很可能您计划通过使用指针来实现。 C＃允许使用unsafe关键字来使用指针。 你考虑过吗？
您将如何调用此代码..是否会经常调用（例如在循环中？）如果是这样，来回编组数据可能会抵消任何性能提升。
跟进
查看本机代码，而不会牺牲某些互操作选项的.NET性能 。 有一些方法可以在没有太多性能损失的情况下进行互操作，但这些互操作只能在最简单的数据类型中进行。
虽然我仍然认为您应该使用直接.NET来调查加速代码。
跟进2
另外，如果您已经开始混合本机代码和托管代码，我可以建议您使用c ++ / cli创建库。 下面是一个简单的例子。 请注意，我不是一个c ++ / cli人，这段代码没有做任何有用的事情……它只是为了表明你可以轻松地混合原生代码和托管代码。
#include "stdafx.h" using namespace System; System::Collections::Generic::List ^MyAlgorithm(System::Collections::Generic::List ^sourceList); int main(array ^args) { System::Collections::Generic::List ^intList = gcnew System::Collections::Generic::List (); 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 ^modifiedList = MyAlgorithm(intList); Console::WriteLine("After Call"); for each(int i in modifiedList) { Console::WriteLine(i); } } System::Collections::Generic::List ^MyAlgorithm(System::Collections::Generic::List ^sourceList) { int* nativeInts = new int[sourceList->Count]; int nativeIntArraySize = sourceList->Count; //Managed to Native for(int i=0; iCount; i++) { nativeInts[i] = sourceList[i]; } //Do Something to native ints for(int i=0; i ^returnList = gcnew System::Collections::Generic::List (); for(int i=0; iAdd(nativeInts[i]); } return returnList; }
是什么让你觉得通过调用C代码你会获得速度？ C并不比C＃神奇地快。 它当然可以，但它也可以很容易地变慢（和缓慢）。 特别是当您将p / invoke调用纳入本机代码时，很难确定这种方法会加速任何事情。
无论如何，C没有像List这样的东西。 它有原始数组和指针（你可以说int **或多或少相当），但你可能最好使用C ++，它有相同的数据结构。 特别是std :: vector。 没有简单的方法可以将这些数据暴露给C＃，但是因为它几乎是随机分散的（每个列表都是指向某处动态分配的内存的指针）
但是，我怀疑最大的性能提升来自于改进C＃中的算法。
编辑：
我可以在你的算法中看到一些似乎不太理想的东西。 构建列表列表不是免费的。 也许您可以创建单个列表并使用不同的偏移量来表示每个子列表。 或者也许使用’yield return’和IEnumerable而不是显式构建列表可能会更快。
您是否已经分析了代码，找到了花费的时间？
我还要投票来调整你的C＃，特别是通过转向’不安全’的代码并丢失可能是很多边界检查开销。
即使它“不安全”，它也不比C / C ++更“安全”，并且它更容易正确。
下面是一个C＃算法，它应该比你发布的算法快得多（并且使用更少的内存）。 它不使用你使用的整洁二进制技巧，因此代码更长一些。 它有一些比你的更多for循环，并可能需要一两次踩踏它与调试器完全grok它。 但是，一旦你了解它正在做什么，它实际上是一种更简单的方法。
作为奖励，返回的集合处于更“自然”的顺序。 它会按照您在问题中列出的顺序返回集合{1 2 3}的子集。 这不是焦点，但是使用的算法的副作用。
在我的测试中，我发现这个算法的速度比你为一大组22个项目发布的算法快了大约4倍（这是我可以在我的机器上运行的那么大而没有过多的磁盘抖动使结果偏差太多）。 你的一次跑了大约15.5秒，我的大约需要3.6秒。
对于较小的列表，差异不太明显。 对于一组只有10件物品，你的物品在大约7.8秒内跑了10,000次，我的约需要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> PowerSet(IList 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> 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; }
您的结果列表与您的代码产生的结果不匹配。 特别是，您不显示生成空集。
如果我正在制作可能有几十亿个子集的powersets，那么单独生成每个子集而不是一次生成所有子集可能会降低内存需求，从而提高代码的速度。 这个怎么样：
static class PowerSet { 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> 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 set in PowerSet .powerset(intList)) { foreach (int i in set) Console.Write("{0} ", i); Console.WriteLine(); } }
我甚至会免费提供带有模板化参数的小错误算法。 为了增加速度，您可以将powerlist（）内部循环包装在不安全的块中。 它没有太大的区别。
在我的机器上，此代码比OP的代码稍慢，直到集合为16或更大。 但是，所有16个元素的时间都小于0.15秒。 在23个元素中，它在64％的时间内运行。 原始算法不能在我的机器上运行24个或更多元素 - 它耗尽了内存。
此代码需要12秒才能生成数字1到24的电源设置，省略屏幕I / O时间。 那是在12秒内达到1600万，或者每秒约1400K。 十亿（这是你之前引用的），那将是大约760秒。 你觉得这应该花多长时间？
它必须是C，还是C ++也是一个选项？ 如果是C ++，你可以从STL中找到它自己的list类型。 否则，您将必须实现自己的列表 – 查找链接列表或动态大小的数组，以获取有关如何执行此操作的指示。
我同意“优化.NET优先”的观点。 这是最无痛的。 我想如果你使用C＃指针编写一些非托管的.NET代码，除了VM开销之外，它与C执行相同。
P爸爸：
您可以将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; }
这将减少乘法和溢出的可能性降至最低。