Simulate an array with structure in C #?

Question

People,

Please, anyone can imagine a “good way” to define a structure in C # that behaves like an array ( int[,] in my case), except that (like all structures) a copy of the structure is passed to any / all called methods.

Below is my ugly first attempt (a structure that mimics a simple int[] , not a matrix) with a small test harness to get it to do something. I think I will have a Matrix of Row structure that will follow a similar pattern. But it's just that much. There has to be a better way!

Any ideas please?

CHECK 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 ONE?

This test verifies that:

• The COPY of the Row structure is passed to the ProcessRow, leaving the local string intact.
• 16 calls with a structure of 16 ints do not call the call stack.

If you're curious ... My real problem is that I pass int [16,16] "map" down a recursive call tree that processes each "daily move" in Programming Challenge 62 - Bendorf Weed Invasion ... on I'm currently doing Array.Copy (actually a couple) for each move I am evaluating and there are about 1.3 quintillion combinations of 10 valid moves, so (oddly enough) it is too slow at 33.5 hours . I thought that passing the structure instead of referencing the array could speed up the process significantly, but I still suspect that I will need a completely different approach (i.e., completely rethinking my algorithm) in order to get closer to the “desired” 100 seconds. What I need is a “quick try”, so I thought that I would find some kind of efficiency first ... Now I know exactly how the guys felt in the era of performance. Waiting for a day and a half for your withdrawal sucks!

---

EDIT: To include my answer based on the accepted AbdElRaheim answer.

It uses a "flat" fixed array of ints to simulate an array of ints with two indices.

All he does is reccess ProcessDay 10 times, passing the map and day index. On each “day”, he simply sets a random cell on the day and prints the map twice: first on the way down the stop-order and again on the way back up ... so that you can, if you want, make sure each ProcessDay call has its own copy of the card.

I do this in two different ways: with the matrix structure and the standard int [,] ... suprise (at least for me) is that the structure 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(); } } 

Greetings. Whale.

---

EDIT 2: Here are the results of my research on the question “Why isn't structure faster?”. In the end, it should be, right? I mean, creating multi-user structures on the stack should be more efficient than creating all these equivalent objects on the heap AND THE SCHEME OF COMBINING THEM ... And what is this story?

Assuming that “creating and transferring the structure” is more efficient, I believe that the profits we made should be offset by less efficient access to the cells ... so I made a little twilak setting for my struct index - (row<<4) instead of row*16 - and now the structure is about 30% faster than an array ... which is as big a win as I dared to hope for initially, so yes, 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 to deduce everything twice to test the theory that my matrix access is even less efficient than accessing an array based on a bidirectional array ... and it is. Structural and class decisions come back to the neck and neck when you draw the map twice (once on the way down the stop-case and again on the way back up) ... so I would kill to find out how the index is implemented in its own two-dimensional arrays .

NEW QUESTION: Any suggestions on how to speed up the implementation of the indexer, or references to the implementation of C # compilers for your own two-dimensional arrays, will be most welcome. TIA -)

Greetings. Whale.

Answer 1

If unsafe, you can use a fixed-size array in your structure. It can be used only in unsafe mode.

 struct Row { public const int COLS = 16; public fixed int Cols[COLS]; ... 

You can also do funny things with pointers, but only in unsafe

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

Answer 2

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

• Let the struct store the private member of the array and have the indexed set of properties set, copy the array, modify the copy and save the link to the modified array in that order. If you want to allow simultaneous thread-safe updates for multiple members of the array, you must wrap this in a CompareExchange loop (so if one thread updates the array reference between the other threads reading and writing them back, the last thread will repeat the update operation in the new array). This approach will be slow to update, but passing the structure will be fast since it should not contain anything other than an array reference.
• Let struct store some discrete fields. If you might want to use a somewhat rather large array (bearing in mind that with this use you should pass things “ref” when possible), it may be useful to use a general structure and nest your arrays; if you do, you will need to use some of the tricks described below to make the updates work (such tricks can help anyway). A few very useful methods to include:

    // 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 will allow you to perform actions on array elements, passing then `ref`, and not by value. It may be useful to define versions with two "additional" parameters of `ref` or perhaps even more; too bad that there is no way to write a variation version. Using these methods, if you have "SixteenITemArray>", it would be possible for the external array to pass the "string" to the internal array update method, allowing it to be updated in-place. You can even do “CompareExchange” on individual elements of the array, which is not possible with any other non-massive collections built into .net outside of some recent ConcurrentXXX collections. Note that these methods are static and take on the role of the `ref` parameter. Performing this method will not allow them to be used for read-only use.
• Create a data structure that combines one or more references to immutable objects and some additional additional information to provide effective 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 (unchecked), this code will reduce by at least half the number of copy operations of the array compared to the first approach, since half of the update operations will simply update the extraItem and extraItemIndexPlusOne without touching the array.

Which approach will best depend on your application.