Итерация по массиву произвольной размерности

Question

Используя c #, как выполнить итерацию многомерного массива неизвестно измерений?

Например, рассмотрите возможность установки каждого элемента массива на указанное значение, все записи массива должныповторяться.Метод должен обрабатывать все следующие случаи и заполнять все записи значением 4, независимо от размера переданного массива.

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

Подпись метода, очевидно, выглядит примерно так:

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

Я знаю, как перебрать одно измерение:

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

Примечание : Этот вопрос не о 2D-массивах, 3D-массивах или 4D-массивах.Он должен обрабатывать любое измерение, указанное в свойстве Rank объекта Array.

Answer 1

Использование Лексикографический порядок :
Индекс - это последовательность «цифр». На каждой итерации последняя «цифра» увеличивается, пока она находится в границах, затем увеличивается следующая «цифра» и т. Д.

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 2

Вы можете построить решение из нескольких частей.Схема решения такова: создайте набор последовательностей от нуля до длины-1, по одной последовательности для каждого измерения массива.Затем возьмите декартово произведение этих последовательностей.Это дает вам последовательность индексов.

Давайте начнем с продукта:

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

Я расскажу, как работает этот код:

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

Нам нужна последовательность последовательностей.Какие последовательности?

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

Итак, у нас есть последовательности, например:

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

Теперь вычислим произведение:

var product = sequences.CartesianProduct();

Итак, произведение равно

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

И теперь вы можете сказать

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

Имеет ли это смысл?

Answer 3

Самым быстрым решением является 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;
}

Статистика:

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

Статистика (функция подсчета):

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

Код:

  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 4

Простое двухэтапное решение, без попыток оптимизации:

    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

Используйте Array.Rank, чтобы определить количество измерений, затем Array.GetLowerBound (измерение размера) и Array.GetUpperBound (измерение измерения), чтобы понять диапазон для каждого данного ранга.

Не указано, как вашитератор должен работать (например, есть ли смысл в порядке итерации).Однако для реализации ClearArray () порядок итерации не должен иметь значения.

Используйте a.SetValue (значение объекта, params int [] indexes), чтобы установить значение, указанное для вашего метода ClearArray.