c# - ¿Alternativa más rápida a los bucles anidados?

combinations

Question

Necesito crear una lista de combinaciones de números. Los números son bastante pequeños, así que puedo usar byte lugar de int . Sin embargo, requiere muchos bucles anidados para obtener todas las combinaciones posibles. Me pregunto si hay una manera más eficiente de hacer lo que busco. El código hasta ahora es:

var data = new List<byte[]>();
for (byte a = 0; a < 2; a++)
for (byte b = 0; b < 3; b++)
for (byte c = 0; c < 4; c++)
for (byte d = 0; d < 3; d++)
for (byte e = 0; e < 4; e++)
for (byte f = 0; f < 3; f++)
for (byte g = 0; g < 3; g++)
for (byte h = 0; h < 4; h++)
for (byte i = 0; i < 2; i++)
for (byte j = 0; j < 4; j++)
for (byte k = 0; k < 4; k++)
for (byte l = 0; l < 3; l++)
for (byte m = 0; m < 4; m++)
{
data.Add(new [] {a, b, c, d, e, f, g, h, i, j, k, l, m});
}

Estaba considerando usar algo como un BitArray pero no estoy seguro de cómo podría incorporarlo.

Cualquier recomendación sería muy apreciada. Alternativamente, ¿tal vez esta es la forma más rápida de hacer lo que quiero?

EDITAR Par de puntos rápidos (y disculpas no puse estos en la publicación original):

• Los números y el orden de ellos (2, 3, 4, 3, 4, 3, 3, etc.) son muy importantes, por lo que usar una solución como Generar permutaciones usando LINQ no ayudará porque los máximos en cada ''columna'' son diferente
• No soy matemático, así que me disculpo si no estoy usando los términos técnicos como ''permutaciones'' y ''combinaciones'' correctamente :)
• Necesito completar todas estas combinaciones a la vez, no puedo simplemente tomar una u otra en función de un índice
• Usar byte es más rápido que usar int , lo garantizo . También es mucho mejor en el uso de la memoria tener 67m + matrices de bytes en lugar de ints
• Mi objetivo final aquí es buscar una alternativa más rápida a los bucles anidados.
• Pensé en usar la programación paralela, pero debido a la naturaleza iterativa de lo que estoy tratando de lograr, no pude encontrar una manera de hacerlo con éxito (incluso con ConcurrentBag ), sin embargo, estoy feliz de que me demuestren que estoy equivocado :)

CONCLUSIÓN

Caramiriel ha proporcionado una buena micro-optimización que reduce un poco los bucles, por lo que he marcado esa respuesta como correcta. Eric también mencionó que es más rápido preasignar la Lista. Pero, en esta etapa, parece que los bucles anidados son, de hecho, la forma más rápida de hacerlo (¡deprimente, lo sé!).

Si desea probar exactamente lo que estaba tratando de comparar con StopWatch , vaya con 13 bucles contando hasta 4 en cada bucle, lo que hace aproximadamente 67m + líneas en la lista. En mi máquina (i5-3320M 2.6GHz) se necesitan aproximadamente 2.2 segundos para hacer la versión optimizada.

Answer 1

¿Necesita que el resultado sea una matriz de matrices? Con la configuración actual, la longitud de las matrices internas es fija y podría reemplazarse por estructuras. Esto permitiría que todo se reservara como un bloque continuo de memoria y proporciona un acceso más fácil a los elementos (no estoy seguro de cómo usarlo más adelante).

El siguiente enfoque es mucho más rápido (41 ms frente a 1071 ms para el original en mi caja):

struct element {
public byte a;
public byte b;
public byte c;
public byte d;
public byte e;
public byte f;
public byte g;
public byte h;
public byte i;
public byte j;
public byte k;
public byte l;
public byte m;
}
element[] WithStruct() {
var t = new element[3981312];
int z = 0;
for (byte a = 0; a < 2; a++)
for (byte b = 0; b < 3; b++)
for (byte c = 0; c < 4; c++)
for (byte d = 0; d < 3; d++)
for (byte e = 0; e < 4; e++)
for (byte f = 0; f < 3; f++)
for (byte g = 0; g < 3; g++)
for (byte h = 0; h < 4; h++)
for (byte i = 0; i < 2; i++)
for (byte j = 0; j < 4; j++)
for (byte k = 0; k < 4; k++)
for (byte l = 0; l < 3; l++)
for (byte m = 0; m < 4; m++)
{
t[z].a = a;
t[z].b = b;
t[z].c = c;
t[z].d = d;
t[z].e = e;
t[z].f = f;
t[z].g = g;
t[z].h = h;
t[z].i = i;
t[z].j = j;
t[z].k = k;
t[z].l = l;
t[z].m = m;
z++;
}
return t;
}

Answer 2

¿Qué pasa con el uso de Parallel.For() para ejecutarlo? (Optimización de estructuras felicitaciones a @Caramiriel ). Modifiqué ligeramente los valores (a es 5 en lugar de 2), así que tengo más confianza en los resultados.

 var data = new ConcurrentStack<List<Bytes>>();
var sw = new Stopwatch();
sw.Start();
Parallel.For(0, 5, () => new List<Bytes>(3*4*3*4*3*3*4*2*4*4*3*4),
(a, loop, localList) => {
var bytes = new Bytes();
bytes.A = (byte) a;
for (byte b = 0; b < 3; b++) {
bytes.B = b;
for (byte c = 0; c < 4; c++) {
bytes.C = c;
for (byte d = 0; d < 3; d++) {
bytes.D = d;
for (byte e = 0; e < 4; e++) {
bytes.E = e;
for (byte f = 0; f < 3; f++) {
bytes.F = f;
for (byte g = 0; g < 3; g++) {
bytes.G = g;
for (byte h = 0; h < 4; h++) {
bytes.H = h;
for (byte i = 0; i < 2; i++) {
bytes.I = i;
for (byte j = 0; j < 4; j++) {
bytes.J = j;
for (byte k = 0; k < 4; k++) {
bytes.K = k;
for (byte l = 0; l < 3; l++) {
bytes.L = l;
for (byte m = 0; m < 4; m++) {
bytes.M = m;
localList.Add(bytes);
}
}
}
}
}
}
}
}
}
}
}
}
return localList;
}, x => {
data.Push(x);
});
var joinedData = _join(data);

_join() es un método privado, definido como:

private static IList<Bytes> _join(IEnumerable<IList<Bytes>> data) {
var value = new List<Bytes>();
foreach (var d in data) {
value.AddRange(d);
}
return value;
}

En mi sistema, esta versión se ejecuta aproximadamente 6 veces más rápido (1.718 segundos frente a 0.266 segundos).

Answer 3

Algunos de sus números caben completamente en un número entero de bits, por lo que puede "empaquetarlos" con el número de nivel superior:

for (byte lm = 0; lm < 12; lm++)
{
...
t[z].l = (lm&12)>>2;
t[z].m = lm&3;
...
}

Por supuesto, esto hace que el código sea menos legible, pero guardó un bucle. Esto se puede hacer cada vez que uno de los números es una potencia de dos, que es siete veces en su caso.

Answer 4

Aquí hay otra solución. Fuera de VS, se ejecuta tan rápido como 437.5 ms, que es un 26% más rápido que el código original (593.7 en mi computadora):

static List<byte[]> Combinations(byte[] maxs)
{
int length = maxs.Length;
int count = 1; // 3981312;
Array.ForEach(maxs, m => count *= m);
byte[][] data = new byte[count][];
byte[] counters = new byte[length];
for (int r = 0; r < count; r++)
{
byte[] row = new byte[length];
for (int c = 0; c < length; c++)
row[c] = counters[c];
data[r] = row;
for (int i = length - 1; i >= 0; i--)
{
counters[i]++;
if (counters[i] == maxs[i])
counters[i] = 0;
else
break;
}
}
return data.ToList();
}

Answer 5

Aquí hay una forma diferente que solo necesita 2 bucles. La idea es aumentar el primer elemento y, si ese número se supera, aumentar el siguiente.

En lugar de mostrar los datos, puede usar currentValues.Clone y agregar esa versión clonada a su lista. Para mí esto corrió más rápido que tu versión.

byte[] maxValues = {2, 3, 4};
byte[] currentValues = {0, 0, 0};
do {
Console.WriteLine("{0}, {1}, {2}", currentValues[0], currentValues[1], currentValues[2]);
currentValues[0] += 1;
for (int i = 0; i <= maxValues.Count - 2; i++) {
if (currentValues[i] < maxValues[i]) {
break;
}
currentValues[i] = 0;
currentValues[i + 1] += 1;
}
// Stop the whole thing if the last number is over
// } while (currentValues[currentValues.Length-1] < maxValues[maxValues.Length-1]);
} while (currentValues.Last() < maxValues.Last());

• Espero que este código funcione, lo convertí de vb

Answer 6

En mi máquina, esto genera las combinaciones en 222 ms frente a 760 ms (el 13 para bucles):

private static byte[,] GenerateCombinations(byte[] maxNumberPerLevel)
{
var levels = maxNumberPerLevel.Length;
var periodsPerLevel = new int[levels];
var totalItems = 1;
for (var i = 0; i < levels; i++)
{
periodsPerLevel[i] = totalItems;
totalItems *= maxNumberPerLevel[i];
}
var results = new byte[totalItems, levels];
Parallel.For(0, levels, level =>
{
var periodPerLevel = periodsPerLevel[level];
var maxPerLevel = maxNumberPerLevel[level];
for (var i = 0; i < totalItems; i++)
results[i, level] = (byte)(i / periodPerLevel % maxPerLevel);
});
return results;
}

Answer 7

La lista tiene una matriz interna donde almacena sus valores, con una longitud fija. Cuando llame a List.Add, verifica si hay suficiente espacio. Cuando no puede agregar el nuevo elemento, creará una nueva matriz de un tamaño mayor, copie todos los elementos anteriores y luego agregue uno nuevo. Esto lleva bastantes ciclos.

Como ya conoce el número de elementos, puede crear la lista del tamaño correcto, que ya debería ser mucho más rápido.

Además, no estoy seguro de cómo acceder a los valores, pero podría crear este elemento y guardar la imagen en el código (cargarlo desde el disco probablemente será más lento de lo que está haciendo; ahora. ¿Cuántas veces lee / escribe en esto? ¿cosa?

Answer 8

Lo que está haciendo es contar (con radix variable, pero aún contando).

Dado que está utilizando C #, supongo que no quiere jugar con un diseño de memoria útil y estructuras de datos que le permitan optimizar realmente su código.

Así que aquí estoy publicando algo diferente, que puede no ser adecuado para su caso, pero vale la pena señalar: en caso de que realmente acceda a la lista de manera dispersa, aquí hay una clase que le permite calcular el elemento i-ésimo en tiempo lineal (en lugar de que exponencial como las otras respuestas)

class Counter
{
public int[] Radices;
public int[] this[int n]
{
get
{
int[] v = new int[Radices.Length];
int i = Radices.Length - 1;
while (n != 0 && i >= 0)
{
//Hope C# has an IL-opcode for div-and-reminder like x86 do
v[i] = n % Radices[i];
n /= Radices[i--];
}
return v;
}
}
}

Puedes usar esta clase de esta manera

Counter c = new Counter();
c.Radices = new int[] { 2,3,4,3,4,3,3,4,2,4,4,3,4};

ahora c[i] es lo mismo que su lista, llámelo l , l[i] .

Como puede ver, puede evitar fácilmente todos esos bucles :) incluso cuando precalcula toda la lista en su totalidad, ya que simplemente puede implementar un contador Carry-Ripple.

Los contadores son un tema muy estudiado, le recomiendo que busque literatura si lo desea.

Answer 9

Puede usar las propiedades de una estructura y asignar la estructura de antemano. Corté algunos niveles en la muestra a continuación, pero estoy seguro de que podrás descubrir los detalles. Se ejecuta entre 5 y 6 veces más rápido que el original (modo de liberación).

El bloque:

struct ByteBlock
{
public byte A;
public byte B;
public byte C;
public byte D;
public byte E;
}

El lazo:

var data = new ByteBlock[2*3*4*3*4];
var counter = 0;
var bytes = new ByteBlock();
for (byte a = 0; a < 2; a++)
{
bytes.A = a;
for (byte b = 0; b < 3; b++)
{
bytes.B = b;
for (byte c = 0; c < 4; c++)
{
bytes.C = c;
for (byte d = 0; d < 3; d++)
{
bytes.D = d;
for (byte e = 0; e < 4; e++)
{
bytes.E = e;
data[counter++] = bytes;
}
}
}
}
}

Es más rápido porque no asigna una nueva lista cada vez que la agrega a la lista. Además, dado que está creando esta lista, necesita una referencia a cualquier otro valor (a, b, c, d, e). Puede suponer que cada valor solo se modifica una vez dentro del bucle, por lo que podemos optimizarlo para hacerlo (localidad de datos).

Lea también los comentarios para los efectos secundarios.

Editó la respuesta para usar una T[] lugar de una List<T> .

Answer 10

Todos sus números son constantes de tiempo de compilación.

¿Qué pasa con desenrollar todos los bucles en una lista (usando su programa para escribir código):

data.Add(new [] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
data.Add(new [] {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
etc.

Eso al menos debería eliminar la sobrecarga de los bucles for (si hay alguno).

No estoy demasiado familiarizado con C #, pero parece que hay algunos medios para serializar objetos. ¿Qué sucede si solo generó esa Lista y la serializó de alguna forma? Sin embargo, no estoy seguro de si la deserialización es más rápida que crear la Lista y agregar los elementos.

Answer 11

Método 1

Una forma de hacerlo más rápido es especificar la capacidad si planea seguir usando List<byte[]> , de esta manera.

var data = new List<byte[]>(2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4);

Método 2

Además, puede usar System.Array directamente para obtener un acceso más rápido. Recomiendo este enfoque si su pregunta insiste en que cada elemento esté físicamente poblado en la memoria, por adelantado.

var data = new byte[2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4][];
int counter = 0;
for (byte a = 0; a < 2; a++)
for (byte b = 0; b < 3; b++)
for (byte c = 0; c < 4; c++)
for (byte d = 0; d < 3; d++)
for (byte e = 0; e < 4; e++)
for (byte f = 0; f < 3; f++)
for (byte g = 0; g < 3; g++)
for (byte h = 0; h < 4; h++)
for (byte i = 0; i < 2; i++)
for (byte j = 0; j < 4; j++)
for (byte k = 0; k < 4; k++)
for (byte l = 0; l < 3; l++)
for (byte m = 0; m < 4; m++)
data[counter++] = new[] { a, b, c, d, e, f, g, h, i, j, k, l, m };

Esto tarda 596 ms en completarse en mi computadora, que es aproximadamente un 10,4% más rápido que el código en cuestión (que tarda 658 ms).

Método 3

Alternativamente, puede usar la siguiente técnica para una inicialización de bajo costo que se adapte al acceso de manera dispersa. Esto es especialmente favorable cuando solo se necesitan algunos elementos y determinarlos por adelantado se considera innecesario. Además, técnicas como estas pueden convertirse en la única opción viable cuando se trabaja con elementos más vastos cuando la memoria se agota.

En esta implementación, cada elemento se deja determinar perezosamente, sobre la marcha, al acceder. Naturalmente, esto tiene un costo de CPU adicional que se incurre durante el acceso.

class HypotheticalBytes
{
private readonly int _c1, _c2, _c3, _c4, _c5, _c6, _c7, _c8, _c9, _c10, _c11, _c12;
private readonly int _t0, _t1, _t2, _t3, _t4, _t5, _t6, _t7, _t8, _t9, _t10, _t11;
public int Count
{
get { return _t0; }
}
public HypotheticalBytes(
int c0, int c1, int c2, int c3, int c4, int c5, int c6, int c7, int c8, int c9, int c10, int c11, int c12)
{
_c1 = c1;
_c2 = c2;
_c3 = c3;
_c4 = c4;
_c5 = c5;
_c6 = c6;
_c7 = c7;
_c8 = c8;
_c9 = c9;
_c10 = c10;
_c11 = c11;
_c12 = c12;
_t11 = _c12 * c11;
_t10 = _t11 * c10;
_t9 = _t10 * c9;
_t8 = _t9 * c8;
_t7 = _t8 * c7;
_t6 = _t7 * c6;
_t5 = _t6 * c5;
_t4 = _t5 * c4;
_t3 = _t4 * c3;
_t2 = _t3 * c2;
_t1 = _t2 * c1;
_t0 = _t1 * c0;
}
public byte[] this[int index]
{
get
{
return new[]
{
(byte)(index / _t1),
(byte)((index / _t2) % _c1),
(byte)((index / _t3) % _c2),
(byte)((index / _t4) % _c3),
(byte)((index / _t5) % _c4),
(byte)((index / _t6) % _c5),
(byte)((index / _t7) % _c6),
(byte)((index / _t8) % _c7),
(byte)((index / _t9) % _c8),
(byte)((index / _t10) % _c9),
(byte)((index / _t11) % _c10),
(byte)((index / _c12) % _c11),
(byte)(index % _c12)
};
}
}
}

Esto tarda 897 ms en completarse en mi computadora (también crear y agregar a una Array como en el Método 2 ), que es aproximadamente un 36,3% más lento que el código en cuestión (que toma 658 ms).

Answer 12

var numbers = new[] { 2, 3, 4, 3, 4, 3, 3, 4, 2, 4, 4, 3, 4 };
var result = (numbers.Select(i => Enumerable.Range(0, i))).CartesianProduct();

Usando el método de extensión en http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
// base case:
IEnumerable<IEnumerable<T>> result =
new[] { Enumerable.Empty<T>() };
foreach (var sequence in sequences)
{
// don''t close over the loop variable (fixed in C# 5 BTW)
var s = sequence;
// recursive case: use SelectMany to build
// the new product out of the old one
result =
from seq in result
from item in s
select seq.Concat(new[] { item });
}
return result;
}