Iterate through an array of arbitrary dimension

Question

Using c#, how to iterate through an multidimensional array of unknown dimensions?

For example consider setting each element of the array to a specified value, all entries of the array needs to be iterated. The method should handle all the following cases and fill all entries with the value 4, regardless of the dimension of the array passed.

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

The methods signature obviously looks something like

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

I know how to iterate through one dimension:

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

Note: This question is not about 2D arrays, 3D arrays, nor 4D arrays. It should handle whatever dimension the Rank property on the Array object says.

Answer 1

Fastest solution is 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;
}

Statistic:

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

Statistic (Count function):

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

Code:

  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

You can build a solution out of a bunch of parts. The sketch of the solution is: make a bunch of sequences from zero to length-1, one sequence for each dimension of the array. Then take the Cartesian product of those sequences. That gives you a sequence of indexes.

Let's start with the product:

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

I discuss how this code works here:

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

We need a sequence of sequences. What sequences?

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

So we have sequences as, say:

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

Now compute the product:

var product = sequences.CartesianProduct();

So the product is

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

And now you can say

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

Does that all make sense?

Answer 3

Use Lexicographical order:
Index is sequence of "digits". On each iteration last "digit" incremented while it in bounds, then next "digit" incremented, 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

A simple 2-step solution, no optimization attempted:

    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

Use Array.Rank to determine the number of dimensions, then Array.GetLowerBound(int dimension) and Array.GetUpperBound(int dimension) to understand the range for each given rank.

It's not specified how your iterator should work (e.g. are there any semantic to the order of iteration). However, to implement ClearArray() the order of iteration should not matter.

Use a.SetValue(object value, params int[] indices) to set the value specified for your ClearArray method.