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

Question

我希望将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#访问返回数据的数据结构,我最好的选择是什么？

提前致谢

更新

谢谢大家到目前为止的评论.以下是问题本质的背景知识.

用于计算集合的幂集的迭代方法是相当直接的.真正有两个循环和一点点操作.它只是被称为..很多(事实上,如果集合的大小足够大,数十亿次).

我对使用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#中使用指针来严重提高此类循环的性能,而无需编组.在进入复杂的互操作世界之前,我会首先研究一下这个场景.

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

Answer 3

是什么让你觉得通过调用C代码可以获得速度？C并不比C#神奇地快.它当然可以,但它也可以很慢(和更慢).特别是当您将p/invoke调用纳入本机代码时,很难确定这种方法会加速任何事情.

无论如何,C没有像List这样的东西.它有原始数组和指针(你可以说int**或多或少相当),但你可能最好使用C++,它有相同的数据结构.特别是std :: vector.没有简单的方法可以将这些数据暴露给C#,但是因为它几乎是随机分散的(每个列表都是指向某处动态分配的内存的指针)

但是,我怀疑最大的性能提升来自于改进C#中的算法.

编辑:

我可以在你的算法中看到一些似乎不太理想的东西.构建列表列表不是免费的.也许您可以创建单个列表并使用不同的偏移量来表示每个子列表.或者也许使用'yield return'和IEnumerable而不是显式构建列表可能会更快.

您是否已分析过您的代码,找到了花费的时间？

Answer 4

我还要投票来调整你的C#,特别是通过转向'不安全'的代码并丢失可能是很多边界检查开销.

即使它"不安全",它也不会比C/C++更"安全",并且它更容易做对.

Answer 5

这一次返回一组powerset.它是基于Python代码在这里.它适用于超过32个元素的powersets.如果需要少于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();
        }
    }
}

您可以下载我在这里测试的所有最快的版本.

我真的认为使用收益率回报是使计算大型网络成为可能的变化.预先分配大量内存会大大增加运行时间并导致算法在很早的时候因内存不足而失败.原创海报应该弄清楚他一次需要多少套动力.拥有> 24个元素并不是真正的选择.