1

伙计们,

请任何人都可以想象在 C# 中定义一个结构的“好方法”,它的行为类似于一个数组(int[,]在我的情况下是一个),除了(像所有结构一样)结构的副本被传递给任何/所有调用的方法。

下面是我丑陋的第一次尝试(一个模拟简单的结构int[],还不是矩阵),并带有一个小测试工具来使它做一些事情。我想我会有一个struct Matrix of Row's,它会遵循类似的模式。但这只是太冗长了。一定有更好的办法!

请问有什么想法吗?

测试线束

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

输出:

 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

何苦?

该测试验证:

  • 将 Row 结构的 COPY 传递给 ProcessRow,保持本地 Row 不变。
  • 结构为 16 个整数的 16 个调用不会弹出调用堆栈。

如果你有兴趣......我真正的问题是我目前正在将一个 int[16,16] “映射”传递给一个递归调用树,该树处理编程挑战 62 - Bendorf Weed Invasion中的每个“日常移动” 。 . 目前我正在为评估的每一个动作做一个 Array.Copy (实际上是一对),并且有大约 1.3 个 quintillion 组合需要考虑 10 个有效动作,所以(有趣的是)它太慢了,在 abour 33.5小时. 我认为传递结构而不是数组引用可能会显着加快速度,但我仍然怀疑我需要一种完全不同的方法(即完全重新考虑我的算法)来接近“期望的”100 秒。我需要做的是“快速尝试”,所以我想我会先找到一些效率……我现在确切地知道这些人在穿孔磁带时代的感受。为你的输出等待一天半完全糟透了!


编辑:包括我的答案,这是基于 AbdElRaheim 接受的答案。

它使用“平面”固定整数数组来模拟双下标整数数组。

它所做的只是递归ProcessDay 10 次,传递mapday index。在每个“天”中,它只是将一个随机单元格设置为day,并打印出两次地图:第一次是在调用堆栈下的路上,然后在再次返回的路上......这样你就可以,如果你愿意,验证ProcessDay的每个调用都有自己的地图副本。

我正在以两种不同的方式执行此操作:使用Matrix struct和使用标准的int[,] ...惊喜(至少对我而言)是该结构更慢...叹息!

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

}

干杯。基思。


编辑2:这是我对“为什么结构不更快?”问题的调查结果。毕竟它“应该”是,不是吗?我的意思是在堆栈上创建大量的大型结构应该比在堆上创建所有那些等效的对象和垃圾收集它们更有效......那么故事是什么?

假设“结构创建和传递”更有效,我认为我们在那里取得的收益一定会被效率较低的单元格访问所抵消......所以我对我的结构索引器进行了下面的小小调整 -(row<<4)而不是row*16- 和现在 struct 比数组快 30% 左右......这是我最初敢于希望的收益,所以是的,很酷 ;-)

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

我还尝试将所有内容输出两次以测试我的矩阵访问仍然不如本机二维数组访问效率低的理论......确实如此。当您输出地图两次时,结构和类解决方案又恢复了并驾齐驱(一次是在调用堆栈的途中,另一次是在备份它的路上)......所以我很想知道索引器是如何在原生二维数组中实现。

新问题:任何关于如何加快我的索引器实现的建议,或对原生二维数组的 C# 编译器实现的引用都将受到欢迎。TIA ;-)

干杯。基思。

4

2 回答 2

2

如果不安全,您可以在结构中使用固定大小的数组。不过只能在不安全模式下使用。

struct Row {
  public const int COLS = 16;

  public fixed int Cols[COLS];

...

也可以用指针做有趣的事情,但也只能在不安全的情况下

    [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;
                }
            }
        }
    }
于 2012-10-31T06:48:01.980 回答
1

至少有三种安全的方法;哪个最好取决于您的使用模式:

  1. 让结构持有一个私有数组成员,并让索引属性设置器制作数组的副本,修改副本,然后按该顺序存储对修改后的数组的引用。如果您希望允许同时对多个数组成员进行线程安全更新,则应将上述内容包装在 `CompareExchange` 循环中(这样,如果一个线程在另一个线程读取它并写回它的时间之间更新数组引用,则后一个线程将在新数组上重复其更新操作)。这种方法更新起来会很慢,但是传递结构会很快,因为它不需要包含任何东西,只需要一个数组引用。
  2. 让结构包含许多离散字段。如果您可能想要使用稍微大一点的数组(请记住,在这种情况下,您应该在实际情况下通过 `ref` 传递东西),使用泛型结构和嵌套数组可能会有所帮助;如果您这样做,您将需要使用下面描述的一些技巧来使更新正常工作(这些技巧在任何情况下都可能有助于提高效率)。包括几个非常有用的方法是:
      // 在结构之外的某个地方定义这些委托
      委托 void ActionByRef2<T>(ref 1 param);
      委托 void ActionByRef2<T1,T2>(ref T1 p1, ref T2 p2);
    
      // 在 StructArray<T> 中,定义方法
      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);
    
    这些方法将允许对数组元素执行操作,然后通过“ref”而不是值传递。使用两个“额外”的 `ref` 参数定义版本可能会有所帮助,甚至更多;太糟糕了,没有办法编写可变参数版本。使用这些方法,如果有一个 `SixteenITemArray>`,则可以让外部数组将“行”传递给内部数组的更新方法,从而使其“就地”更新。甚至可以设法对单个数组元素执行“CompareExchange”,这是在最近的“ConcurrentXXX”集合之外的.net 中内置的任何其他非数组集合无法实现的。请注意,这些方法是静态的,并将要操作的事物作为 `ref` 参数。
  3. 设计一种数据结构,将一个或多个对不可变对象的引用和一些可选的附加信息结合起来,以实现有效的更新。作为一个简单的(远非最佳)示例:
    结构 StructArray2<T>
    {
      塔尔[];
      额外物品;
      int extraItemIndexPlusOne;
      T this[int 索引]
      {
        得到
        {
          if (extraItemIndexPlusOne == index+1)
            返回额外项目;
          否则 if (arr != null)
            返回 arr[索引]};
          别的
            返回默认值(T);
        }
        放
        {
          if (extraItemIndexPlusOne != 0 && extraItemIndexPlusOne != index+1)
          {
            T[] tempArr;
            如果(arr == null)
              tempArr = 新 Arr[大小];
            别的
              tempArr = (T[])arr.Copy();
            tempArr[extraItemIndexPlusOne-1] = extraItem;
            tempArr [索引] = 值;
            arr = tempArr;
            extraItemPlusOne = 0;
          }
          别的
          {
            额外项目 = 价值;
            extraItemIndexPlusOne = 索引+1;
          }
        }
      }
    }
    
    假设它有效(未经测试),与第一种方法相比,此代码将至少减少一半的数组复制操作,因为一半的更新操作将简单地更新 `extraItem` 和 `extraItemIndexPlusOne` 而无需接触数组。

哪种方法最好取决于您的应用程序。

于 2012-11-01T15:50:33.507 回答