C structure de données pour imiter de C#List<List<int>>?

Aussi, assurez-vous que le passage à la C/C++ est vraiment ce que vous devez faire pour la vitesse, pour commencer. Instrument de l'original de la méthode C# (autonome, exécutée par le biais de tests unitaires), instrument de la nouvelle C/C++ méthode (encore une fois, autonome via des tests unitaires) et de voir ce que le monde réel différence.

La raison pour laquelle je aborder cette question, c'est que je crains qu'il ne peut être un pyrhhic victoire -- à l'aide de Smokey Bacon conseils, vous obtenez votre liste de classe, vous êtes dans le "plus rapide" C++, mais il y a toujours un coût pour l'appelant que la DLL: Rebondir hors de la durée de P/Invoke ou COM interop porte une somme assez importante sur les performances.

Être sûr que vous êtes l'obtention de votre "argent" de ce saut avant de le faire.

Mise à jour basé sur l'OP de la mise à Jour

Si vous êtes à l'appel de cette boucle, vous devez absolument vous assurer que la totalité de la boucle logique est encapsulé dans un seul appel d'interopérabilité -- dans le cas contraire les frais généraux de triage (comme d'autres ici l'ont mentionné) va certainement vous tuer.

Je pense que, compte tenu de la description du problème, que le problème n'est pas que C#/.NET est "plus lent" que C, mais il est plus probable que le code doit être optimisé. Comme une autre affiche ici mentionnés, vous pouvez utiliser les pointeurs en C# sérieusement d'augmenter les performances dans ce genre de boucle, sans la nécessité pour la sérialisation. Je regarde pour la première, avant de sauter dans un complexe interop monde, pour ce scénario.

Ce qui vous fait penser que vous allez gagner de la vitesse en appelant le code C? C n'est pas comme par magie plus rapide que le C#. Il peut être, bien sûr, mais il peut aussi facilement être plus lent (et buggier). Surtout quand vous facteur dans le p/invoke appels en code natif, il est loin d'être certain que cette approche permettra d'accélérer quoi que ce soit.

En tout cas, C de ne pas avoir quelque chose comme la Liste. Il a cru les tableaux et les pointeurs (et on pourrait dire que int** est plus ou moins l'équivalent), mais vous êtes probablement mieux d'utiliser C++, qui n'ont d'équivalent structures de données. En particulier, std::vector.
Il n'y a pas de moyens simples pour exposer ces données, C#, cependant, car il sera dispersé assez bien au hasard (chaque liste est un pointeur vers certains de mémoire allouée dynamiquement quelque part)

Je soupçonne cependant, la plus grande amélioration de la performance provient de l'amélioration de l'algorithme en C#.

Edit:

Je peux voir plusieurs choses dans votre algorithme qui semblent fonctionner de manière optimale. La construction d'une liste de listes n'est pas gratuit. Peut-être vous pouvez créer une liste unique et l'utilisation des positions différentes pour représenter chaque sous-liste. Ou peut-être à l'aide du rendement de retour " et IEnumerable au lieu de construire explicitement des listes pourrait être plus rapide.

Avez-vous profilé votre code, où le temps est dépensé?

Ci-dessous est un C# algorithme qui devrait être beaucoup plus rapide (et d'utiliser moins de mémoire) que l'algorithme que vous avez posté. Il n'utilise pas le soigné binaire astuce vôtre utilise, et comme un résultat, le code est un bon peu plus longtemps. Il a un peu plus de for boucles que la vôtre, et qui peut prendre une heure ou deux de marcher à travers elle avec le débogueur entièrement grok il. Mais c'est en fait une approche la plus simple, une fois que vous comprenez ce qu'il fait.

Comme un bonus, les jeux sont plus "naturelles" de l'ordre. Il serait de retour des sous-ensembles de l'ensemble {1 2 3} dans le même ordre que vous avez indiquée dans votre question. Ce n'était pas un accent, mais est un effet secondaire de l'algorithme utilisé.

Dans mes tests, j'ai trouvé cet algorithme soit environ 4 fois plus rapide que l'algorithme que vous avez posté pour un grand jeu de 22 articles (qui était aussi grand que je pouvais aller sur ma machine sans trop de disque-volée de biaiser les résultats trop). Un run de la vôtre a pris environ 15,5 secondes, et le mien a pris environ 3,6 secondes.

Pour les petites listes, la différence est moins prononcée. Pour un ensemble de seulement 10 points, le vôtre a couru 10 000 fois environ 7,8 secondes, et le mien a pris environ 3,2 secondes. Pour les ensembles avec 5 ou moins d'éléments, ils ont a peu près le même temps. Avec un nombre d'itérations, la vôtre tourne un peu plus vite.

De toute façon, voici le code. Désolé, c'est tellement long, j'ai essayé de m'assurer que je commente, c'est bien.

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

- T-il C ou C++ une option trop? Si C++, vous pouvez seulement de sa propre list type de la STL. Sinon, vous aurez à mettre en place votre propre liste - rechercher des listes chaînées ou dynamiquement la taille des tableaux de pointeurs sur la façon de le faire.

P Daddy:

Vous pouviez changer de Combinaison() code ce:

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

Cela permettra de réduire la multiplication et la chance de débordement à un minimum.