Copia eficiente de una matriz de objetos a una matriz más grande de objetos

Question

Estoy escribiendo una estructura de datos similar a un quadtree que contiene matrices de objetos genéricos T. Si cuatro subnodos contienen todas las matrices definidas de T, voy a agregarlos en una matriz única y más grande, y luego eliminar los subnodos. ¿Hay una forma más eficiente de hacer esto que recorrer cada referencia y copiarla? ¿Puedo copiar trozos de memoria en su lugar?

---

Ejemplo:

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

Si puede hacer que la estructura sea inmutable, puede evitar tener que hacer muchas copias. Eric Lippert tiene algunos great posts about immutable structures.

Editar: Una vez más, no sé si va a mejorar el rendimiento en su caso, pero aquí es un ejemplo de un posible diseño con objetos inmutables:

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

Ahora usted sería capaz de usar es como sigue:

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

una vez más, no sé si es apropiado en su situación o si se da una mejora en el rendimiento, porque tiene un nivel de indirección al obtener el valor. Sin embargo, hay varias formas de mejorar esto, pero depende de lo que realmente necesite hacer.

Buena suerte.

Answer 2

Tal vez estoy fuera de lugar aquí, pero si la restringirá T a ser un tipo de referencia, entonces sería copiando nada más que las referencias y no los datos sí mismo. Así que solo cree nuevas referencias a los objetos T en la nueva matriz y elimínelos de las matrices antiguas. Aquí es cómo puede restringir T. Observe el uso de las palabras clave where y class.

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

Answer 3

System.Buffer.BlockCopy quizás? Eso copiará trozos de memoria.

Answer 4

Si no tiene miedo de usar un código inseguro y puede utilizar referencias, puede usar punteros de estilo antiguo. Primero debe usar la palabra clave fixed en sus matrices. La matriz multidimensional alinea cada dimensión una después de la otra.

Answer 5

Decidí poner mi comentario como respuesta.

Entonces en otras palabras: ¿está copiando los elementos de una matriz en alguna otra matriz? Puede usar Array.CopyTo o Buffer.BlockCopy (la copia solo tardará varios μs).

Además, si modifica su diseño por lo que no es array[64], pero array[64*64] y el uso de módulo (%)/multiplicar (*) para obtener elementos/sistema, que será aún más rápido. Sin embargo, no estoy seguro de dónde está el cuello de botella de rendimiento. Depende de la frecuencia con la que acceda a los elementos de las matrices frente a la frecuencia con la que copia.

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

y en el código:

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