¿Estructura de datos de C para imitar la Lista de C # <Lista >?

Estoy buscando refactorizar el método ac # en función ac para intentar ganar algo de velocidad, y luego llamar a la dll c en c # para permitir que mi progtwig use la funcionalidad.

Actualmente el método c # toma una lista de enteros y devuelve una lista de listas de enteros. El método calculó el conjunto de potencias de los enteros, de modo que una entrada de 3 ints produciría la siguiente salida (en esta etapa, los valores de los ints no son importantes, ya que se utilizan como un valor de ponderación interno)

1 2 3 1,2 1,3 2,3 1,2,3 

Donde cada línea representa una lista de enteros. La salida indica el índice (con un desplazamiento de 1) de la primera lista, no el valor. Así que 1,2 indica que el elemento en el índice 0 y 1 es un elemento del conjunto de potencias.

No estoy familiarizado con c, ¿cuáles son mis mejores opciones para las estructuras de datos que permitirán a c # acceder a los datos devueltos?

Gracias por adelantado

Actualizar

Gracias a todos por sus comentarios hasta ahora. Aquí hay un poco de antecedentes de la naturaleza del problema.

El método iterativo para calcular el conjunto de potencias de un conjunto es bastante sencillo. Dos bucles y un poco de manipulación de bits es todo lo que hay que hacer. Simplemente se llama … mucho (de hecho, miles de millones de veces si el tamaño del conjunto es lo suficientemente grande).

Mi opinión sobre el uso de c (c ++ como lo ha señalado la gente) es que ofrece más posibilidades de ajuste de rendimiento. Es posible que un puerto directo no ofrezca ningún aumento, pero abre el camino para que los métodos más involucrados obtengan un poco más de velocidad. Incluso un pequeño aumento por iteración equivaldría a un aumento medible.

Mi idea era portar una versión directa y luego trabajar para boostla. Y luego refactorícelo con el tiempo (con la ayuda de todos aquí en SO).

Actualización 2

Otro punto justo de jalf, no tengo que usar list o equivelent. Si hay una manera mejor, entonces estoy abierto a sugerencias. La única razón para la lista fue que cada conjunto de resultados no es del mismo tamaño.

El código hasta ahora …

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

Como se puede ver, no mucho. ¡Sólo da vueltas y vueltas mucho!

Acepto que la creación y construcción de listas puede que no sea la forma más eficiente, pero necesito alguna forma de proporcionar los resultados de una manera manejable.

Actualización 2

Gracias por todo el trabajo de entrada y aplicación. Solo para aclarar un par de puntos planteados: No necesito que la salida esté en ‘orden natural’, y tampoco estoy interesado en que se devuelva el conjunto vacío.

La implementación de hughdbrown es intuitiva, pero creo que necesitaré almacenar los resultados (o al menos un subconjunto de ellos) en algún momento. Parece que las limitaciones de memoria se aplicarán mucho antes de que el tiempo de ejecución se convierta en un problema real. En parte debido a esto, creo que puedo salir adelante con el uso de bytes en lugar de números enteros, lo que ofrece un mayor almacenamiento potencial.

La pregunta realmente es entonces: ¿hemos alcanzado la velocidad máxima para este cálculo en C #? ¿La opción de código no administrado proporciona más scope? Sé que, en muchos aspectos, la respuesta es inútil, ya que incluso si tenemos tiempo para ejecutar, solo permitiría valores adicionales en el conjunto original.

Esto devuelve un conjunto de un conjunto de poderes a la vez. Se basa en el código de Python aquí . Funciona para grupos de más de 32 elementos. Si necesita menos de 32, puede cambiar largo a int. Es bastante rápido, más rápido que mi algoritmo anterior y más rápido que (mi versión modificada para usar rendimiento) del código de 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(); } } } 

Puedes descargar todas las versiones más rápidas que he probado aquí .

Realmente creo que usar la rentabilidad es el cambio que hace posible calcular grandes grupos de potencias. La asignación de grandes cantidades de memoria por adelantado aumenta considerablemente el tiempo de ejecución y hace que los algoritmos fallen por falta de memoria desde el principio. El póster original debe averiguar cuántos conjuntos de un conjunto de poderes necesita a la vez. Sostener a todos ellos no es realmente una opción con> 24 elementos.

Además, asegúrese de que pasar a C / C ++ sea realmente lo que necesita hacer para comenzar con la velocidad. Instale el método C # original (independiente, ejecutado a través de pruebas unitarias), instrumente el nuevo método C / C ++ (nuevamente, independiente a través de pruebas unitarias) y vea cuál es la diferencia del mundo real.

La razón por la que menciono esto es que me temo que puede ser una victoria pyrhhic: usando el consejo de Smokey Bacon, obtienes tu clase de lista, estás en C ++ “más rápido”, pero todavía hay un costo para llamar a ese DLL: rebotar El tiempo de ejecución con P / Invoke o interoperabilidad COM conlleva un costo de rendimiento bastante importante.

Asegúrese de obtener el “valor de su dinero” de ese salto antes de hacerlo.

Actualización basada en la actualización del OP

Si llama a este bucle repetidamente, debe asegurarse absolutamente de que toda la lógica del bucle esté encapsulada en una sola llamada de interoperabilidad; de lo contrario, la sobrecarga de ordenamiento (como han mencionado otros) definitivamente lo matará.

Creo que, dada la descripción del problema, el problema no es que C # / .NET sea “más lento” que C, sino que es más probable que el código deba optimizarse. Como se mencionó en otro póster aquí, puede usar los punteros en C # para mejorar seriamente el rendimiento en este tipo de bucle, sin la necesidad de una clasificación. Antes de saltar a un complejo mundo de interoperabilidad, me ocuparía de este escenario.

Si desea utilizar C para obtener un aumento de rendimiento, lo más probable es que planee hacerlo mediante el uso de punteros. C # permite el uso de punteros, usando la palabra clave no segura. ¿Has considerado eso?

Además, ¿cómo llamará a este código … se lo llamará a menudo (p. Ej., En un bucle?) Si es así, la reorganización de los datos puede compensar cualquier ganancia de rendimiento.


Seguir

Eche un vistazo al código nativo sin sacrificar el rendimiento de .NET para algunas opciones de interoperabilidad. Hay formas de interoperar sin una pérdida excesiva de rendimiento, pero esos interopses solo pueden ocurrir con los tipos de datos más simples.

Aunque sigo pensando que deberías investigar acelerar tu código usando .NET directo.


Seguimiento 2

Además, puedo sugerir que si tiene la intención de mezclar código nativo y código administrado, cree su biblioteca utilizando c ++ / cli. A continuación se muestra un ejemplo simple. Tenga en cuenta que no soy un chico de c ++ / cli, y este código no hace nada útil … solo pretende mostrar con qué facilidad puede mezclar código nativo y administrado.

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

¿Qué te hace pensar que ganarás velocidad llamando al código C? C no es mágicamente más rápido que C #. Puede ser, por supuesto, pero también puede ser más lento (y con más errores). Especialmente cuando se toma en cuenta el p / invocación de llamadas en el código nativo, está lejos de ser seguro de que este enfoque acelere algo.

En cualquier caso, C no tiene nada como List. Tiene matrices y punteros sin procesar (y podría argumentar que int ** es más o menos equivalente), pero probablemente sea mejor usar C ++, que tiene estructuras de datos equivalentes. En particular, std :: vector. Sin embargo, no hay formas simples de exponer estos datos a C #, ya que se dispersarán de forma bastante aleatoria (cada lista es un puntero a alguna memoria asignada dinámicamente en algún lugar )

Sin embargo, sospecho que la mayor mejora en el rendimiento proviene de la mejora del algoritmo en C #.

Editar:

Puedo ver varias cosas en su algoritmo que parecen subóptimas. Construir una lista de listas no es gratis. Quizás pueda crear una lista única y usar diferentes desplazamientos para representar cada sublista. O tal vez el uso de ‘rendimiento de rendimiento’ e IEnumerable en lugar de construir explícitamente las listas podría ser más rápido.

¿Ha perfilado su código, averiguado dónde se está gastando el tiempo?

También pondré un voto para ajustar su C #, particularmente al ir al código “inseguro” y perder lo que podría ser una gran cantidad de gastos generales de verificación de límites.

Aunque es “inseguro”, no es menos “seguro” que C / C ++, y es mucho más fácil hacerlo bien.

A continuación se muestra un algoritmo de C # que debería ser mucho más rápido (y usar menos memoria) que el algoritmo que publicaste. No utiliza el sencillo truco binario que utiliza, y como resultado, el código es un poco más largo. Tiene unos cuantos más for loops que los suyos, y puede tomar uno o dos pasos con el depurador para asimilarlo por completo. Pero en realidad es un enfoque más simple, una vez que entiendes lo que está haciendo.

Como beneficio adicional, los conjuntos devueltos están en un orden más “natural”. Devolvería los subconjuntos del conjunto {1 2 3} en el mismo orden en que los incluyó en su pregunta. Eso no fue un enfoque, pero es un efecto secundario del algoritmo utilizado.

En mis pruebas, encontré que este algoritmo era aproximadamente 4 veces más rápido que el algoritmo que publicaste para un gran conjunto de 22 elementos (que era tan grande como podía ir en mi máquina sin un excesivo balanceo de discos que distorsionara los resultados). Una carrera tuya duró unos 15,5 segundos, y la mía tomó unos 3,6 segundos.

Para listas más pequeñas, la diferencia es menos pronunciada. Para un conjunto de solo 10 elementos, el tuyo se ejecutó 10,000 veces en aproximadamente 7.8 segundos, y el mío tomó aproximadamente 3.2 segundos. Para conjuntos con 5 o menos elementos, se ejecutan casi al mismo tiempo. Con muchas iteraciones, la tuya corre un poco más rápido.

De todos modos, aquí está el código. Lo siento es tan largo; Traté de asegurarme de que lo comentaba 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> 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; } 

Su lista de resultados no coincide con los resultados que produciría su código. En particular, no se muestra generando el conjunto vacío.

Si estuviera produciendo grupos de energía que pudieran tener unos cuantos miles de millones de subconjuntos, entonces la generación de cada subconjunto por separado en lugar de todos a la vez podría reducir los requisitos de memoria, mejorando la velocidad de su código. Qué tal esto:

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

Entonces su código de cliente se ve así:

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

Incluso incluiré un algoritmo de twitdling de bits con argumentos de plantilla de forma gratuita. Para mayor velocidad, puede envolver el bucle interno powerlist () en un bloque inseguro. No hace mucha diferencia.

En mi máquina, este código es ligeramente más lento que el código del OP hasta que los conjuntos son 16 o más grandes. Sin embargo, todos los tiempos a 16 elementos son menos de 0.15 segundos. Con 23 elementos, se ejecuta en el 64% del tiempo. El algoritmo original no se ejecuta en mi máquina para 24 o más elementos, se queda sin memoria.

Este código tarda 12 segundos en generar la potencia establecida para los números del 1 al 24, omitiendo el tiempo de E / S de la pantalla. Eso es 16 millones en 12 segundos, o aproximadamente 1400K por segundo. Para un billón (que es lo que citó anteriormente), eso sería unos 760 segundos. ¿Cuánto tiempo crees que esto debería tomar?

¿Tiene que ser C, o es C ++ una opción también? Si C ++, solo puede su propio tipo de list desde el STL. De lo contrario, deberá implementar su propia lista: busque listas vinculadas o matrices de tamaño dynamic para obtener sugerencias sobre cómo hacerlo.

Estoy de acuerdo con la opinión de “optimizar .NET primero”. Es lo más indoloro. Me imagino que si escribiera algún código .NET no administrado utilizando punteros de C #, sería idéntico a la ejecución de C, excepto por la sobrecarga de la máquina virtual.

Papi p

Podrías cambiar tu código de Combinación () a esto:

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

Esto reducirá las multiplicaciones y la posibilidad de desbordamiento a un mínimo.