Iterieren durch ein Array beliebiger Dimension

Question

Mit C#, wie durch ein multidimensionales Array von unbekannte Dimensionen durchlaufen?

Wenn Sie beispielsweise jedes Element des Arrays auf einen bestimmten Wert setzen möchten, müssen alle Einträge des Arrays wiederholt werden. Die Methode sollte alle folgenden Fälle behandeln und alle Einträge mit dem Wert 4 füllen, unabhängig von der Dimension des übergebenen Arrays.

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

Die Methoden Signatur sieht offensichtlich so etwas wie

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

Ich weiß, wie durch eine Dimension iterieren:

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

Hinweis: Diese Frage nicht um 2D-Arrays ist , 3D-Arrays oder 4D-Arrays. Es sollte jede Dimension behandeln, die die Rank Eigenschaft auf dem Array Objekt sagt.

Answer 1

schnellste Lösung ist 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 (Zählfunktion):

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

Verwenden Sie Array.Rank, um die Anzahl der Dimensionen zu ermitteln, und anschließend Array.GetLowerBound (int dimension) und Array.GetUpperBound (int dimension), um den Bereich für jeden gegebenen Rang zu verstehen.

Es wird nicht angegeben, wie Ihr Iterator funktionieren soll (z. B. gibt es irgendeine Semantik in der Reihenfolge der Iteration). Um ClearArray() zu implementieren, sollte die Reihenfolge der Iteration jedoch keine Rolle spielen.

Verwenden Sie a.SetValue (Objektwert, Parameter int [] Indizes), um den für Ihre ClearArray-Methode angegebenen Wert festzulegen.

Answer 3

Verwenden Sie Lexicographical order:
Index ist Sequenz von "Ziffern". Bei jeder Iteration letzten "digit" erhöht, während es in Grenzen, dann neben "digit" erhöht, 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

Eine einfache 2-Stufen-Lösung, keine Optimierung versucht:

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

Sie können eine bauen Lösung aus einem Bündel von Teilen. Die Skizze der Lösung lautet: Machen Sie eine Reihe von Sequenzen von Null bis Länge-1, eine Sequenz für jede Dimension des Arrays. Nehmen Sie dann das kartesische Produkt dieser Sequenzen. Das gibt Ihnen eine Reihe von Indizes.

Beginnen wir mit dem Produkt:

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

ich diskutieren, wie dieser Code funktioniert hier:

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

wir eine Folge von Sequenzen benötigen. Welche Sequenzen?

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

So haben wir Sequenzen, wie sie sagen:

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

nun das Produkt berechnen:

var product = sequences.CartesianProduct(); 

So ist das Produkt

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

Und jetzt kann man sagen,

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

Macht das alles Sinn?