Simulate an array with a struct in C#?

Folks,

Please can anybody imagine "a nice way" of defining a struct in C# that behaves like an array (an int[,] in my case) except that (like all structs) a copy of the struct is passed to the any/all called methods.

Below is my ugly first attempt (a struct that simulates a simple int[], not a matrix yet) with a little test harness to make it do something. I'm thinking I'd then have a struct Matrix of Row's, which would follow a similar pattern. But it's just so verbose. There's got to be better way!

Any ideas, please?

TEST HARNESS

using System;

struct Row {
  public const int COLS = 16;

  public int _0;
  public int _1;
  public int _2;
  public int _3;
  public int _4;
  public int _5;
  public int _6;
  public int _7;
  public int _8;
  public int _9;
  public int _10;
  public int _11;
  public int _12;
  public int _13;
  public int _14;
  public int _15;

  public int this[int index] { 
    get { 
      switch ( index ) {
        case 0: return _0;
        case 1: return _1;
        case 2: return _2;
        case 3: return _3;
        case 4: return _4;
        case 5: return _5;
        case 6: return _6;
        case 7: return _7;
        case 8: return _8;
        case 9: return _9;
        case 10: return _10;
        case 11: return _11;
        case 12: return _12;
        case 13: return _13;
        case 14: return _14;
        case 15: return _15;
      }
      throw new IndexOutOfRangeException("Index="+index+" is not between 0 and 15");
    } 
    set { 
      switch ( index ) {
        case 0: _0 = value; break;
        case 1: _1 = value; break;
        case 2: _2 = value; break;
        case 3: _3 = value; break;
        case 4: _4 = value; break;
        case 5: _5 = value; break;
        case 6: _6 = value; break;
        case 7: _7 = value; break;
        case 8: _8 = value; break;
        case 9: _9 = value; break;
        case 10: _10 = value; break;
        case 11: _11 = value; break;
        case 12: _12 = value; break;
        case 13: _13 = value; break;
        case 14: _14 = value; break;
        case 15: _15 = value; break;
      }
    }
  }

  public override string ToString() {
    return String.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}{11}{12}{13}{14}{15}"
                         ,_0,_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,_11,_12,_13,_14,_15);
  }
}

class TestClass
{
  public static void ProcessRow(Row row, int index) {
    if (index == Row.COLS) return;
    row[index] = 1;
    Console.WriteLine("{0,2} {1}", index, row);
    ProcessRow(row, index+1);
    Console.WriteLine("{0,2} {1}", index, row);
  }

  public static void Main() {
    var row = new Row();
    ProcessRow(row, 0);
  }
}

OUTPUT:

 0 1000000000000000
 1 1100000000000000
 2 1110000000000000
 3 1111000000000000
 4 1111100000000000
 5 1111110000000000
 6 1111111000000000
 7 1111111100000000
 8 1111111110000000
 9 1111111111000000
10 1111111111100000
11 1111111111110000
12 1111111111111000
13 1111111111111100
14 1111111111111110
15 1111111111111111
15 1111111111111111
14 1111111111111110
13 1111111111111100
12 1111111111111000
11 1111111111110000
10 1111111111100000
 9 1111111111000000
 8 1111111110000000
 7 1111111100000000
 6 1111111000000000
 5 1111110000000000
 4 1111100000000000
 3 1111000000000000
 2 1110000000000000
 1 1100000000000000
 0 1000000000000000

WHY BOTHER?

This test verifies that:

a COPY of the Row struct is passed to ProcessRow, leaving the local Row unchanged.
16 calls with a struct of 16 ints doesn't pop the call-stack.

If you're interested... My real problem is I'm currently passing an int[16,16] "map" down a recursive call-tree which processes each "daily move" in Programming Challenge 62 - Bendorf Weed Invasion... at the moment I'm doing an Array.Copy (a couple actually) for each and every move evaluated, and there are about 1.3 quintillion combinations of 10 valid moves to consider, so (funnily enough) it's way too slow, at abour 33.5 hours. I thought that passing a struct instead of an array-reference might speed things up significantly, but I still suspect I'll need a total different approach (i.e. complete rethink of my algorithm) to get close to the "desired" 100 seconds. What I need to be able to do is "try stuff quickly", so I thought I'd find some efficiencies first... I now know exactly how the guys felt in the punched-tape era. Waiting a day a half for your output totally sucks!

EDIT: To include my answer, which is based on the accepted answer by AbdElRaheim.

It uses a "flat" fixed array of ints to simulate a doubly-subscripted array of ints.

All it does is recurse ProcessDay 10 times, passing the map and the day index. On each "day" it just sets a random cell to day, and prints-out the map twice: first on the way down the callstack, and again on the way back up again... so that you can, if you wish, verify that each invocation of ProcessDay has its own copy of the map.

I'm doing this two different ways: with the Matrix struct, and with a standard int[,] ... the suprise (for me at least) is that the struct is slower... Sigh!

using System;
using System.Runtime.InteropServices;
using System.Text;
using System.IO;
using System.Diagnostics;

[StructLayout(LayoutKind.Sequential, Size=64)]
unsafe struct Matrix
{
  public const int ROWS = 16;
  public const int COLS = 16;

  private fixed int Cells[ROWS*COLS];

  public int this[int row, int col] {
    get { 
      fixed ( int* addressOfCells = Cells)
        return *(addressOfCells+row*16+col); 
    }
    set { 
      fixed ( int* addressOfCells = Cells)
        *(addressOfCells+row*16+col) = value; 
    }
  }

  public override string ToString() {
    var sb = new StringBuilder(COLS+2*ROWS);
    for ( int row=0; row<ROWS; ++row) {
      for ( int col=0; col<COLS; ++col) 
        sb.Append(ToChar(this[row,col])); 
      sb.Append(Environment.NewLine);
    }
    return sb.ToString();
  }

  private char ToChar(int cellValue) {
    return cellValue==0 ? '.' : (char)('0'+cellValue);
  }

}

class TestClass
{
  private static readonly Random RANDOM = new Random();

  private static StreamWriter _output;

  public static void Main() {
    using ( _output = new StreamWriter("TestClass.out") ) {
      // priming goes
      ProcessDay(new Matrix(), 0);
      ProcessDay(new int[16,16], 0);

      // timed runs
      Time("Using a struct", delegate() {
        for (int i=0; i<1000; ++i) 
          ProcessDay(new Matrix(), 0);
      });
      Time("Using an array", delegate() {
        for (int i=0; i<1000; ++i) 
          ProcessDay(new int[16,16], 0);
      });
    }
    Console.WriteLine("See: "+Environment.CurrentDirectory+@"\TestClass.out");
    Pause();
  }

  #region Using a plain int[,]

  private static void ProcessDay(int[,] theMap, int day) {
    if ( day == 10 ) return;
    var myMap = (int[,])theMap.Clone();
    myMap[RANDOM.Next(Matrix.ROWS),RANDOM.Next(Matrix.COLS)] = day;
    WriteMap(day, myMap);
    ProcessDay(myMap, day + 1);
    WriteMap(day, myMap);
  }

  private static void WriteMap(int day, int[,] map) {
    _output.Write("\r\n{0}:\r\n", day);
    for ( int row=0; row<16; ++row) {
      for ( int col=0; col<16; ++col) 
        _output.Write(map[row,col]==0 ? '.' : (char)('0'+map[row,col])); 
      _output.WriteLine();
    }
  }

  #endregion

  #region Using the Matrix struct

  public static void ProcessDay(Matrix map, int day) {
    if ( day == 10 ) return;
    map[RANDOM.Next(Matrix.ROWS),RANDOM.Next(Matrix.COLS)] = day;
    WriteMap(day, map);
    ProcessDay(map, day + 1);
    WriteMap(day, map);
  }

  private static void WriteMap(int day, Matrix map) {
    _output.Write("\r\n{0}:\r\n{1}", day, map);
  }

  #endregion

  private delegate void TimedTask();
  private static void Time(string desc, TimedTask task) {
    Console.WriteLine();
    Console.WriteLine(desc);
    var sw = new System.Diagnostics.Stopwatch();
    sw.Start();
    task();
    sw.Stop();
    Console.WriteLine(desc +" took "+ sw.ElapsedMilliseconds + " ms");
  }

  [Conditional("DEBUG")]
  private static void Pause() {
    Console.Write("Press any key to continue . . .");
    Console.ReadKey();
  }

}

Cheers. Keith.

EDIT 2: Here's the results of my investigation into the question "Why isn't the struct faster?". After all it "should" be, shouldn't it? I mean creating lots-of-largeish-structs on the stack should be a shipload more efficient than creating all those equivalent objects on the heap AND GARBAGE COLLECTING THEM... so what's the story?

Assuming that "struct creation and passing" is more efficient, I reckon the gains we made there must be being offset by less efficient cell access... so I made the below little bit-twiddling tweak to my struct indexor - (row<<4) instead of row*16 - and now the struct is about 30% faster than the array... which is as much of a gain as I'd dared to hope for initially, so yeah, Cool ;-)

public int this[int row, int col] {
  get { 
    fixed ( int* p = Cells)
      return *(p+(row<<4)+col);
  }
  set { 
    fixed ( int* p = Cells)
      *(p+(row<<4)+col) = value; 
  }
}

I also tried outputting everything twice to test the theory that my matrix access is still less efficient than native-bidimensional-array access... and it is. The struct and the class solutions are back to neck-and-neck when you output the map twice (once on the way down the callstack and again on the way back up it)... so I'd kill to know how the indexor is implemented in native bidimensional arrays.

NEW QUESTION: Any suggestions on how to speed up my indexor implementation, or references to the C# compilers implementation of native bidimensional arrays would be most welcome. TIA ;-)

Cheers. Keith.

回答1:

if unsafe you can use a fixed size array in your struct. Can only be used in unsafe mode though.

struct Row {
  public const int COLS = 16;

  public fixed int Cols[COLS];

...

Also can do fun stuff with pointers but only in unsafe also

    [StructLayout(LayoutKind.Sequential, Size = 64)]
    unsafe struct Row
    {
        public int this[int index]
        {
            get
            {
                // need validation of index or AV
                fixed (Row* p = &this)
                {
                    int* value = (int*)p;
                    return *(value + index);
                }
            }

            set
            {
                // need validation of index or AV
                fixed (Row* p = &this)
                {
                    int* item = (int*)p;
                    item += index;
                    *item = value;
                }
            }
        }
    }

回答2:

There are at least three safe approaches; which one is best will depend upon your usage patterns:

Have the struct hold a private array member, and have the indexed property setter make a copy of the array, modify the copy, and then store a reference to the modified array, in that order. If you wish to allow simultaneous thread-safe updates to multiple array members, you should wrap the above in a `CompareExchange` loop (so that if one thread updates the array reference between the time another thread has read it and written it back, the latter thread will repeat its update operation on the new array). This approach will be slow to update, but passing the struct will be fast since it need not contain anything but an array reference.
Have the struct hold a number of discrete fields. If you may be wanting to use a somewhat largish array (bearing in mind that, with such uses, you should pass things by `ref` when practical) it may be helpful to use generic structure, and nest your arrays; if you do this, you'll need to use some tricks described below to make updates work properly (such tricks may help efficiency in any case). A couple of very useful methods to include would be:
```
  // Define these delegates somewhere outside the struct
  delegate void ActionByRef2<T>(ref 1 param);
  delegate void ActionByRef2<T1,T2>(ref T1 p1, ref T2 p2);

  // Within StructArray<T>, define methods
  static void UpdateItemAtIndex(ref StructArray1<T> arr, int index, ActionByRef<T> proc);
  static void UpdateItemAtIndex<TParam>(ref StructArray1<T> arr, int index,
     ActionByRef<T,TParam> proc, ref TParam param);
```
These methods would allow actions to be performed on array elements, passing then by `ref` rather than by value. It may be helpful to define a versions with two "extra" `ref` parameters, or maybe even more; it's too bad there's no way to write a variadic version. Using these methods, if one has a `SixteenITemArray>`, one could have the outer array pass a "row" to the inner array's update method, allowing it to be updated "in place". One could even manage to do a `CompareExchange` on an individual array elements, something which isn't possible with any of the other non-array collections built into .net outside some of the recent `ConcurrentXXX` collections. Note that these methods are static, and take the thing to be acted upon as a `ref` parameter. Doing things this way will prevent them from being used to act upon read-only structures.

Design a data structure which combines one or more references to immutable objects and some optional additional information so as to allow for efficient updates. As a simple (far from optimal) example:

struct StructArray2<T>
{
  T arr[];
  T extraItem;
  int extraItemIndexPlusOne;
  T this[int index]
  {
    get
    {
      if (extraItemIndexPlusOne == index+1)
        return extraItem;
      else if (arr != null)
        return arr[index]};
      else
        return default(T);
    }
    set
    {
      if (extraItemIndexPlusOne != 0 && extraItemIndexPlusOne != index+1)
      {
        T[] tempArr;
        if (arr == null)
          tempArr = new Arr[size];
        else
          tempArr = (T[])arr.Copy();
        tempArr[extraItemIndexPlusOne-1] = extraItem;
        tempArr[index] = value;
        arr = tempArr;
        extraItemPlusOne = 0;
      }
      else
      {
        extraItem = value;
        extraItemIndexPlusOne = index+1;
      }
    }
  }
}

Assuming it works (untested), this code will reduce by at least half the number of array-copy operations compared with the first approach, since half the update operations will simply update `extraItem` and `extraItemIndexPlusOne` without having to touch the array.

Which approach is best will depend upon your application.