1

皆さん、

(すべての構造体と同様に) 構造体のコピーが任意/すべての呼び出されたメソッドに渡されることint[,]を除いて、C# で配列のように動作する (私の場合は) 構造体を定義する「良い方法」を誰でも想像できますか?

以下は、私の醜い最初の試み (int[]まだマトリックスではなく単純な をシミュレートする構造体) で、何かを実行するための小さなテスト ハーネスを使用しています。同様のパターンに従うRow's の struct Matrixがあると思います。しかし、それは非常に冗長です。もっといい方法があるに違いない！

何かアイデアはありますか？

テストハーネス

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 個の int の構造体を使用した 16 回の呼び出しは、呼び出しスタックをポップしません。

興味があれば...私の本当の問題は、現在、int [16,16]「マップ」を再帰呼び出しツリーに渡していることです。これは、プログラミングチャレンジ62の「毎日の動き」を処理します-ベンドルフウィードインベージョン.. . 現時点では、評価される手ごとに Array.Copy (実際には 2 つ) を実行していますが、考慮すべき 10 の有効な手の組み合わせは約 1.3 京あります。 33.5時間. 配列参照の代わりに構造体を渡すと大幅に高速化される可能性があると思いましたが、「望ましい」100秒に近づくには、まったく異なるアプローチ（つまり、アルゴリズムを完全に再考する）が必要になると思います。私ができる必要があるのは「物事をすばやく試す」ことなので、最初にいくつかの効率性を見つけようと思いました..パンチテープの時代に彼らがどのように感じていたかを正確に知ることができます. あなたのアウトプットを半日待つのは本当に最低です！

編集: AbdElRaheim によって受け入れられた回答に基づく私の回答を含めるには。

これは、int の "フラットな" 固定配列を使用して、二重添字付きの int 配列をシミュレートします。

ProcessDay を10 回再帰し、 mapとday indexを渡すだけです。各「日」で、ランダムなセルをdayに設定し、マップを 2 回出力します。最初はコールスタックを下る途中で、もう 1 つは再び戻る途中です...必要に応じて、ProcessDayの呼び出しごとに独自のマップのコピーがあることを確認します。

私はこれを 2 つの異なる方法で行っています: 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();
  }

}

乾杯。キース。

EDIT 2:「なぜ構造体が速くならないのですか?」という質問に対する私の調査結果は次のとおりです。やっぱり「あるべき」じゃないですか。スタック上に大量の大きな構造体を作成することは、ヒープ上に同等のオブジェクトをすべて作成してそれらをガベージコレクションするよりも効率的であるべきだということです...それで、話は何ですか?

「構造体の作成と受け渡し」がより効率的であると仮定すると、そこで得られた利益は、効率の悪いセルアクセスによって相殺されるに違いないと考えています...そのため、構造体インデクサーに以下の少しいじる微調整を行いました-(row<<4)代わりにrow*16-と現在、構造体は配列よりも約 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; 
  }
}

また、すべてを 2 回出力して、マトリックス アクセスがネイティブの 2 次元配列アクセスよりも効率が悪いという理論をテストしてみましたが、そうです。構造体とクラスのソリューションは、マップを 2 回出力すると (1 回はコールスタックを下る途中で、もう 1 回は戻る途中で) 首と首に戻ってきます。ネイティブの 2 次元配列で実装されます。

新しい質問: インデクサーの実装を高速化する方法に関する提案、またはネイティブの 2 次元配列の C# コンパイラの実装への参照は大歓迎です。ティア;-)

乾杯。キース。

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

少なくとも 3 つの安全なアプローチがあります。どちらが最適かは、使用パターンによって異なります。

  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」で渡します。2 つの「余分な」 `ref` パラメータ、またはそれ以上のバージョンを定義すると役立つ場合があります。可変長バージョンを書く方法がないのは残念です。これらのメソッドを使用すると、「SixteenITemArray>」がある場合、外側の配列から「行」を内側の配列の更新メソッドに渡して、「その場で」更新できるようにすることができます。個々の配列要素に対して「CompareExchange」を実行することもできますが、これは、最近の「ConcurrentXXX」コレクション以外の .net に組み込まれた他の非配列コレクションでは不可能なことです。これらのメソッドは静的であり、操作対象を `ref` パラメータとして受け取ることに注意してください。
  3. 効率的な更新を可能にするために、不変オブジェクトへの 1 つ以上の参照といくつかのオプションの追加情報を組み合わせたデータ構造を設計します。簡単な (最適とはほど遠い) 例として: 
    struct StructArray2<T>
{
  タール[];
  T extraItem;
  int extraItemIndexPlusOne;
  T this[int インデックス]
  {
    得る
    {
      if (extraItemIndexPlusOne == インデックス+1)
        extraItem を返します。
      else if (arr != null)
        戻る arr[インデックス]};
      そうしないと
        デフォルト(T)を返します。
    }
    設定
    {
      if (extraItemIndexPlusOne != 0 && extraItemIndexPlusOne != インデックス+1)
      {
        T[] tempArr;
        if (arr == null)
          tempArr = 新しい Arr[サイズ];
        そうしないと
          tempArr = (T[])arr.Copy();
        tempArr[extraItemIndexPlusOne-1] = extraItem;
        tempArr[インデックス] = 値;
        arr = tempArr;
        extraItemPlusOne = 0;
      }
      そうしないと
      {
        extraItem = 値;
        extraItemIndexPlusOne = インデックス+1;
      }
    }
  }
}
    動作すると仮定すると (未テスト)、このコードは、最初のアプローチと比較して、配列のコピー操作の数を少なくとも半分に減らします。

どのアプローチが最適かは、アプリケーションによって異なります。

于 2012-11-01T15:50:33.507 に答える