# Maximale Länge eines integer Arrays ?



## babuschka (23. Aug 2009)

Hallo,

ich würde gerne wissen, wieviele Elemente ein integer array maximal fassen kann?

Also was ist der maximal erlaubt Wert s für
int[] a = new int;   ?

Gibt es diesbezüglich überhaupt eine Beschränkung oder hängt das vom verfügbaren Speicher ab?


Schöne Grüße


----------



## gizmo (23. Aug 2009)

Zum Arrayzugriff benutzt du einen int, ich gehe davon aus, die grösse von int ist das Limit.


----------



## Schandro (23. Aug 2009)

Falls du genug RAM zur Verfügung haben solltest um ein Array mit 2,1 Milliarden Elementen zu speichern: mach halt ein 2Dimensionales Array draus, dann sinds 1,84*10^19 mögliche Elemente...


----------



## babuschka (23. Aug 2009)

Danke für die schnelle Antwort.

So ein integer Wert reicht ja bis etwa 2 Milliarden im positiven Bereich.
Daher habe ich mal ein Beispiel gemacht:

```
public class Test {
  public static void main(String args[]) {
    int s = 300000000;
    int[] net = new int[s];
}
```

Das führt bei mir leider zu einer Fehlermeldung:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Test.main(Test.java:15)


Setze ich den Wert von s auf etwa 100.000.000, so funktioniert es noch.
Jetzt bin ich mir unsicher, mein Rechner einen so großen Array nicht packt, oder ob es doch eine Begrenzung von seiten Java gibt die niedriger als der maximale integer Wert liegt?

Schöne Grüße


----------



## babuschka (23. Aug 2009)

Schandro hat gesagt.:


> Falls du genug RAM zur Verfügung haben solltest um ein Array mit 2,1 Milliarden Elementen zu speichern: mach halt ein 2Dimensionales Array draus, dann sinds 1,84*10^19 mögliche Elemente...



Danke für deine Antwort. 

Sieht also so aus als wäre mein RAM zu knapp: -Xms32m  -Xmx1024m  eingesetellt  bei 2 GB RAM.


----------



## Schandro (23. Aug 2009)

> Setze ich den Wert von s auf etwa 100.000.000, so funktioniert es noch.
> Jetzt bin ich mir unsicher, mein Rechner einen so großen Array nicht packt, oder ob es doch eine Begrenzung von seiten Java gibt die niedriger als der maximale integer Wert liegt?


Du hast es am Anfang mit 300 Millionen statt 3 Milliarden ausprobiert 

Damit du es nicht selber ausprobieren musst:

```
int i = 3000000000;
```
 nimmt der Compiler nicht an, eben da es über den Maximalwert von Integer liegt

```
long i = 3000000000;
int[] a = new int[i];
```
Nimmt er nicht an, da er das long nicht zu nem int casten kann.

```
long i = 3000000000;
int[] a = new int[(long)i];
```
Nimmt er zwar an, aber dann wird mit 2,1.. Milliarden gerechnet da das long abgerundet werden muss um zum int gecastet zu werden

```
int[] a = new int[Integer.MAX_VALUE+1]
```
Nimmt er nicht an, da Integer.MAX_VALUE+1 eine negative Zahl (um genau zu sein: Integet.MIN_VALUE) ist...


Ergo => geht imho net^^


----------



## babuschka (23. Aug 2009)

@Schandro: Danke für die Antwort !

Das mit den 300 Millionen war Absicht. 
300 Millionen sollte ja theoretisch funktionieren, aber bereits da bekomme ich die Fehlermeldung 
"Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Test.main(Test.java:15)"
um die Ohren geworfen.

Das bedeutet dann wohl, dass mein Hauptspeicher nicht ausreicht.

In meinem Programm, dass ich schreiben möchte, müsste ich außerdem mit mehreren Arrays der Länge 1 Milliarde umgehen. Gibt es noch einen Weg was am Speicher zu tricksen? Gibt es sowas wie automatische Auslagerungen auf Festplatte ?


Schöne Grüße


----------



## FatFire (24. Aug 2009)

> müsste ich außerdem mit mehreren Arrays der Länge 1 Milliarde umgehen.


Wtf?!?...ähm, müssen die denn zwangsweise auch im Speicher liegen? Eine automatische Auslagerung auf die Festplatte gibt es nicht, das müsstest Du Dir schon selbst basteln. Aber was zum Geier machst Du mit den Arrays, wenn man fragen darf? Ich kann mir auf die Schnelle wirklich keinen vernünftigen Grund aus den Fingern saugen, mit soviel Werten auf einmal zu hantieren.

Gruß FatFire


----------



## Landei (24. Aug 2009)

JLS 10.4


> arrays must be indexed by int values; short, byte, or char values may also be used as index values because they are subjected to unary numeric promotion (§) and become int values. An attempt to access an array component with a long index value results in a compile-time error.


----------



## babuschka (26. Aug 2009)

FatFire hat gesagt.:


> Wtf?!?...ähm, müssen die denn zwangsweise auch im Speicher liegen? Eine automatische Auslagerung auf die Festplatte gibt es nicht, das müsstest Du Dir schon selbst basteln. Aber was zum Geier machst Du mit den Arrays, wenn man fragen darf? Ich kann mir auf die Schnelle wirklich keinen vernünftigen Grund aus den Fingern saugen, mit soviel Werten auf einmal zu hantieren.
> 
> Gruß FatFire



Meine Aufgabe ist es ein Programm zu schreiben, dass auf einem quadratischen Gitternetz mit s Spalten/Zeilen operiert. Dabei ist 0 < s < 1.000.000.000 .
In der Aufgabe muss ich grob gesagt bestimmte "Pfade" finden. Um nun einen Pfad zu speichern war mein erster Gedanke jeden Punkt des Pfades in diesem Gitternetz (aufgefasst als Koordinatensystem) in einen Array oder Vector zu packen.  Auf diesem Pfad wird dann weiter operiert.

Da das aber aufgrund des Speichers zur Überlastung führt, hilft wohl nur eine Auslagerung z.b. in eine Datei. Leider wird das wohl sehr auf die Laufzeit drücken... : -/

Schöne Grüße,
Rouven


----------



## tfa (26. Aug 2009)

> hilft wohl nur eine Auslagerung z.b. in eine Datei.


Oder ein anderer Ansatz.
Wie kommen denn die Daten in das Gitternetz, bzw. wie sehen die aus? Ist es vielleicht eine spärlich besetzte Matrix? Kann man die Daten statt in einer Matrix in eine Liste oder sonstige Datenstruktur speichern?


----------



## babuschka (26. Aug 2009)

tfa hat gesagt.:


> Oder ein anderer Ansatz.
> Wie kommen denn die Daten in das Gitternetz, bzw. wie sehen die aus? Ist es vielleicht eine spärlich besetzte Matrix? Kann man die Daten statt in einer Matrix in eine Liste oder sonstige Datenstruktur speichern?



Es gibt in dem Gitternetz vertikale und horizontale Linien, von denen man per Textdatei den Start- und Endpunkt bekommt. Das dürfen höchstens 100 sein, also nicht so wahnsinnig viele im Vergleich zur größe des Gitternetzes.
Die Daten über die Kabel habe ich durch die Start- und Endpunkte beschrieben gespeichert, nicht als Array der jeden Punkt (also auch die dazwischenliegenden) erfasst.
Das Gitternetz selbst ist somit gar nicht als Matrix gespeichert vorhanden.

Das Problem ist, dass ich einen Pfad (der sehr eckig sein könnte) durch das Gitternetz speichern muss, d.h. hier werden viele Eckpunkte (maximal rund 1 Milliarde) zusammenkommen. Gibt es dafür eine Alternative als diese in einem array zu speichern? Stehe etwas auf der Leitung. :-/

Schöne Grüße,
Rouven


----------



## tfa (26. Aug 2009)

Warum kann der Pfad eine Milliarde Eckpunkte haben? 
Ich nehme an, du willst einen Pfad finden, der nicht mit den Gitternetzlinien kollidiert. Bei höchstens 100 sollte der nicht so "kurvig" sein müssen.


----------



## babuschka (26. Aug 2009)

tfa hat gesagt.:


> Warum kann der Pfad eine Milliarde Eckpunkte haben?
> Ich nehme an, du willst einen Pfad finden, der nicht mit den Gitternetzlinien kollidiert. Bei höchstens 100 sollte der nicht so "kurvig" sein müssen.



Der Pfad soll zwei gegebene Punkte verbinden und dabei eine minimale Anzahl an Überschneidungen haben.

Ja, du hast recht. So eckig wird es dann doch wieder nicht. 
Speichert man also nur die Eckpunkte und nicht die dazwischenliegenden Punkte, so spart man sich einiges. Bleibt dann nur zu hoffen, dass es nicht zu eckig wird und sich noch im Rahmen hält. Oder gibt es noch eine sparsamere Methode um einen solchen Pfad zu speichern?

Schöne Grüße,
Rouven


----------



## 0x7F800000 (27. Aug 2009)

Rouven hat gesagt.:


> Oder gibt es noch eine sparsamere Methode um einen solchen Pfad zu speichern?


Ich hab mir jetzt den gesamten Thread fleißig durchgelesen, und ich kann mir leider immer noch keinen Reim draus machen... Kannst du bitte kurz & klar erklären, worum es in deiner Anwendung geht? Ich habe irgendwo "Kabel" gelesen. Wenn es um irgendwelche kabel in einem Gelände / Gebäude / Fahrzeug / Computer geht, kann es absolut unmöglich sein, dass da irgendwelche Pfade mit 1 Mrd. Knoten auftauchen, erst recht nicht mit 10^18 Knoten. In einem Microchip haben die Transistoren Ausmaße von ~50 nanometer ( also 50^10-9 meter), selbst wenn dein Pfad sogar solche Größenordnungen erfasst, dann wäre die verkabelung 50*10^9 meter lang, das wären immer noch ~130 Mal zum Mond und zurück... 


Rouven hat gesagt.:


> Meine Aufgabe ist es ein Programm zu schreiben, dass auf einem quadratischen Gitternetz mit s Spalten/Zeilen operiert. Dabei ist 0 < s < 1.000.000.000


Um was damit zu machen? Um sowas abzuspeichern bräuchtest du 4*10^18 Bytes, wenn du so eine Speichereinheit aus 1-Terabyte festplatten zusammenbauen würdest, wäre das ein Würfel 20x20x20 meter lang, breit und hoch... Und das würde so einiges kosten^^ Um jedes einzelne feld mit einem 1GHZ prozessor einfach nur einmal auszulesen, bräuchtest du etwa 3 jahre, von irgendwelchen Algorithmen ganz zu schweigen... 

Also: was du hier erzählst klingt extremst abgehoben und von der realität fern... Worum geht's? Willst du 5 Steckdosen und 3 rechner in deinem Zimmer verkabeln?


----------



## babuschka (27. Aug 2009)

@0x7F800000: Erst einmal viele Dank für das ausführliche Durchlesen. 

Ja, du hast vollkommen Recht, die Aufgabe ist fern von der Realität. 
Es ist eine fiktive Aufgabe aus der Uni, die ich hier eigentlich nicht besonders breit treten wollte, da ich meine "Hausaufgaben" selbst machen sollte. ;-) Aber es geht wohl nicht anders.. ;-)

Meine Aufgabe lautet:
Quadratisches Gitternetz bis zu 1 Milliarde vertikale/horizontale Linien.
100 "Kabel" die bereits eingezeichnet sind.
2 Punkte gegeben -> Pfad finden, die die 2 Punkte verbinden mit minimaler Überschneidung.

Der Kniff an der Aufgabe ist gerade die Größe (!).
Also ich denke mir nicht aus Spass solche merkwürdigen Aufgaben aus. ;-)
Daher suche ich nun nach einer möglichst sparsamen Methode zur Speicherung des Pfades (ganz zu schweigen vom Finden des Pfades!)

Vorallem bei naiver Heransgehenweise per Brute Force wäre das auf einem normalen Rechner in mehreren Jahre nicht durchführbar.

Also bisher fiel mir für einen Pfad nur ein, die Ecken zu speichern, um so möglichst viele Punkte die dazwischen liegen nicht extra speichern zu müssen. Könnte allerdings trotzdem recht groß werden... :-/


Schöne Grüße,
Rouven


----------



## Marco13 (27. Aug 2009)

Ähäm. *räusper*. *kurz überleg*. Aaalso... Ich bin nicht sicher ob ich die Aufgabe verstanden habe, weil
kurz
telegrammstil
unpäzise

Aber ... so wie ich es verstanden habe: Du wirst wohl long-Werte nehmen müssen. 
Und ansonsten hat das mit einem Gitter ja nichts zu tun. Wenn du drei Zahlen zwischen 0 und 10 speichern willst, z.B. 1, 5 und 6, dann legst du dir ja auch kein String-Array an

```
//                    0      1      2        3          4          5          6      7     8       9
String zahlen[] = { "nö", "jupp", "nö", "auch nicht", "pah!", "schon eher", "joa", "nee", "ne", "nein" };
```

Du rechnest zwar auf irgendwelchen Koordinaten rum, und ja, die nehmen Werte von 0 bis 1 Mrd. an, und ja, der Pfad kann auch etliche Milliarden Einheiten lang sein, aber... ein Pfad, der von (0,0) bis (1000000000,0) geht braucht gerade mal ca. 32 bytes. Also nichts dramatisches.


----------



## tfa (27. Aug 2009)

Marco13 hat gesagt.:


> Ähäm. *räusper*. *kurz überleg*. Aaalso... Ich bin nicht sicher ob ich die Aufgabe verstanden habe, weil
> kurz
> telegrammstil
> unpäzise


Kurz und bündig. Ich fand's verständlich.


> Aber ... so wie ich es verstanden habe: Du wirst wohl long-Werte nehmen müssen.


Wieso das jetzt? 1 Mrd. passt bequem in ein int.


> Und ansonsten hat das mit einem Gitter ja nichts zu tun. Wenn du drei Zahlen


Richtig. Mit einer Matrix ist man hier auf dem Holzweg. Vielleicht könnte man einen Graph nehmen. Auf jeden Fall eine interessante Aufgabe. @TS: Du kannst ja mal die Lösung posten, wenn du eine hast


----------



## 0x7F800000 (27. Aug 2009)

Marco13 hat gesagt.:


> Ähäm. *räusper*. *kurz überleg*. Aaalso... Ich bin nicht sicher ob ich die Aufgabe verstanden habe, weil
> kurz
> telegrammstil
> unpäzise


so geht es mir nach wie vor... :bahnhof:


tfa hat gesagt.:


> Kurz und bündig. Ich fand's verständlich.


fand ich nicht :noe:



Rouven hat gesagt.:


> Quadratisches Gitternetz bis zu 1 Milliarde vertikale/horizontale Linien.
> 100 "Kabel" die bereits eingezeichnet sind.
> 2 Punkte gegeben -> Pfad finden, die die 2 Punkte verbinden mit minimaler Überschneidung.


Was in drei teufels namen ist denn jetzt ein kabel ;(
Ist das eine Gerade?
Ist es homöomorph zu einem Kreis?
Oder zu einem beschränkten interval?
Oder ist das ein Strahl?
Eine gerade Strecke?
Ein Polygon?
Ein Knoten?
Einfach nur irgendeine stetige Kurve?

Was ist "Kabel"?! ;(


----------



## babuschka (27. Aug 2009)

Sorry, falls ich mich unverständlich ausgedrückt habe. Ich dachte, wenn ich es etwas "natürlichsprachiger" formuliere, ist es klar. 

Nochmal mathematischer:
Koordinatensystem von 0 bis 1 Milliarde in x und y Richtung.
Darin liegen 100 "Linien" beliebiger Länge die durch zwei Punkte gegeben sind - entweder horizontal oder vertikal (die "Kabel").
Gegeben sind zwei Punkte. Die Aufgabe ist es, diese zwei zu verbinden durch einen Pfad (darf beliebig verlaufen, also auch über Ecken, muss nicht eine Linie sein), der eine minimale Anzahl an Überschneidungen mit den vorhandenen Linien aufweist.

So... und nun nochmal zum Speichern des Ergebnispfades ;-)
Ich fasse das Koordinatensystem nicht als Matrix auf, das wäre schon zuviel an Speicherverbrauch.
Schwierigkeiten bereitet der Ergebnispfad (falls bereits ausgerechnet, das wäre dann noch ein Problem ;-) ). Denn der Ergebnispfad könnte sehr "eckig" sein, d.h. selbst wenn man die geradlinigen Stellen im Pfad nur durch die Endpunkte beschreibt, könnten dennoch viele (!) Punkte zustandekommen, die es zu speichern gilt.

Bsp: Ergebnispfad geht über (1, 3) , (1, 5), (10, 5) , usw.  

Wenn ich mir vorstelle, dass der minimale Weg zufällig etwas verzwickt zu erreichen ist, können da schon einige Millionen (?) Ecken zustande kommen. Oder doch nicht? 


Schöne Grüße, Rouven


----------



## 0x7F800000 (28. Aug 2009)

Rouven hat gesagt.:


> Koordinatensystem von 0 bis 1 Milliarde in x und y Richtung.


Dann speichere die vertices als double-Punkte und fertig, das dürfte reichen...  Kannst auch gerne mit exakten rationalen werten rumrechnen: wenn du zwei geraden schneidest, die durch rationale koeffizienten festgelegt werden, dann ist der schnittpunkt auch rational. Drum geht's doch eh nicht.



> Darin liegen 100 "Linien" beliebiger Länge die durch zwei Punkte gegeben sind - entweder horizontal oder vertikal (die "Kabel").


selbst wenn die Kabel sehr lang sind, und auf optimalste weise übereinander gelegt werden, sodass die ebene in möglichst viele Bereiche unterteilt wird, dann wächst die Anzahl der Bereiche wie n(n+1)/2. Dadurch dass die kabel nur vertikal oder horizontal ausgerichtet werden können, müssten es weniger bereiche werden. Dadurch dass es keine unendlich lange geraden sind, sondern strecken, werden es noch weniger bereiche, dafür werden sie aber evtl nicht konvex. Ich hab's jetzt nicht genau nachgerechnet, aber ich denke mal, dass die Anzahl der Knoten des schlimmstmöglichen Pfades durch alle bereiche etwa wie O(n^2) wächst, du solltest also damit rechnen, dass da im allerschlimmsten fall 50000 Knoten rauskommen. da deine Aufgabe besteht, den allerbesten Pfad zu finden, wird die Anzahl der knoten wohl nicht mal dreistellig werden... das ist etwas vollkommen anderes als 10^18 Knoten 


> Gegeben sind zwei Punkte. Die Aufgabe ist es, diese zwei zu verbinden durch einen Pfad (darf beliebig verlaufen, also auch über Ecken, muss nicht eine Linie sein), der eine minimale Anzahl an Überschneidungen mit den vorhandenen Linien aufweist.


Ja, gut, bastel dir halt den dualen Graphen des ganzen, und lass da deinen lieblings-wegsuchalgo druf... Da du anscheinend auch über schnittpunkte der kabel laufen darfst, und es als eine überschneidung zählt, brauchst du nicht ganz genau das, was man unter einem dualen graphen versteht, sondern so einen graphen mit ein paar extra-kanten, die auch über knoten des ursprünglichen graphen laufen.

Was ist das ganze eigentlich? Für eine einzelne Aufgabe aus einer Hausaufgabe hört sich das doch recht kompliziert an, vor allem weil das so eine Grundvorlesung ist, wenn man sich die Fragen so anschaut... Als eine ganze Hausaufgabe für eine Woche würde es schon eher gehen, aber da dürften imho einige dran verzweifeln :autsch:


----------



## tfa (28. Aug 2009)

0x7F800000 hat gesagt.:


> Dann speichere die vertices als double-Punkte und fertig, das dürfte reichen...  Kannst auch gerne mit exakten rationalen werten rumrechnen: wenn du zwei geraden schneidest, die durch rationale koeffizienten festgelegt werden, dann ist der schnittpunkt auch rational. Drum geht's doch eh nicht.


Das versteh ich jetzt nicht. Zahlen zwischen 0 und 1 Mrd. passen bequem in ints.
Und wenn die Kabel nur horizontal und vertikal sein können, gibt's auch keine Bruchzahlen, wenn die sich schneiden (dürfen sie das überhaupt?)



> Was ist das ganze eigentlich? Für eine einzelne Aufgabe aus einer Hausaufgabe hört sich das doch recht kompliziert an, vor allem weil das so eine Grundvorlesung ist, wenn man sich die Fragen so anschaut... Als eine ganze Hausaufgabe für eine Woche würde es schon eher gehen, aber da dürften imho einige dran verzweifeln :autsch:



Ich finde es auch ziemlich schwierig. Welches Semester und welcher Studiengang ist denn das?


----------



## Marco13 (28. Aug 2009)

tfa hat gesagt.:


> Kurz und bündig. Ich fand's verständlich.



Ich könnte jetzt 100 Fragen stellen, deren Antworten nicht aus der Beschreibung hervorgehen - Andrey hat schon ein bißchen angefangen: Was heißt "schneiden"? Können Kabel diagonal liegen? (Offenbar nicht) Kann man diagonal laufen?... 

Dass für 1 Mrd ein int reicht stimmt, aber man nähert sich damit schon dem Grenzbereich: Wenn das _"bis zu"_ 1 Mrd. wirklich _verbindlich_ ist, ist es noch OK, aber bei 1.1 Mrd könnte es schon Probleme geben, wenn man in irgendeinem Zusammenhang (bei irgendeinem ausgefuchsten Algorithmus, warum auch immer) mal die Summe zweier x-Koordinaten braucht oder so...

Ansonsten wäre mein Ansatz jetzt auch ein Graph. Aber eben KEINEN den man sich wirklich aus 1 Mrd x 1 Mrd Objekten der Klasse "Node" und doppelt so vielen der Klasse "Edge" aufbaut und im Speicher hält. Stattdessen (auch, weil die Topologie ja trivial ist) kann man eine Klasse schreiben, die einem die gleichen Informationen liefert, wie ein Graph - also bildlich gesprochen: Die das "Graph"-Interface implementiert. (Hey ... "bildlich"? Ich code zu viel  ). 

Man hat dann also so einen "virtuellen" Graphen, mit den Kabeln

```
A   B   C   D
    |   |
E---F---G---H
    |   |
I   J   K   L
    |   |
M   N---O---P
        |
Q   R   S   T
```
Und der Graph liefert einem für die Abstände zwischen den Knoten eben Gewichte (Längen): Bei der Abfrage [c]graph.getDistance(I,Q)[/c] bekommt man die Entfernung 0 (wegen 0 Überschneidungen) , und bei der Abfrage [c]graph.getDistance(I,K)[/c] bekommt man die Entfernung 1 (wegen 1 Überschneidung). 

Und DORT werden jetzt auch die ganzen Fragen relevant, die nicht in der Beschreibung standen: Ist der Abstand zwischen I und J nun 0 oder 1 (also gilt das "Besuchen" von J schon als Überschniedung der dortigen Linie?) Was ist dann der Abstand zwischen M und N? Ist das 0,1 oder 2? Können mehrere "Kabel" den gleichen Verlauf haben? Als wie viele Überschneidungen gilt das dann?

Wenn alle diese Fragen geklärt sind (->notfalls Tutor fragen) kann man die "Distanzfunktion" noch anpassen, so dass der Abstand zwischen zwei Knoten
1 ist, wenn KEINE Überschneidung vorliegt
1000000000 ist, WENN eine Überschneidung vorliegt
Dann ist das "primäre" Kriterium für den Weg, den man findet, dass er möglichst wenige Überschneidungen hat, und das "sekundäre" Kriterium, dass er auch möglichst kurz ist.

Alles in allem läßt sich die Frage dann mit dem Wort beantworten, dass sich in den letzten Absätzen schon rauskristallisiert hat: *Dijkstra*.


----------



## 0x7F800000 (28. Aug 2009)

tfa hat gesagt.:


> Das versteh ich jetzt nicht. Zahlen zwischen 0 und 1 Mrd. passen bequem in ints.


Ja, aber wenn die Eckpunkte ganzzahlig sind, müssen es die schnittpunkte bei schrägen Strecken nicht mehr sein.


> Und wenn die Kabel nur horizontal und vertikal sein können, gibt's auch keine Bruchzahlen, wenn die sich schneiden (dürfen sie das überhaupt?)


Ich dachte das bezieht sich nur auf die 100 Kabel, die schon da liegen. Den weg darüber dürfte man beliebig wählen, da wäre die Einschränkung auf das ganzzahlige gitter zumindest mal störend.

Im Folgenden beispiel müsste man zum Beispiel mehr knotenpunkte einfügen, wenn man auf dem ganzzahligen gitter bleiben wollte:





(rot sollen die kabel sein, blau ist der sicherste weg über möglichst wenige kabel zwischen den grünen punkten, der Knick liegt nicht mehr auf dem Gitter)



			
				Marco13 hat gesagt.:
			
		

> Alles in allem läßt sich die Frage dann mit dem Wort beantworten, dass sich in den letzten Absätzen schon rauskristallisiert hat: Dijkstra.


Dem OP wünsch ich dann schonmal viel Spaß bei der Implementierung des Fibonacci heaps :hihi:


----------



## Marco13 (28. Aug 2009)

0x7F800000 hat gesagt.:


> Dem OP wünsch ich dann schonmal viel Spaß bei der Implementierung des Fibonacci heaps :hihi:



Ja der soll heftig sein, ich hatte mal 
FibonacciHeap (JGraphT : a free Java graph library)
überflogen, aber bevor man versucht, das selbst zu machen: 
DijkstraShortestPath (JGraphT : a free Java graph library) 
-> "Graph" interface implementieren und fertig


----------



## FatFire (28. Aug 2009)

0x7F800000 hat gesagt.:
			
		

> Den weg darüber dürfte man beliebig wählen, da wäre die Einschränkung auf das ganzzahlige gitter zumindest mal störend.


Störend ja, aber der einzige praktische Einsatzzweck in solchen Maßstäben ist für mich Platinenätztechnik und Chiparchitektur (mag sein, dass es noch mehr gibt, vielleicht bin ich da im Moment auch etwas kurzsichtig), und da kann man halt meist nicht noch dazwischen hauen, weil man schon an der Präzisionsgrenze arbeitet (das erklärt ja auch die irrsinnig oft unterteilten Gitter, dass es 1 Mrd * 1 Mrd ist, einfach weil die Auflösung schon so irrsinnig hoch ist).
Und Dein genanntes Beispiel müsste, auch wenn es hässlich ausschaut, dann so


 oder besser so 

  umgesetzt werden. Wenn man denn das Glück hat, dass es noch nicht so fein aufgelöst ist, dass diagonale Verbindungen nicht möglich sind (kann leider auch vorkommen...).
Aber da dieser Punkt nicht ganz klar ist, können wir da wohl nur mutmaßen (deswegen hasse ich diese theoretischen Herangehensweisen, denn im praktischen Beispiel könnte man auch besser eine klare Arbeitsvorschrift erarbeiten).

Gruß FatFire


----------



## Marco13 (28. Aug 2009)

FatFire hat gesagt.:


> Störend ja, aber der einzige praktische Einsatzzweck in solchen Maßstäben ist für mich Platinenätztechnik und Chiparchitektur (mag sein, dass es noch mehr gibt, vielleicht bin ich da im Moment auch etwas kurzsichtig)



Übungsaufgaben für die Vorlesung zu Algorithmen und Datenstrukturen


----------



## 0x7F800000 (28. Aug 2009)

FatFire hat gesagt.:


> Aber da dieser Punkt nicht ganz klar ist, können wir da wohl nur mutmaßen (deswegen hasse ich diese theoretischen Herangehensweisen, denn im praktischen Beispiel könnte man auch besser eine klare Arbeitsvorschrift erarbeiten).



Genau deswegen hasse ich dieses schwammige pseudoanschauliche rumgelaber, wieso schreibt er die Aufgabe nicht in der einfachen und absolut eindeutigen mathematischen notation hin ;(
:bae:


----------



## FatFire (28. Aug 2009)

Marco13 hat gesagt.:
			
		

> Übungsaufgaben für die Vorlesung zu Algorithmen und Datenstrukturen


:lol:


			
				0x7F800000 hat gesagt.:
			
		

> wieso schreibt er die Aufgabe nicht in der einfachen und absolut eindeutigen mathematischen notation hin


Weil dann Leute wie ich sabbernd und mit Fragezeichen auf der Stirn vor dem Monitor kleben würden und nichts schreiben, weil Sie kein Wort verstanden haben und auch Google daraufhin mehr Verwirrung als Aufklärung liefert (tja, Angewandte Informatiker...wir wissen nicht, wie es funktioniert, wir machen es einfach).

Gruß FatFire


----------



## 0x7F800000 (28. Aug 2009)

FatFire hat gesagt.:


> Weil dann Leute wie ich sabbernd und mit Fragezeichen auf der Stirn vor dem Monitor kleben würden und nichts schreiben, weil Sie kein Wort verstanden haben und auch Google daraufhin mehr Verwirrung als Aufklärung liefert (tja, Angewandte Informatiker...wir wissen nicht, wie es funktioniert, wir machen es einfach).


Das ist ja eigentlich egal... Solange die Erklärung präzise ist, ist alles ok. Aber momentan ist sie das nicht. :noe:


----------



## babuschka (29. Aug 2009)

Ein Dankeschön an alle für die weiteren Antworten ! 



0x7F800000 hat gesagt.:


> Genau deswegen hasse ich dieses schwammige pseudoanschauliche rumgelaber, wieso schreibt er die Aufgabe nicht in der einfachen und absolut eindeutigen mathematischen notation hin ;(
> :bae:



Du hast Recht. Immernoch war die Aufgabenstellung in einigen Punkten zu schwammig. Ich hoffe, ich kann dem Abhilfe schaffen. Hier noch einmal die Zusammenfassung:

Koordinatensystem von 0 bis 1 Milliarde in x und y Richtung (ganzzahlig ! ).
100 "Linien" beliebiger Länge die durch zwei Punkte gegeben sind liegen bereits darin - entweder horizontal oder vertikal (dürfen sich überschneiden !).
Gegeben sind zwei Punkte. Die Aufgabe ist es, diese zwei zu verbinden durch einen Pfad der eine minimale Anzahl an Überschneidungen mit den bisherigen Linien aufweist. Der Pfad darf nur vertikal oder horizontal verlaufen und ebenfalls nur in ganzzahligen Punkten liegen.

Details nach Rücksprache mit Dozenten:
Trifft der Pfad auf einen Endpunkt einer Linie gilt dies auch als Überschneidung.
Trifft der Pfad z.B. auf einen Punkt auf dem bereits zwei (!) Endpunkte bestehnder Linien sind, so gilt das als zweifache Überschneidung.
Der Pfad darf nicht mehr als eine Überschneidung mit einer Linie aufweisen.
Der Pfad darf beliebig verlaufen, muss also nicht der kürzeste im Sinne von Anzahl an Kanten bzw. Knoten sein, sondern nur der kürzeste im Sinne von Anzahl an Überschneidungen.
Obere Grenze des Koordinatensystems ist 1 Milliarde, nichts darüber.

Falls es noch weitere Fragen gibt, einfach Bescheid geben. ;-)



			
				Marco13 hat gesagt.:
			
		

> Ansonsten wäre mein Ansatz jetzt auch ein Graph. Aber eben KEINEN den man sich wirklich aus 1 Mrd x 1 Mrd Objekten der Klasse "Node" und doppelt so vielen der Klasse "Edge" aufbaut und im Speicher hält. Stattdessen (auch, weil die Topologie ja trivial ist) kann man eine Klasse schreiben, die einem die gleichen Informationen liefert, wie ein Graph - also bildlich gesprochen: Die das "Graph"-Interface implementiert. (Hey ... "bildlich"? Ich code zu viel ).
> 
> Man hat dann also so einen "virtuellen" Graphen, mit den Kabeln
> Code:
> ...



Ich verstehe was du mit "virtuellen" Graph meinst. Die Idee hört sich recht gut an, um so das tatsächliche Anlegen von (1 Milliarde)^2 Objekten zu verhindern. 
Für den Dijkstra Algorithmus muss man ja festhalten, welche Knoten bereits besucht wurden bzw. die Summe des bisherigen Verlaufs. Das würde dann für jeden Knoten auf ( 1 Milliarde )^2 hinauslaufen, was für meinen Hauptspeicher zuviel ist (streikt bereits bei int array mit 1 Milliarde Einträgen, auch wenn das theoretisch möglich ist).
Vielleicht könnte man hier den Graph etwas "stutzen" indem man die relativ großen linienlosen Flächen so auffasst als wäre dort kein Knoten dazwischen.

Beispiel: Der folgende Graph

```
A   B   C   D   E   F
    |               |
G   H   I   J   K   L
    |               |
M   N   O   P   Q   R
    |               |
S   T   U   V   W   X
```
wird aufgefasst als

```
B   F
|   |
H   L
|   |
N   R
|   |
T   X
```
Für den "virtuellen" Graph könnte man dazu eine Methode graph.getNeighbourNodes(Position pos) bereitstellen, um sich so alle Nachbarknoten berechnen zu lassen. Die Methode müsste anhand der gespeicherten Eckpunkte der Linien schauen, welche Punkte der Linien erreichbar sind. Dazu müssten sie ausgehend von der gegebenen Position sich in alle Richtungen "vorantasten" bis sie auf eine Linie stößt.

Allerdings könnte ein Knoten dadurch evtl rund 1 Millarde Nachbarknoten besitzen, wenn beispielsweise eine Linie sich komplett von (0, 50) bis (1.000.000.000, 50) durchzieht und der Ursprungsknoten unterhalb dieser Linie liegt.
Eventuell könnte man hier auch wieder abkürzen:
Man fasst alle Knoten einer solchen Linie, bei der sich unmittelbar "davor" und "dahinter" keine weitere Linie befindet als einen Knoten auf.
Befindet sich im obigen Beispiel beispielsweise eine vertikale Linie in (100, 50) / (100, 7000), so würde die horizontale Linie in zwei Teile gesplittet werden, die für die Berechnung der minimalen Anzahl an Überschneidungen relevant sind.

Etwas anschaulicher:

```
A   B   C   D   E   F
        |           
G   H   I   J   K   L
        |           
M - N - O - P - Q - R
                   
S   T   U   V   W   X
```
wird zu 

```
C  
    |           
    I   
    |           
M - O - P
```

Ich hoffe, ich konnte mich halbwegs verständlich ausdrücken und habe euch nicht verwirrt. 
Was haltet ihr davon? Klingt das für euch machbar oder habe ich irgendwo einen entscheidenden Denkfehler gemacht?


Schöne Grüße,
Rouven


----------



## 0x7F800000 (30. Aug 2009)

Ääähm... was ein dualer Graph ist weißt du? *hust*
Das problem unterteilt sich in 2 probleme:

Kürzesten weg mit irgendeinem Wegsuchalgo auf dem dualen Graph finden. Die schätzung hast du ja gesehen: allerhöchstens 10000 Knoten wird er haben, und dazu sehr sehr dünn sein.
Innerhalb jeder Fläche, die zu einem Knoten des dualen Graphen gehört, muss man einen weg auf dem ganzzahligen gitter konstruieren. Wenn man ein bisschen darüber herumhirnt, kann man das recht einfach machen, indem man die Fläche in konvexe Rechtecke zerlegt: innerhalb eines Rechtecks ist es ja total billig von A nach B zu gehen: man gehe einfach in einem "L". Dann muss man das ganze nur noch zusammenkleben fertig...

Reicht's jetzt an Denkanstößen? Ich frag mich mehr denn je, was es denn jetzt ist^^ Immer noch dieselbe hausaufgabe kann's ja nicht mehr sein, da die Woche ja quasi vorbei ist. ???:L


----------

