Iterar a través de una matriz de dimensión arbitraria

Question

Usando C#, ¿cómo iterar a través de una matriz multidimensional de dimensiones desconocidas?

Por ejemplo, considere establecer cada elemento de la matriz en un valor especificado, todas las entradas de la matriz deben repetirse. El método debe manejar todos los casos siguientes y completar todas las entradas con el valor 4, independientemente de la dimensión de la matriz pasada.

ClearArray(new int[3], 4); 
ClearArray(new int[3,3], 4); 
ClearArray(new int[3, 3, 3, 3], 4); 

La firma métodos, obviamente, se ve algo como

static void ClearArray(Array a, int val) { ... } 

Yo sé la manera de recorrer uno dimensión:

for (int i=0; i<a.GetLength(dimension); i++) 
{ 
    ... 
} 

Nota: Esta pregunta no es acerca de las matrices 2D , Matrices 3D, ni arrays 4D. Debe manejar cualquier dimensión que indique la propiedad Rank en el objeto Array.

Answer 1

solución más rápida es Buffer.BlockCopy:

static void ClearArray(Array array, int val) 
{ 
    var helper = Enumerable.Repeat(val, Math.Min(array.Length, 1024)).ToArray(); 
    var itemSize = 4; 


    Buffer.BlockCopy(helper, 0, array, 0, helper.Length * itemSize); 
    for (var len = helper.Length; len < array.Length; len *= 2) 
    { 
    Buffer.BlockCopy(array, 0, array, len * itemSize, Math.Min(len, array.Length - len) * itemSize); 
    } 
} 

static int Count(Array array, Func<int, bool> predicate) 
{ 
    var helper = new int[Math.Min(array.Length, 4096)]; 
    var itemSize = 4; 

    var count = 0; 
    for (var offset = 0; offset < array.Length; offset += helper.Length) 
    { 
    var len = Math.Min(helper.Length, array.Length - offset); 
    Buffer.BlockCopy(array, offset * itemSize, helper, 0, len * itemSize); 
    for (var i = 0; i < len; ++i) 
     if (predicate(helper[i])) 
     count++; 
    } 
    return count; 
} 

Estadística:

time: 00:00:00.0449501, method: Buffer.BlockCopy 
time: 00:00:01.4371424, method: Lexicographical order 
time: 00:00:01.3588629, method: Recursed 
time: 00:00:06.2005057, method: Cartesian product with index array reusing 
time: 00:00:08.2433531, method: Cartesian product w/o index array reusing 

Estadística (función Count):

time: 00:00:00.0812866, method: Buffer.BlockCopy 
time: 00:00:02.7617093, method: Lexicographical order 

Código:

Array array = Array.CreateInstance(typeof(int), new[] { 100, 200, 400 }, new[] { -10, -20, 167 }); 
    foreach (var info in new [] 
    { 
     new {Name = "Buffer.BlockCopy", Method = (Action<Array, int>)ClearArray_BufferCopy}, 
     new {Name = "Lexicographical order", Method = (Action<Array, int>)ClearArray_LexicographicalOrder}, 
     new {Name = "Recursed", Method = (Action<Array, int>)ClearArray_Recursed}, 
     new {Name = "Cartesian product with index array reusing", Method = (Action<Array, int>)ClearArray_Cartesian_ReuseArray}, 
     new {Name = "Cartesian product w/o index array reusing", Method = (Action<Array, int>)ClearArray_Cartesian}, 
    } 
    ) 
    { 
    var stopwatch = new Stopwatch(); 
    stopwatch.Start(); 
    var count = 10; 
    for (var i = 0; i < count; ++i) 
     info.Method(array, i); 
    stopwatch.Stop(); 
    Console.WriteLine("time: {0}, method: {1}", TimeSpan.FromTicks(stopwatch.Elapsed.Ticks/count), info.Name); 
    } 

Answer 2

Utilice Array.Rank para determinar el número de dimensiones, luego Array.GetLowerBound (dimensión int) y Array.GetUpperBound (dimensión int) para comprender el rango para cada rango dado.

No se especifica cómo debería funcionar su iterador (por ejemplo, hay semántica en el orden de iteración). Sin embargo, para implementar ClearArray() el orden de iteración no debería importar.

Utilice a.SetValue (valor del objeto, params int [] índices) para establecer el valor especificado para su método ClearArray.

Answer 3

Use Lexicographical order:
El índice es una secuencia de "dígitos". En cada iteración última "dígito" incrementado, mientras que dentro de límites, entonces la próxima "dígito" incrementa, etc

Func<Array, int[]> firstIndex = 
    array => Enumerable.Range(0, array.Rank) 
     .Select(_i => array.GetLowerBound(_i)) 
     .ToArray(); 

Func<Array, int[], int[]> nextIndex = (array, index) => 
    { 
    for (int i = index.Length-1; i >= 0; --i) 
    { 
     index[i]++; 
     if (index[i] <= array.GetUpperBound(i)) 
     return index; 
     index[i] = array.GetLowerBound(i); 
    } 
    return null; 
    }; 

for (var index = firstIndex(array); index != null; index = nextIndex(array, index)) 
{ 
    var v = array.GetValue(index); 
    ... 
    array.SetValue(newValue, index); 
} 

Answer 4

Una solución simple de 2 pasos, sin optimización intentó:

public static void ClearArray(Array a, int val) 
    { 
     int[] indices = new int[a.Rank]; 
     ClearArray(a, 0, indices, val); 
    } 

    private static void ClearArray(Array a, int r, int[] indices, int v) 
    { 
     for (int i = 0; i < a.GetLength(r); i++) 
     { 
      indices[r] = i; 

      if (r + 1 < a.Rank) 
       ClearArray(a, r + 1, indices, v); 
      else 
       a.SetValue(v, indices); 
     } 
    } 

Answer 5

Se puede construir una solución de un montón de partes. El boceto de la solución es: crea un conjunto de secuencias desde cero hasta longitud-1, una secuencia para cada dimensión de la matriz. Luego tome el producto cartesiano de esas secuencias. Eso te da una secuencia de índices. inicio

Vamos con el producto:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    this IEnumerable<IEnumerable<T>> sequences) 
{ 
    IEnumerable<IEnumerable<T>> emptyProduct = 
    new[] { Enumerable.Empty<T>() }; 
    return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) => 
     from accseq in accumulator 
     from item in sequence 
     select accseq.Concat(new[] {item})); 
} 

discuto cómo este código funciona aquí:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

Necesitamos una secuencia de secuencias. ¿Qué secuencias?

var sequences = from dimension in Enumerable.Range(0, array.Rank) 
     select Enumerable.Range(array.GetLowerBound(dimension), array.GetLength(dimension)); 

Así que tienen secuencias como, por ejemplo:

{ 
    { 0, 1, 2 }, 
    { 0, 1, 2, 3 } 
} 

Ahora calcular el producto:

var product = sequences.CartesianProduct(); 

lo que el producto es

{ 
    { 0, 0 }, 
    { 0, 1 }, 
    { 0, 2 }, 
    { 0, 3 }, 
    { 1, 0 }, 
    { 1, 1 }, 
    { 1, 2 }, 
    { 1, 3 }, 
    { 2, 0 }, 
    { 2, 1 }, 
    { 2, 2 }, 
    { 2, 3 } 
} 

y ahora se puede decir

foreach(IEnumerable<int> indices in product) 
    array.SetValue(value, indices.ToArray()); 

¿Tiene todo eso sentido?