PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : [JAVA] Kopieren größerer Datenmengen (in einer 2D Datenstruktur)


Nasenbaer
2009-07-12, 23:25:37
Hi,
ich habe folgendes Problem, wer weiß was Seam Carbing ist, sollte das kennen:
Ich habe eine 2D Datstruktur (z.B. int[][]) und ich möchte nun pro Zeile ein Pixel entfernen und das in jeder Zeile (siehe Anhang) - also das schwarze wird gelöscht und dann muss der grüne Teil wieder an den roten "ranrücken".

Hatte da zuerst ein ArrayList<ArrayList<Integer>> genommen, weil dort ja nachfolgende Elemente automatisch aufrücken. Laut meinem Beispielbild geht das auch, weil jede Bildzeile ein ArrayList<Integer> ist. Für das Seam Carving muss ich diese Schnitte aber auch horizontal durchführen können - und dann klappt mein Ansatz natürlich längst nicht mehr so einfach weil ich dann mehrere ArrayList<Integer> zusammen "mergen" müsste.

Einfachste Alternative wäre ein int[][] und man kopiert nach dem Entfernen die roten und grünen Bereiche in ein neues, verkleinerte int[][]. Wenn ich da aber Element für Element umkopiere ist das langsam und memcpy() kenn ich in Java nicht. :)

Hat jemand vielleicht ne gute Idee wie man das Problem lösen könnte?

Sephiroth
2009-07-12, 23:36:56
Wie wäre es mit System.arraycopy() (http://www.martinrinehart.com/articles/repz.html)?

Monger
2009-07-12, 23:44:09
Ich bin nicht sicher, ob du dein Problem mit den Standard Klassen erschlagen bekommst. Möglicherweise musst du dir selbst da eine Datenstruktur basteln.

Wenn es um häufige Einfüge- und Löschoperationen geht, ist ja grundsätzlich mal eine LinkedList (http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html) ein Kandidat. Da ist jedes Kettenglied ein Objekt, und um eins zu entfernen/hinzuzufügen müssen lediglich vom Vorgänger und Nachfolger die Referenzen umgebogen werden. Da das kein Umkopieren benötigt, ist diese Operation sehr schnell - dafür ist es vergleichsweise teuer, auf einen bestimmten Index zuzugreifen, weil erst alle Kettenglieder durchlaufen werden müssen.

Wenn es bei dir wirklich nur eine Menge an int Werten sind, muss man unter Umständen berücksichtigen dass Autoboxing auch Performance frisst - aber so ganz grundsätzlich solltest du dir überlegen, ob du nicht vielleicht ein doppelt verlinktes "Gitter" implementieren willst. Ist vielleicht im Endeffekt einfacher, als dieses Konstrukt mühsam mit Arrays und Listen zu "simulieren".

Pinoccio
2009-07-13, 00:10:13
Ich bin nicht sicher, ob du dein Problem mit den Standard Klassen erschlagen bekommst. Möglicherweise musst du dir selbst da eine Datenstruktur basteln.

Wenn es um häufige Einfüge- und Löschoperationen geht, ist ja grundsätzlich mal eine LinkedList (http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html) ein Kandidat. Da ist jedes Kettenglied ein Objekt, und um eins zu entfernen/hinzuzufügen müssen lediglich vom Vorgänger und Nachfolger die Referenzen umgebogen werden. Da das kein Umkopieren benötigt, ist diese Operation sehr schnell - dafür ist es vergleichsweise teuer, auf einen bestimmten Index zuzugreifen, weil erst alle Kettenglieder durchlaufen werden müssen.

Wenn es bei dir wirklich nur eine Menge an int Werten sind, muss man unter Umständen berücksichtigen dass Autoboxing auch Performance frisst - aber so ganz grundsätzlich solltest du dir überlegen, ob du nicht vielleicht ein doppelt verlinktes "Gitter" implementieren willst. Ist vielleicht im Endeffekt einfacher, als dieses Konstrukt mühsam mit Arrays und Listen zu "simulieren".arraycopy ist da schon ganz richtig. Allerdings selber mal benchen (wenn du Zeit hast^^), bei kleinen Arrays sind Schleifen möglicherweise günstiger.
Ansonsten ist die Frage, wie viel % du damti verbringst, wenn du eigentlich nur Seam Carbing machst kann eine eigene Datenstruktur lohnen, wennn es nur ein kleiner Aspekt unter vielen ist, tja, wer weiß ...
AFAIK ist beim Seam Craving aber weniger das Datenschaufeln das, was dauert, sondern rauszufinden, was geschaufelt werden muß.

Gibts mehr Informationen?

/edit: Das ganze gibt es schon fertig, so zum reinschauen ;-) (http://www.developpez.net/forums/d418823/autres-langages/algorithmes/contribuez/image-seam-carving/)

mfg

Nasenbaer
2009-07-13, 00:29:15
arraycopy ist da schon ganz richtig. Allerdings selber mal benchen (wenn du Zeit hast^^), bei kleinen Arrays sind Schleifen möglicherweise günstiger.
Ansonsten ist die Frage, wie viel % du damti verbringst, wenn du eigentlich nur Seam Carbing machst kann eine eigene Datenstruktur lohnen, wennn es nur ein kleiner Aspekt unter vielen ist, tja, wer weiß ...
AFAIK ist beim Seam Craving aber weniger das Datenschaufeln das, was dauert, sondern rauszufinden, was geschaufelt werden muß.

Gibts mehr Informationen?

Brauche das nur fürs Seam Carving. Meine Aufgabe war einen bestehenden Code für Seam Carving in ein größeres Framework zu integrieren. Dabei stellte sich heraus, dass dieser Code stilistisch grottig ist, sau lahm und dazu auch noch mit kleineren Fehlern.
Deswegen muss ich das größtenteils neu schreiben. :)

Das Problem ist aber beim bisherigen Code vorallem die Array-Kopierei gewesen, deswegen hab ich jetzt erstmal mir da Optimierungsmöglichkeiten einfallen lassen. Wenn der Teil schnell ist, dass reicht die Performance für den Prototypen erstmal aus.

/edit: Das ganze gibt es schon fertig, so zum reinschauen ;-) (http://www.developpez.net/forums/d418823/autres-langages/algorithmes/contribuez/image-seam-carving/)

mfg
Der nutzt auch arraycopy. :)
Muss es ja aber eh selbst implementieren, weil der Code generische bzgl. EngerieFunktionen und Seam-Entfernungsstrategie werden soll.

Nasenbaer
2009-07-13, 10:04:53
Hab nochmal ein wenig darüber nachgedacht. ArrayCopy ist doch nicht so dolle - wenn man horizontal was rausschneidet ist es fummelig mit den Indizes zu hantieren. Werde jetzt ein LinkedRegularGrid implementieren. Freu mich schon aufs debugging. :crazy:

Pinoccio
2009-07-13, 11:38:18
wenn man horizontal was rausschneidet ist es fummelig mit den Indizes zu hantieren.Schneidest du abwechselnd horizontal und vertikal? Wenn nicht, dreh doch dein Bild bzw. deine ArrayStruktur nach dem vertikalen verkleinern.

mfg

Nasenbaer
2009-07-13, 12:27:05
Schneidest du abwechselnd horizontal und vertikal? Wenn nicht, dreh doch dein Bild bzw. deine ArrayStruktur nach dem vertikalen verkleinern.

mfg
Derzeit erst horizontal und dan vertikal aber abwechselnd soll später auch imeplementiert werden können.

Ich hab auch nochmal etwas nachgedacht und beim Implementieren des Grids fiel mir auf, dass die Pointer-Jonglirerei sehr aufwändig werden würde. Ich nehme jetzt doch ein einfache 2D Array. Dadurch, dass ich mittels extra Klasse alle relevanten Daten in einem Array speichere spare ich denke ich genug Zeit (im Ursprungscode wurde fürs BildArray und die EnergieArrays jeweils ein eigenes Array angelegt und nach jedem Schnitt umkopiert *gg*).

Wenn ich jetzt was rausschneide, dann setze ich die Array-Zellen auf null. Dann hab ich ne Funktion, die mir die Elemente, die nicht null sind, in ne LinkedList schreibt und die schreibe ich dann zeilenweise in das neue, kleinere Array - mal sehen wie schnell das dann ist. :) Jedenfalls ist das der wohl einfachste Weg.
Ich überlege lieber nochmal bevor ich Blödsinn schreibe. :D

Nasenbaer
2009-07-13, 18:14:42
Nach etwas genauerer Überlegung hab ichs nun doch so gemacht: Ich schneide ein Seam raus (setze die Array-Werte auf Null) und hole mir dann die Werte des 2D-Arrays als einfache Liste. Ich muss es halt nur so machen, dass ich bei vertikalen Schnitten das 2D-Array zeilenweise auslese und bei horizontalen dann von oben nach unten und links nach rechts. Dementsprechend muss ich die dann auch wieder zeilenweise bzw. spaltenweise ins neue, kleiner 2D-Array einfügen.

Das klappt ganz gut und die Aufwand ist überschaubar - optimale bzgl. Laufzeit ist es aber sicher nicht. *g*