c# - resueltos - metodo de burbuja en lenguaje c
C estructura de datos para imitar la lista de C#<List<int>>? (10)
Estoy buscando refactorizar el método ac # en la función ac en un intento de ganar algo de velocidad, y luego llamar al c dll en c # para permitir que mi programa use la funcionalidad.
Actualmente, el método c # toma una lista de enteros y devuelve una lista de enteros. El método calculó el conjunto de potencia de los enteros, por lo que una entrada de 3 ints produciría la siguiente salida (en esta etapa los valores de los enteros no son importantes ya que se usa 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. Entonces 1,2 indica que el elemento en el índice 0 y 1 es un elemento del conjunto de potencia.
No estoy familiarizado con c, entonces, ¿cuáles son mis mejores opciones para las estructuras de datos que permitirán que c # acceda a los datos devueltos?
Gracias por adelantado
Actualizar
Gracias a todos por sus comentarios hasta ahora. Aquí hay un poco de un trasfondo de la naturaleza del problema.
El método iterativo para calcular el conjunto de potencia de un conjunto es bastante directo. Dos bucles y un poco de manipulación es todo lo que hay realmente. Simplemente se llama ... un montón (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 han señalado las personas) es que da más margen para la optimización del rendimiento. Un puerto directo puede no ofrecer 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 mensurable.
Mi idea era portar una versión directa y luego trabajar para aumentarla. Y luego refactorizarlo 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 mejor manera, entonces estoy abierto a sugerencias. La única razón para la lista era que cada conjunto de resultados no tiene el mismo tamaño.
El código hasta el momento ...
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;
}
Como puede ver, no hay mucho para eso. ¡Simplemente da vueltas y vueltas!
Acepto que la creación y creación de listas puede no ser la manera más eficiente, pero necesito alguna forma de devolver los resultados de una manera manejable.
Actualización 2
Gracias por todo el trabajo de entrada e implementación. Solo para aclarar un par de puntos planteados: no necesito que la salida esté en ''orden natural'', y tampoco estoy tan interesado en que se devuelva el conjunto vacío.
La implementación de hughdbrown es complicada, pero creo que tendré que 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 salirse con la suya usando bytes en lugar de enteros, dando más almacenamiento potencial.
La pregunta realmente es: ¿Hemos alcanzado la velocidad máxima para esta calcualción en C #? ¿La opción de código no administrado proporciona más alcance? Sé que en muchos aspectos la respuesta es inútil, ya que incluso si tuviéramos el tiempo para correr, solo permitiría valores adicionales en el conjunto original.
¿Tiene que ser C, o es C ++ una opción también? Si C ++, puede simplemente su propio tipo de list desde el STL. De lo contrario, tendrá que implementar su propia lista: busque listas vinculadas o matrices de tamaño dinámico para los indicadores sobre cómo hacer esto.
¿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 más caprichoso). Especialmente cuando se tienen en cuenta las llamadas p / invoke en el código nativo, está lejos de ser cierto que este enfoque acelerará cualquier cosa.
En cualquier caso, C no tiene nada como Lista. Tiene matrices y punteros sin procesar (y se podría argumentar que int ** es más o menos equivalente), pero probablemente sea mejor utilizar 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 alguna parte )
Sin embargo, sospecho que la mayor mejora en el rendimiento proviene de mejorar el algoritmo en C #.
Editar:
Puedo ver varias cosas en tu algoritmo que parecen no ser óptimas. La construcción de una lista de listas no es gratuita. Tal vez pueda crear una lista única y usar diferentes compensaciones para representar cada sublista. O tal vez usar ''yield return'' e IEnumerable en lugar de construir listas explícitamente podría ser más rápido.
¿Ha perfilado su código, descubrió dónde se está gastando el tiempo?
Además, asegúrese de pasar a C / C ++ es realmente lo que necesita hacer para la velocidad, para empezar. Instrumenta el método C # original (independiente, ejecutado a través de pruebas unitarias), instrumenta el nuevo método C / C ++ (de nuevo, independiente mediante pruebas unitarias) y observa cuál es la diferencia en el mundo real.
La razón por la que menciono esto es porque me temo que puede ser una victoria pírhica: 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 esa DLL: rebotando del tiempo de ejecución con P / Invoke o interoperabilidad COM tiene un costo de rendimiento bastante sustancial.
Asegúrese de obtener el "dinero que vale" de ese salto antes de hacerlo.
Actualización basada en la actualización del OP
Si está llamando a este bucle repetidamente, debe asegurarse de que la lógica del bucle completo esté encapsulada en una única llamada de interoperabilidad; de lo contrario, la sobrecarga de clasificación (como han mencionado otros aquí) definitivamente lo matará.
Creo, dada la descripción del problema, que 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 otro cartel aquí mencionado, puede usar punteros en C # para aumentar seriamente el rendimiento en este tipo de bucle, sin la necesidad de ordenar. Me fijaría en eso primero, antes de saltar a un complejo mundo de interoperabilidad, para este escenario.
Si está buscando usar C para obtener un aumento en el rendimiento, lo más probable es que esté planeando hacerlo mediante el uso de punteros. C # permite el uso de punteros, utilizando la palabra clave insegura. ¿Lo has considerado?
Además, ¿cómo va a llamar a este código ... se lo llamará a menudo (por ejemplo, en un bucle?) De ser así, ordenar los datos hacia adelante y hacia atrás puede compensar con creces 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 demasiada pérdida de rendimiento, pero esas interoperaciones solo pueden ocurrir con los tipos de datos más simples.
Aunque todavía creo que deberías investigar la aceleración de tu código usando .NET directo.
Seguimiento 2
Además, le sugiero que, si está decidido a mezclar el código nativo y el código administrado, cree su biblioteca con 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 la facilidad con la que puede mezclar el código nativo y el código administrado.
#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;
}
También voy a votar para afinar tu C #, particularmente yendo a un código "inseguro" y perdiendo lo que podría ser una gran cantidad de límites: controlar los gastos generales.
Aunque es "inseguro", no es menos "seguro" que C / C ++, y es mucho más fácil hacerlo bien.
Debajo hay 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 truco binario ordenado que usa tuyo, y como resultado, el código es un poco más largo. Tiene unos cuantos bucles más que los tuyos, y puede tomar uno o dos pasos recorrerlo 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 subconjuntos del conjunto {1 2 3} en el mismo orden en que los incluyó en su pregunta. Ese no era un foco, pero es un efecto secundario del algoritmo utilizado.
En mis pruebas, encontré que este algoritmo es 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 excesiva distorsión del disco sesgando demasiado los resultados). Una carrera tuya tomó aproximadamente 15.5 segundos, y la mía tardó aproximadamente 3.6 segundos.
Para listas más pequeñas, la diferencia es menos pronunciada. Para un conjunto de solo 10 elementos, el tuyo corrió 10.000 veces en aproximadamente 7.8 segundos, y el mío tardó aproximadamente 3.2 segundos. Para conjuntos con 5 o menos elementos, se ejecutan cerca del 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 comenté 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;
}
Estoy de acuerdo con la opinión de "optimizar .NET primero". Es el más indoloro. Imagino que si escribes algún código .NET no administrado usando punteros C #, sería idéntico a la ejecución C, excepto por la sobrecarga de VM.
Esto devuelve un conjunto de un powerset a la vez. Se basa en el código python aquí . Funciona para conjuntos de potencia de más de 32 elementos. Si necesita menos de 32, puede cambiar long 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 devolver el rendimiento) del código de 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();
}
}
}
Puede descargar todas las versiones más rápidas que he probado aquí .
Realmente creo que el uso del retorno de rendimiento es el cambio que hace posible el cálculo de conjuntos de energía grandes. Asignar grandes cantidades de memoria por adelantado aumenta dramáticamente el tiempo de ejecución y hace que los algoritmos fallen por falta de memoria desde el principio. El Póster original debería averiguar cuántos conjuntos de un conjunto de poder necesita a la vez. Sostenerlos a todos no es realmente una opción con> 24 elementos.
P Daddy:
Puedes cambiar tu código de combinación () a este:
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 al mínimo.
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 conjuntos de potencia que podrían tener unos pocos miles de millones de subconjuntos, entonces generar cada subconjunto por separado en lugar de todos a la vez podría reducir sus requisitos de memoria, mejorando la velocidad de su código. Qué tal esto:
static class PowerSet<T>
{
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<IList<T>> 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<int> set in PowerSet<int>.powerset(intList))
{
foreach (int i in set)
Console.Write("{0} ", i);
Console.WriteLine();
}
}
Incluso lanzaré un algoritmo de poco tiempo con argumentos modelados 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 un poco más lento que el código del OP hasta que los conjuntos son 16 o más grandes. Sin embargo, todos los tiempos hasta 16 elementos son menos de 0.15 segundos. En 23 elementos, se ejecuta en el 64% del tiempo. El algoritmo original no se ejecuta en mi máquina durante 24 o más elementos: se queda sin memoria.
Este código tarda 12 segundos en generar la potencia configurada para los números del 1 al 24, omitiendo el tiempo de E / S de la pantalla. Eso es 16 millones de ish en 12 segundos, o aproximadamente 1400K por segundo. Por mil millones (que es lo que citó antes), eso sería aproximadamente 760 segundos. ¿Cuánto tiempo crees que esto debería tomar?