C数据结构以模拟C＃的List< List< int>？ [英] C data structure to mimic C#'s List<List<int>>?
问题描述
我正在将ac＃方法重构为ac函数，以尝试获得一些速度，然后在c＃中调用c dll以允许我的程序使用该功能。
目前，c＃方法获取整数列表，并返回整数列表的列表。该方法计算整数的幂集，因此3个int的输入将产生以下输出（在此阶段，int的值不重要，因为它用作内部加权值）
1
2
3
1,2
1,3
2,3
1,2,3
其中每行表示整数列表。输出指示第一个列表的索引（偏移量为1），而不是值。所以1,2表示索引0和1的元素是功率集的元素。
我不熟悉c，那么我最好的数据选择是什么结构将允许c＃访问返回的数据？
提前感谢
更新
感谢大家的意见。这是一个有关这个问题性质的背景。
用于计算集合的集合的迭代方法是相当简单的。两个循环和一点位操作都是真的。它只是得到call..a很多（实际上数十亿次，如果集合的大小足够大）。
我的想法是使用c（c ++作为人有指出的是，它为性能调优提供了更多的空间。直接港口可能不会增加任何增长，但它为更多涉及的方法提供了更多的速度。即使是每次迭代的小幅度增加都等于可衡量的增长。
我的想法是移植一个直接版本，然后努力增加它。然后随着时间的推移重构（在SO的所有人的帮助下）。
更新2
另一个公平的点从jalf，我不必使用列表或等同。如果有更好的方法，那么我可以接受建议。列表的唯一原因是每组结果的大小不一样。
到目前为止的代码...
public List< List< int>> powerset（List< int> currentGroupList）
{
_currentGroupList = currentGroupList;
int max;
int count;
//计算组中的对象
count = _currentGroupList.Count;
max =（int）Math.Pow（2，count）;
//外循环
for（int i = 0; i
_currentSet = new List< int&
//内循环
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＃中达到了这个计算的最大速度？非托管代码的选项是否提供更多的范围。我知道在许多方面，答案是徒劳的，即使我们耽搁了运行时间，只允许在原始集合中增加一些值。
一次返回一组电源。它基于python代码 here 。它适用于超过32个元素的电源。如果您需要少于32个，您可以将long更改为int。它比我以前的算法快 - （我修改为使用收益返回版本）P Daddy的代码，速度非常快。
静态类PowerSet4< T>
{
static public IEnumerable< IList>> powerset（T [] currentGroupList）
{
int count = currentGroupList.Length;
字典< long，T> powerToIndex = new Dictionary< long，T>（）;
long mask = 1L; （int i = 0; i< count; i ++）
{
powerToIndex [mask] = currentGroupList [i];
mask<< = 1;
}
字典< long，T> result = new Dictionary< long，T>（）;
yield return result.Values.ToArray（）;
long max = 1L<<计数;
for（long i = 1L; i< max; i ++）
{
long key = i& -一世;
if（result.ContainsKey（key））
result.Remove（key）;
else
result [key] = powerToIndex [key];
yield return result.Values.ToArray（）;
}
}
}
您可以下载所有最快版本我已经测试了 here 。
<我真的认为使用收益回报是使计算大型电力系统成为可能的变化。预先大量分配大量的内存可以显着增加运行时间，并导致算法在早期缺少内存而失败。原创海报应该能够确定他需要多少套电源。控制所有这些都不是一个> 24个元素的选项。
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.
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)
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.
I am unfamiliar with c, so what are my best options for data structures that will allow the c# to access the returned data?
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.
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).
Update 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.
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
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.
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.
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.
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.
这篇关于C数据结构以模拟C＃的List< List< int>？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
