Efektywne kopiowanie macierzy obiektów na większą macierz obiektów

Question

Piszę strukturę podobną do kwadratu, która zawiera matryce obiektów ogólnych T. Jeśli wszystkie cztery podwęzły zawierają zdefiniowane macierze T, zamierzam je zebrać w jedną, większą macierz, a następnie usunąć podwęzły. Czy jest to skuteczniejszy sposób niż przechodzenie przez każdą referencję i jej kopiowanie? Czy mogę zamiast tego skopiować porcje pamięci?

---

Przykład:

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

Jeśli możesz uczynić strukturę niezmienną, być może uratujesz się od konieczności wykonywania wielu kopii. Eric Lippert ma około great posts about immutable structures.

Edit: Ponownie, nie wiem, czy będzie to zwiększyć wydajność w swojej sprawie, ale tutaj jest przykład możliwej konstrukcji z niezmiennych obiektów:

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

Teraz będzie można użyć to w następujący sposób:

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

Znowu, ja nie wiem, czy to jest właściwe w danej sytuacji, czy też daje wzrost wydajności, ponieważ masz poziom zadnie gdy uzyskanie wartości. Istnieje jednak kilka sposobów, aby to poprawić, ale zależy to od tego, co naprawdę trzeba zrobić.

Powodzenia.

Answer 2

Może jestem daleko baza tutaj, ale jeśli ograniczyć T być rodzaj odniesienia wtedy można byłoby kopiowanie niczego więcej niż odniesień, a nie dane samo. Stwórz więc nowe odniesienia do obiektów T w nowej macierzy i usuń je ze starych macierzy. Oto, w jaki sposób można ograniczyć T. Zwróć uwagę na użycie słów kluczowych where i class.

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

Answer 3

System.Buffer.BlockCopy być może? To skopiuje fragmenty pamięci.

Answer 4

Jeśli nie boisz się używać niebezpiecznego kodu i możesz używać referencji, możesz użyć wskaźników starego stylu. Najpierw musisz użyć słowa kluczowego fixed do swoich tablic. Wielowymiarowa tablica wyrównuje każdy wymiar po sobie.

Answer 5

Postanowiłem umieścić mój komentarz jako odpowiedź.

Innymi słowy: kopiujesz elementy macierzy do innej macierzy? Możesz użyć Array.CopyTo lub Buffer.BlockCopy (kopiowanie zajmie tylko kilka μs).

Ponadto, jeśli zmodyfikować swój projekt, więc nie jest array[64], ale array[64*64] i użyć modulo (%)/pomnożyć (*) pobierać/elementy, to będzie jeszcze szybciej. Nie wiesz, gdzie jest twoje wąskie gardło wydajności. Zależy to od tego, jak często uzyskujesz dostęp do elementów matryc w porównaniu do częstotliwości ich kopiowania.

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

aw kodu:

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