高效地將對象矩陣複製到更大的對象矩陣

Question

我正在寫一個包含通用對象矩陣的四叉樹數據結構T。如果四個子節點都包含定義的矩陣T，我將它們聚合成一個更大的矩陣，然後刪除子節點。有沒有比循環遍歷每個引用並複製它更有效的方法？我可以複製大塊內存嗎？

---

例子：

T[,] _leaf1 = new T[64,64]; 
T[,] _leaf2 = new T[64,64]; 
T[,] _leaf3 = new T[64,64]; 
T[,] _leaf4 = new T[64,64]; 

// Populate leafs 

T[,] _root = new T[128,128]; 

CopyInto(ref _root, ref _leaf1, 64, 64); 
CopyInto(ref _root, ref _leaf2, 0, 64); 
CopyInto(ref _root, ref _leaf3, 0, 0); 
CopyInto(ref _root, ref _leaf4, 64, 0); 

Answer 1

如果你可以使結構不變，你可以保存自己不必做大量的副本。 Eric Lippert有一些great posts about immutable structures。

編輯： 同樣，我不知道這是否會在你的情況下提高性能，但這裏是一個可能的設計，不可變對象的例子：

abstract class QuadTree<T> 
{ 
    public QuadTree(int width, int height) 
    { 
     this.Width = width; 
     this.Heigth = heigth; 
    } 

    public int Width { get; private set; } 
    public int Height { get; private set; } 

    public abstract T Get(int x, int y); 
} 

class MatrixQuadTree<T> : QuadTree<T> 
{ 
    private readonly T[,] matrix; 

    public QuadTree(T[,] matrix, int width, int heigth) 
     : base(width, heigth) 
    { 
     this.matrix = matrix; 
    } 

    public override T Get(int x, int y) 
    { 
     return this.matrix[x, y]; 
    } 
} 

class CompositeQuadTree<T> : QuadTree<T> 
{ 
    private readonly QuadTree<T> topLeft; 
    private readonly QuadTree<T> topRight; 
    private readonly QuadTree<T> bottomLeft; 
    private readonly QuadTree<T> bottomRight; 

    public CompositeQuadTree(QuadTree<T> topLeft, 
     QuadTree<T> topRight, QuadTree<T> bottomLeft, 
     QuadTree<T> bottomRight) 
     : base(topLeft.Width + topRight.Width, 
      topLeft.Height + bottomLeft.Heigth) 
    { 
     // TODO: Do proper checks. 
     if (this.Width != topLeft.Width + bottomRight.Width) 
      throw Exception(); 

     this.topLeft = topLeft; 
     this.topRight = topRight; 
     this.bottomLeft = bottomLeft; 
     this.bottomRight = bottomRight; 
    } 

    public override T Get(int x, int y) 
    { 
     if (x <= this.topLeft.Width) 
     { 
      if (y <= this.topLeft.Width) 
      { 
       return this.topLeft.Get(x, y); 
      } 
      else 
      { 
       return this.topLeft.Get(x, y + this.topLeft.Heigth); 
      } 
     } 
     else 
     { 
      if (y <= this.topLeft.Width) 
      { 
       return this.topRight.Get(x + this.topLeft.Width, y); 
      } 
      else 
      { 
       return this.topRight.Get(x + this.topLeft.Width, 
        y + this.topLeft.Heigth); 
      } 
     } 
    } 
} 

現在你就可以使用它如下：

T[,] _leaf1 = new T[64,64]; 
T[,] _leaf2 = new T[64,64]; 
T[,] _leaf3 = new T[64,64]; 
T[,] _leaf4 = new T[64,64]; 

// Populate leafs 

QuadTree<T> l1 = new MatrixQuadTree<T>(_leaf1,64,64); 
QuadTree<T> l2 = new MatrixQuadTree<T>(_leaf2,64,64); 
QuadTree<T> l3 = new MatrixQuadTree<T>(_leaf3,64,64); 
QuadTree<T> l4 = new MatrixQuadTree<T>(_leaf4,64,64); 

// Instead of copying, you can no do this: 
QuadTree<T> c = CompositeQuadTree<T>(l1,l2,l3,l4); 

// And you can even make composites, of other composites: 
QuadTree<T> c2 = CompositeQuadTree<T>(c,c,c,c); 

// And you can read a value as follows: 
T value = c2[30, 50]; 

同樣，我不知道這是否是您的情況適當的或所獲得的價值時，它是否給出了一個性能改進，因爲你有間接的級別。但是，有幾種方法可以改善這一點，但這取決於您真正需要做什麼。

祝你好運。

Answer 2

也許我的路要走基地在這裏，但如果你限制T是引用類型，那麼你會被複制無非是引用的更多，而不是數據本身。因此，只需在新矩陣中創建對T對象的新引用，並將它們從舊矩陣中移除即可。這裏是你如何限制T。請注意使用where和class關鍵字。

public class Foo<T> where T: class 
{ 
} 

Answer 3

System.Buffer.BlockCopy也許？這將複製大量的內存。

Answer 4

如果您不害怕使用不安全的代碼，並且可以使用引用，則可以使用舊式指針。首先，您必須首先使用fixed關鍵字。 多維數組將每個維相互對齊。

Answer 5

決定把我的評論作爲答案。

換言之：您正在將矩陣的元素複製到其他矩陣中？您可以使用Array.CopyTo或Buffer.BlockCopy（複製只需幾微秒）。

此外，如果您修改設計，所以它不是array[64]，但array[64*64]和使用模（%）/乘（*）獲取/設置元素，它會更快。不知道你的性能瓶頸在哪裏。這取決於您訪問矩陣元素的頻率與您複製的頻率。

public class Matrix<T> 
{ 
    private int size; 
    private T[] elements; 

    public Matrix(int size) 
    { 
     this.size = size; 
     this.elements = new T[size]; 
    } 

    T this[int x, int y] 
    { 
     get 
     { 
      return elements[x + (y*size)]; 
     } 
     set 
     { 
      elements[x + (y*size)] = value; 
     } 
    } 

    public void CopyTo(Matrix<T> destination, int x, int y) 
    { 
     int offset = x + (y*size); 
     T[] destinationArray = (T[])destination; 
     Buffer.BlockCopy(this.elements, 0, destinationArray, offset, this.elements.Length); 
    } 

    public static explicit operator T[] (Matrix<T> matrix) 
    { 
     return matrix.elements; 
    } 
} 

和代碼：

Matrix<int> leaf = new Matrix<int>(64); 
Matrix<int> root = new Matrix<int>(128); 
leaf.CopyTo(root, 0, 0);