Maximale Länge eines integer Arrays ?

Status
Nicht offen für weitere Antworten.

babuschka

Top Contributor
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
 

Schandro

Top Contributor
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

Top Contributor
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:
Java:
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
 

Schandro

Top Contributor
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:
Code:
int i = 3000000000;
nimmt der Compiler nicht an, eben da es über den Maximalwert von Integer liegt
Java:
long i = 3000000000;
int[] a = new int[i];
Nimmt er nicht an, da er das long nicht zu nem int casten kann.
Java:
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
Java:
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^^
 
Zuletzt bearbeitet:

babuschka

Top Contributor
@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

Bekanntes Mitglied
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

Top Contributor
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

Top Contributor
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
 
Zuletzt bearbeitet von einem Moderator:

tfa

Top Contributor
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

Top Contributor
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

Top Contributor
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

Top Contributor
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

Top Contributor
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... :rolleyes:
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... :eek:

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? ;)
 
Zuletzt bearbeitet:

babuschka

Top Contributor
@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

Top Contributor
Ä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
Code:
//                    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

Top Contributor
Ä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

Top Contributor
Ä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:
Kurz und bündig. Ich fand's verständlich.
fand ich nicht :noe:

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

Top Contributor
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

Top Contributor
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 :eek:
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

Top Contributor
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

Top Contributor
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
Code:
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

Top Contributor
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:
kabele.jpg

(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:
 
Zuletzt bearbeitet:

FatFire

Bekanntes Mitglied
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
 

0x7F800000

Top Contributor
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

Bekanntes Mitglied
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

Top Contributor
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

Top Contributor
Ein Dankeschön an alle für die weiteren Antworten ! :)

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:
Code:
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 graph.getDistance(I,Q) bekommt man die Entfernung 0 (wegen 0 Überschneidungen) , und bei der Abfrage graph.getDistance(I,K) 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.

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
Code:
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
Code:
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:
Code:
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
Code:
    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

Top Contributor
Äää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
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
F Maximale Länge eines Strings Java Basics - Anfänger-Themen 5
R maximale Länge des INHALTS im JTextField Java Basics - Anfänger-Themen 2
M Maximale String länge finden? Java Basics - Anfänger-Themen 8
T Maximale Anzahl von Konsonanten im String Java Basics - Anfänger-Themen 6
RudiRüssel maximale Anzahl von Schlüsseln in einer Hash Tabelle Java Basics - Anfänger-Themen 2
E Maximale KM-Kosten Java Basics - Anfänger-Themen 20
B substring() maximale Zeichenlänge festlegen? Java Basics - Anfänger-Themen 1
D Maximale Teilsumme ermitteln Java Basics - Anfänger-Themen 6
A Maximale zeichenanzahl im TextField? Java Basics - Anfänger-Themen 4
A Threads Minimale und maximale Anzahl. Java Basics - Anfänger-Themen 28
Q jTextArea maximale Textlänge Java Basics - Anfänger-Themen 3
G maximale Anzahl der Tage im Monat Java Basics - Anfänger-Themen 18
N Maximale Zahl in einem String Java Basics - Anfänger-Themen 8
T Methoden Maximale Ziffer von int-Wert Java Basics - Anfänger-Themen 8
M Maximale Anzahl von add-Befehlen? Java Basics - Anfänger-Themen 11
B maximale Zeichenfläche Java Basics - Anfänger-Themen 3
Q Maximale Eingabelänge eines JTextFields Java Basics - Anfänger-Themen 2
G Maximale Größe von klasse Java Basics - Anfänger-Themen 7
G JTextField Abfrage auf maximale Integergröße? Java Basics - Anfänger-Themen 17
Franky868 JTextfield maximale Zeichenanzahl Java Basics - Anfänger-Themen 1
G Maximale Fenstergröße eines JFrame Java Basics - Anfänger-Themen 4
P Maximale Threadzahl Java Basics - Anfänger-Themen 10
G jedem while element eine maximale rechenzeit zusichern Java Basics - Anfänger-Themen 16
N maximale Anzahl Schlüssel in einem Hashtable Java Basics - Anfänger-Themen 7
M Länge eines Arrays als Variable speichern möglich? Java Basics - Anfänger-Themen 14
H Liste nach String-Länge sortieren Java Basics - Anfänger-Themen 1
D Länge einer Liste aufrufen. Java Basics - Anfänger-Themen 19
S Die durchschnittliche Länge der Strings Java Basics - Anfänger-Themen 11
Hzrfa Länge der längsten Kette java Java Basics - Anfänger-Themen 56
BeginnerJava String mit vorgegebener Länge und Buchstaben erzeugen/ mit Leerstellen Java Basics - Anfänger-Themen 8
JavaBeginner22 Wort mit der größten Länge ausgeben Java Basics - Anfänger-Themen 4
I Array Länge in Klasse festlegen Java Basics - Anfänger-Themen 1
Csircc Neuer Array mit geringerer Länge und selben werten. Java Basics - Anfänger-Themen 2
P Länge des längsten möglichst klein Java Basics - Anfänger-Themen 2
districon 2D Array - Länge zuweisen Java Basics - Anfänger-Themen 1
t2im Java Array-Länge ändern? Java Basics - Anfänger-Themen 22
W Best Practice Tabulatoren verschiedener Länge ersetzen Java Basics - Anfänger-Themen 8
H Klassen Die Länge einer Text-Node bestimmen Java Basics - Anfänger-Themen 2
J Objekt-Array dynamischer Länge aus Benutzereingaben erstellen Java Basics - Anfänger-Themen 6
G Variablen Array Länge über den Konstruktor definieren Java Basics - Anfänger-Themen 4
M Strings mit gerader und ungerader Länge ausgeben Java Basics - Anfänger-Themen 10
N Länge eines Arrays in einem Objekt testen Java Basics - Anfänger-Themen 51
L Zwei sortierte Subarrays mit gleicher Länge zusammenfügen Java Basics - Anfänger-Themen 2
A Arrays kombinieren (länge eines Arrays kann 0 sein) Java Basics - Anfänger-Themen 6
S Java Array Länge aus anderer Klasse lesen Java Basics - Anfänger-Themen 1
O Länge eines Arrays Java Basics - Anfänger-Themen 6
M Die länge von char Java Basics - Anfänger-Themen 6
A Best Practice Undefinierte länge bei arrays Java Basics - Anfänger-Themen 4
E Array-list mit einer bestimmten Länge Java Basics - Anfänger-Themen 17
L Länge der dritten Dimension eines dreidimensionalen Arraya Java Basics - Anfänger-Themen 1
T Länge einer Textdatei Java Basics - Anfänger-Themen 11
C Array - Länge dynamisch übergeben Java Basics - Anfänger-Themen 7
N Array mit unbestimmter länge Java Basics - Anfänger-Themen 12
T String länge messen in mm Java Basics - Anfänger-Themen 1
M Generierter Tannenbaum - String Länge Java Basics - Anfänger-Themen 1
T String/int länge Java Basics - Anfänger-Themen 2
I Länge von mehrdimensionalen Array Java Basics - Anfänger-Themen 5
A Länge Substring Java Basics - Anfänger-Themen 1
D Zweidimensionales Array (Länge) Java Basics - Anfänger-Themen 2
S Listnode Länge Java Basics - Anfänger-Themen 2
shiroX Input/Output Array erstellen / Länge Java Basics - Anfänger-Themen 3
Z Erste Schritte Einlesen der Länge eines Feldes Java Basics - Anfänger-Themen 25
G Erste Schritte berechne länge von einträgen Java Basics - Anfänger-Themen 5
S Länge einer Zahl Java Basics - Anfänger-Themen 18
C Datentypen Array-Einträge überhalb der Array-Länge - welcher Wert? Java Basics - Anfänger-Themen 5
M Strings mit variabler Länge auffüllen Java Basics - Anfänger-Themen 6
J Alle Wörter der Länge n mit 0 und 1 Java Basics - Anfänger-Themen 17
S Länge eines Elements im String Array Java Basics - Anfänger-Themen 5
C Datentypen Array mit dynamischer Länge? Java Basics - Anfänger-Themen 14
M Länge der Strecke zwischen zwei Punkten Java Basics - Anfänger-Themen 10
P länge von array abfragen? Java Basics - Anfänger-Themen 2
D Erste Schritte Warum wird bei einem Array die Länge über Length ausgegeben? Java Basics - Anfänger-Themen 6
S Länge eines zweidimensionalen Feldes Java Basics - Anfänger-Themen 3
M Länge String Java Basics - Anfänger-Themen 3
A Länge einer Hexadezimalzahl in Bits Java Basics - Anfänger-Themen 40
P String- Länge Java Basics - Anfänger-Themen 3
A Klassen Eigene Datenklasse - Strings mit fixer Länge Java Basics - Anfänger-Themen 2
E Länge eines spez. Arrays Java Basics - Anfänger-Themen 10
E Länge eines Feldes ausgeben Java Basics - Anfänger-Themen 13
Gossi Datentypen Länge von Zahlentypen Java Basics - Anfänger-Themen 3
V Warten bis die Länge eines Strings nicht mehr 0 ist Java Basics - Anfänger-Themen 13
G Array mit zufälliger Länge Java Basics - Anfänger-Themen 4
D prüfen ob länge eines Arrays == 0 Java Basics - Anfänger-Themen 4
S Datentypen String mit fester Länge (Rückgabewert einer Methode) Java Basics - Anfänger-Themen 2
D Array anlegen ohne bekannte Länge? Java Basics - Anfänger-Themen 6
J Länge eines long wertes Java Basics - Anfänger-Themen 13
S ArrayList länge lässt sich nicht voreinstellen Java Basics - Anfänger-Themen 10
F String begrenzte Länge??? Java Basics - Anfänger-Themen 16
N List länge Java Basics - Anfänger-Themen 6
DStrohma Binärwörter der Länge n ausgeben Java Basics - Anfänger-Themen 3
G Länge eines Integers ermitteln? Java Basics - Anfänger-Themen 38
A array und seine länge Java Basics - Anfänger-Themen 5
G länge von string, string aus integer/char Java Basics - Anfänger-Themen 6
G Länge einer Enumeration feststellen Java Basics - Anfänger-Themen 15
T Länge von Strings im Array vergleichen Java Basics - Anfänger-Themen 2
N Array bei unbekannter Länge Java Basics - Anfänger-Themen 4
M unerklärbarer Fehler bei Array-Länge Java Basics - Anfänger-Themen 4
R Frage zur Länge von Textfeld und String Java Basics - Anfänger-Themen 4
G Warum hat char die Länge 2? Java Basics - Anfänger-Themen 9
G Länge eines Array trimmen oder dynamisch verändern. Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben