public class Test {
public static void main(String args[]) {
int s = 300000000;
int[] net = new int[s];
}
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...
Du hast es am Anfang mit 300 Millionen statt 3 Milliarden ausprobiertSetze 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?
int i = 3000000000;
long i = 3000000000;
int[] a = new int[i];
long i = 3000000000;
int[] a = new int[(long)i];
int[] a = new int[Integer.MAX_VALUE+1]
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.müsste ich außerdem mit mehreren Arrays der Länge 1 Milliarde umgehen.
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.
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
Oder ein anderer Ansatz.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?
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.
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...Oder gibt es noch eine sparsamere Methode um einen solchen Pfad zu speichern?
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...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
// 0 1 2 3 4 5 6 7 8 9
String zahlen[] = { "nö", "jupp", "nö", "auch nicht", "pah!", "schon eher", "joa", "nee", "ne", "nein" };
Kurz und bündig. Ich fand's verständlich.Ähäm. *räusper*. *kurz überleg*. Aaalso... Ich bin nicht sicher ob ich die Aufgabe verstanden habe, weil
kurz
telegrammstil
unpäzise
Wieso das jetzt? 1 Mrd. passt bequem in ein int.Aber ... so wie ich es verstanden habe: Du wirst wohl long-Werte nehmen müssen.
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 hastUnd ansonsten hat das mit einem Gitter ja nichts zu tun. Wenn du drei Zahlen
so geht es mir nach wie vor... :bahnhof:Ähäm. *räusper*. *kurz überleg*. Aaalso... Ich bin nicht sicher ob ich die Aufgabe verstanden habe, weil
kurz
telegrammstil
unpäzise
fand ich nicht :noe:Kurz und bündig. Ich fand's verständlich.
Was in drei teufels namen ist denn jetzt ein kabel ;(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.
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.Koordinatensystem von 0 bis 1 Milliarde in x und y Richtung.
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 KnotenDarin liegen 100 "Linien" beliebiger Länge die durch zwei Punkte gegeben sind - entweder horizontal oder vertikal (die "Kabel").
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.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.
Das versteh ich jetzt nicht. Zahlen zwischen 0 und 1 Mrd. passen bequem in ints.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.
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:
Kurz und bündig. Ich fand's verständlich.
A B C D
| |
E---F---G---H
| |
I J K L
| |
M N---O---P
|
Q R S T
Ja, aber wenn die Eckpunkte ganzzahlig sind, müssen es die schnittpunkte bei schrägen Strecken nicht mehr sein.Das versteh ich jetzt nicht. Zahlen zwischen 0 und 1 Mrd. passen bequem in ints.
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.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?)
Dem OP wünsch ich dann schonmal viel Spaß bei der Implementierung des Fibonacci heaps :hihi: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:
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).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)
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).
:lol:Marco13 hat gesagt.:Übungsaufgaben für die Vorlesung zu Algorithmen und Datenstrukturen
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).0x7F800000 hat gesagt.:wieso schreibt er die Aufgabe nicht in der einfachen und absolut eindeutigen mathematischen notation hin
Das ist ja eigentlich egal... Solange die Erklärung präzise ist, ist alles ok. Aber momentan ist sie das nicht. :noe: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).
Genau deswegen hasse ich dieses schwammige pseudoanschauliche rumgelaber, wieso schreibt er die Aufgabe nicht in der einfachen und absolut eindeutigen mathematischen notation hin ;(
:bae:
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:
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).Code:A B C D | | E---F---G---H | | I J K L | | M N---O---P | Q R S T
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.
A B C D E F
| |
G H I J K L
| |
M N O P Q R
| |
S T U V W X
B F
| |
H L
| |
N R
| |
T X
A B C D E F
|
G H I J K L
|
M - N - O - P - Q - R
S T U V W X
C
|
I
|
M - O - P