c# - 模仿 C# 的 List> 的 C 数据结构？

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

到目前为止的代码...

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

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

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

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

Answer 1

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

我之所以提出这个问题，是因为我担心这可能是一个失败的胜利——使用 Smokey Bacon 的建议，你得到了你的列表类，你在“更快”的 C++ 中，但是调用那个 DLL 仍然有成本: 使用 P/Invoke 或 COM 互操作从运行时跳出会带来相当大的性能成本。

在跳之前，确保你从这次跳跃中“物有所值”。

基于 OP 更新的更新

如果您重复调用此循环，则需要绝对确保将整个循环逻辑封装在单个互操作调用中——否则编码的开销(如其他人所提到的)肯定会让您丧命。

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