Laden...

mehrdimensionales bzw jagged Array effizient kopieren

Erstellt von bloody_fighter vor 13 Jahren Letzter Beitrag vor 13 Jahren 3.194 Views
B
bloody_fighter Themenstarter:in
54 Beiträge seit 2008
vor 13 Jahren
mehrdimensionales bzw jagged Array effizient kopieren

Guten Abend,
Ich bin derzeit dabei ein Programm zu programmieren, das sehr Rechenintensiv ist.
Dabei muss ich unter anderem ein Objekt sehr oft kopieren, welches eine 2 Dimensionale Liste enthält. Bisher braucht dieser Vorgang 40% der rechenzeit.
Ich mache es bisher so:
Das ist die Klasse deren Instanzen kopiert werden sollen mit ihrem Konstruktor:

    class Feld
    {
        public List<List<int>> feld = new List<List<int>>();
        public int breite;
        public Feld(int breite)
        {
            this.breite = breite;
            for (int i = 0; i < breite; i++)
            {
                List<int> liste = new List<int>();
                for (int j = 0; j < breite; j++)
                {
                    liste.Add(0);
                }
                feld.Add(liste);
            }
        }

Das ist die Funktion in der Klasse, mit der ich bisher kopiere:

public Feld KopieErstellen()
        {
            
            Feld b = new Feld(breite);
            
            for(int i = 0; i < breite; i++)
            {
                b.feld.Add(new List<int>());
                for (int j = 0; j < breite; j++)
                {
                    b.feld[i].Add(new int());
                    b.feld[i][j] = feld[i][j];
                }
            }             

            return b;
        }

Wie kann ich das ganze schneller machen??
Liebe Grüße,
Daniel

194 Beiträge seit 2006
vor 13 Jahren

Hallo bloody_fighter

Ich will jetzt nicht deinen Code refactoren(gut Deutsch) aber du solltest grundsätzlich properties(Eigenschaften) anstatt von Feldern verwenden.

Dann zu deiner Frage. Ausser dass man


public Feld KopieErstellen()
..
                    b.feld[i].Add(new int()); //Hier sowieso nicht ganz klar was das ergibt
                    b.feld[i][j] = feld[i][j];
...
        }

gleich in


public Feld KopieErstellen()
..
                    b.feld[i].Add(feld[i][j]);
...
        }

umändern könnte sehe ich keine weiteren nennenswerten Möglichkeiten mehr um noch was an Performance rauszuholen.

Es gäbe natürlich auch noch List(T).CopyTo-Methode (T[]) aber dies verläuft dann über den Umweg eines Puffer arrays und daher eigentlich mehr Rechenarbeit.

Gruss

Balaban_s

Gelöschter Account
vor 13 Jahren

Schau doch mal ob du mit Paralell.For etwas rausholen kannst.
Natürlich von Rechner zu Rechner verschieden dann.

16.807 Beiträge seit 2008
vor 13 Jahren

Du kannst eine Liste auch 1:1 Klonen How do i clone a generlic list in c#
Ein ähnliches Prinzip solltest Du auf Dein Objekt mit Properties ebenfalls anwenden können.

Oder machst ne Shallow copy mit Hilfe von GetRange() da sparst Dir wenigstens eine Schleife.

5.742 Beiträge seit 2007
vor 13 Jahren

Hallo bloody_fighter,

sicher, dass du wirklich eine Liste brauchst?

Mit einem reinen multidimensionalen Array ginge es sicherlich schneller in Verbindung mit Array.Copy.

4.931 Beiträge seit 2008
vor 13 Jahren

Hallo bloody_fighter,

ist es denn zwingend erforderlich, daß du jedesmal eine DeepCopy machen mußt, d.h. verändern sich die Feldinhalte bei dir?

Da du anscheinend immer konstante, quadratische Felder hast, würde sich bei dir auch ein multidimensional (rect)-Array anbieten, d.h.


private int[,] fields;

public Feld(int breite)
{
   fields = new int[breite, breite];
   // ...
}

Diese lassen sich auch einfacher (und schneller) als jagged-Arrays kopieren (Array.Copy).

Mist: winSharp93 war schneller, dafür habe ich noch etwas Beispiel-Code...

1.361 Beiträge seit 2007
vor 13 Jahren

Hi,

Ich bin derzeit dabei ein Programm zu programmieren, das sehr Rechenintensiv ist. Dann sollte auch der Zugriff effizient erfolgen können. Das ist bei einem jagged Array so. (siehe Hilfe bei Performance (was ist schneller z.B. int[,] oder List<List<int>>))

Das kopieren eines jagged Arrays ist ebenso effizient möglich.

class Feld
{
    public int[][] feld;
    public int breite;

    public Feld(int breite)
    {
        this.breite = breite;
        feld = new int[breite][];
        for (int i = 0; i < breite; i++)
        {
            feld[i] = new int[breite];
        }
    }

    public Feld(Feld f) // Copy Constructor
    {
        this.breite = f.breite;
        feld = new int[breite][];
        for (int i = 0; i < breite; i++)
        {
            feld[i] = new int[breite];
            f.feld[i].CopyTo(feld[i], 0);
        }
    }

    public Feld KopieErstellen()
    {
        return new Feld(this);
    }
}

Du könntest - wenn breite wirklich sehr sehr groß werden könnte - diese schleife sogar parallelisieren.

beste Grüße
zommi

998 Beiträge seit 2007
vor 13 Jahren

unsafe und mit Pointern kopieren! Ist schnell und einfach zu implementieren!

Gruß David

5.742 Beiträge seit 2007
vor 13 Jahren

unsafe und mit Pointern kopieren!

Array.Copy ist IMHO sogar in Assembler implementiert - das sollte nichts mehr schlagen.

B
bloody_fighter Themenstarter:in
54 Beiträge seit 2008
vor 13 Jahren

Ersteinmal vielen Dank für die vielen Antworten.
@TH69, ja, es ist zwingend erforderlich, dass ich jedes mal eine DeepCopy mache. Das ganze Programm arbeitet Rekursiv und ruft sich jedes mal etwa 20 mal selbst auf(also die Funktion), dafür muss dann aber auch jedes mal ein neues Feld übergeben werden. Ansonsten werde ich dann wohl auf einen 2Dimensionalen Array umsteigen und dafür die Liste weglassen, das scheint dann ja wohl ordentlich schneller zu gehen 😉

B
bloody_fighter Themenstarter:in
54 Beiträge seit 2008
vor 13 Jahren

So, habe es jetzt umgesetzt. Jetzt braucht es nur noch 10% anstatt 40% der Gesamtdauer, also weit mehr als eine vervierfachung der geschwindigkeit des kopierens!

5.742 Beiträge seit 2007
vor 13 Jahren

Weitere Idee zur Performanceoptimierung: Je nach dem, wie viel Änderungen du durchführst bzw. wie diese Änderungen auf die einzelnen Zeilen und Spalten verteilt sind, kannst du auch erst bei der ersten Änderung kopieren.

Hier könntest du sogar den Zustand für jede Dimension des Arrays einzeln verwalten, was dazu führen kann, dass du bei entsprechenden Änderungen nur eine "Zeile" bzw. "Spalte" kopieren müsstest (und nicht jedes Mal alle).

Das umzusetzen ist aber nicht ganz so trivial wie ein komplettes Kopieren.

B
bloody_fighter Themenstarter:in
54 Beiträge seit 2008
vor 13 Jahren

Also es wird immer kopiert und eine einzige position wird dann geändert. Theoretisch könnte ich also auch immer nur z.B. die entsprechende Zeile kopieren und für die anderen Zeilen dann nur den Verweis kopieren, aber ob das so viel bringt weiß ich nicht...als alternative habe ich mir überlegt, einfach jedesmal die Änderung wieder rückgängig zu machen. Denkt ihr, dass das Performancetechnisch Sinn ergeben würde?

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo bloody_fighter,

kannst du auch erst bei der ersten Änderung kopieren.

nennt sich Copy On Write.

Denkt ihr, dass das Performancetechnisch Sinn ergeben würde?

Warum probierst du es nicht aus? Hängt natürlich von dem Umständen ab, aber die Chancen halte ich für gut.

herbivore