Tengo un conjunto de números en forma de { -1, 0, +1 } que tengo que iterar usando dos bucles, al igual que lo haría cuando usa una matriz 2D.

El conjunto completo se convierte en cada combinación de los números anteriores: { -1, -1 } -> { +1, +1 }, que es 9 en total.

Sin embargo, el conjunto { 0, 0 } tengo que omitirlo. Normalmente solo verificaría con una instrucción if, pero usar esto dentro de dos bucles anidados hará que verifique esta condición en cada ejecución.

¿Hay alguna manera eficiente de hacer esto de alguna manera?

ACTUALIZACIÓN: creo que esto merece un poco más de detalle, porque podría haber una solución completamente diferente a este problema de lo que quiero hacer anteriormente.

Básicamente es verificar celdas adyacentes dentro de una matriz. Entonces, { 0, 0 } es la celda que estamos verificando, pero deseo verificar cada celda adyacente, sin incluir la celda principal.

Imagina que tuviéramos una matriz 2D int[,] array = new int[,] { ... }; Si luego accedemos a la matriz en cualquier índice aproximadamente en el medio (no cerca de ningún índice de borde; como la fila inferior / superior o la columna inferior / superior), nuestra vista conceptual de la matriz se vería así:

[-1, -1] [-1, 0] [-1, +1]
[0, -1] [0, 0] [0, +1]
[+1, -1] [+1, 0] [+1, +1]

[0,0] es nuestro elemento actual. Podemos acceder a cada elemento / celda adyacente utilizando los números anteriores para [fila, columna].

Un bucle típico para hacer esto se vería así:

for (int i = row-1; i <= row+1; ++i) {
    for (int j = col-1; j <= col+1; ++j) {
        if (i == row && j == col) continue;
            ...
    }
}

¿Podemos evitar la declaración if?

0
user3407764 19 ene. 2018 a las 19:37

3 respuestas

La mejor respuesta

Después de su edición, parece que no necesita bucles y el resultado deseado tiene 8 elementos bien definidos.

Entonces, simplemente podría crear un pequeño método que le proporcione todas las celdas adyacentes a su celda principal:

Point[] GetAdjacentPoints(Point p)
{
    return new[]{
        new Point { X = p.X - 1, Y = p.Y - 1 },
        new Point { X = p.X,     Y = p.Y - 1 },
        new Point { X = p.X + 1, Y = p.Y - 1 },
        new Point { X = p.X - 1, Y = p.Y },
        // leave out p itself
        new Point { X = p.X + 1, Y = p.Y },
        new Point { X = p.X - 1, Y = p.Y + 1},
        new Point { X = p.X,     Y = p.Y + 1},
        new Point { X = p.X + 1, Y = p.Y + 1}
    };
}

(Supongo que Point es algo así como struct Point {public int X {get;set;} public int Y {get;set;}} o cualquier otro tipo para contener dos enteros).

Puedes usar este método así:

foreach(Point adjacent in GetAdjacentPoints(new Point {X = 0, Y = 0})
    Console.WriteLine($"X: {adjacent.X} Y: {adjacent.Y}");

Salida:

X: -1 Y: -1
X: 0 Y: -1
X: 1 Y: -1
X: -1 Y: 0
X: 1 Y: 0
X: -1 Y: 1
X: 0 Y: 1
X: 1 Y: 1
1
René Vogt 19 ene. 2018 a las 17:17

Simplemente calcule cada par y luego elimine el par que desea excluir de su conjunto final. [bien implementado] Los conjuntos están diseñados específicamente para una eliminación eficiente (más eficiente que lineal de todos modos, O (1) para conjuntos basados en hash, O (log (n)) para conjuntos basados en árboles), por lo que será más rápido que verificar cada valor en el conjunto, que es lo que harías al tener el cheque en tu ciclo.

1
Servy 19 ene. 2018 a las 16:59

Le sugiero que lo mida primero y vea si esto realmente es un problema, porque dependiendo del tipo de colección que esté utilizando, la operación Add puede ser más costosa que la declaración if (en mi caso a continuación, consiste en crear una nueva lista y luego agregar esa lista a otra lista).

Por ejemplo, usando un List<int> para mantener el conjunto original y un List<List<int>> para contener las combinaciones, encuentro que usar la declaración if es más rápido que no usarlo (y si no lo usamos, entonces aún necesitamos iterar sobre los pares para encontrar los que queremos eliminar).

A continuación se muestra la prueba que ejecuté, usando bucles con el if y sin el if, con 2001 elementos en el conjunto (de -1000 a 1000), que crea un total de 4004000 conjuntos. Ejecuté las pruebas en un bucle 100 veces y mostré el tiempo promedio en un intento de obtener el resultado más preciso:

private static void Main()
{
    var items = Enumerable.Range(-1000, 2001).ToList();
    var combinations = new List<List<int>>();
    var withIfCount = new List<long>();
    var withoutIfCount = new List<long>();
    var sw = new Stopwatch();

    // Both test are run 100 times
    for (int count = 0; count < 100; count++)
    {
        sw.Restart();
        for (int outer = 0; outer < items.Count; outer++)
        {
            for (int inner = 0; inner < items.Count; inner++)
            {
                if (outer == 0 && inner == 0) continue;
                combinations.Add(new List<int> {outer, inner});
            }
        }
        sw.Stop();
        withIfCount.Add(sw.ElapsedMilliseconds);
        combinations.Clear();

        sw.Restart();
        for (int outer = 0; outer < items.Count; outer++)
        {
            for (int inner = 0; inner < items.Count; inner++)
            {
                combinations.Add(new List<int> {outer, inner});
            }
        }
        sw.Stop();
        withoutIfCount.Add(sw.ElapsedMilliseconds);
        combinations.Clear();
    }

    // Display averages
    Console.WriteLine("Average time with 'if': " + withIfCount.Average());
    Console.WriteLine("Average time without 'if': " + withoutIfCount.Average());

    Console.WriteLine("\nDone!\nPress any key to exit...");
    Console.ReadKey();
}

Salida

enter image description here

1
Rufus L 19 ene. 2018 a las 17:32