高效地将对象矩阵复制到更大的对象矩阵

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