Mit welcher programmiersprache/technik werde ich hier schneller

[Hm...]

hi Leute,

ich habe folgenden Java Code:

  
LinkedList<Integer> listNs=new LinkedList();  
		LinkedList<Integer> listOhneNs=new LinkedList();  
		  
		for(int i=0;i<Controller.stations.size();i++)  
		{  
			if(Controller.stations.get(i).tripel.n && (Controller.stations.get(i).tripel.a!=-1 || Controller.stations.get(i).tripel.b!=-1))  
				listNs.add(i);  
			else if(!Controller.stations.get(i).tripel.n)  
				listOhneNs.add(i);  
		}  

mit Controller.stations.size==100.000.000 (Controller.stations ist eine linkedList), diese berechnung dauert sehr, sehr lange.

die klasse NodeData:

  
import java.util.ArrayList;  
import java.util.LinkedList;  
  
public class NodeData {  
  
	public int id;  
	public LinkedList<NodeData> list;  
	public Tripel tripel;  
	  
	public NodeData(int id, Tripel tripel)  
	{  
		this.id = id;  
		this.list = new LinkedList<NodeData>();  
		this.tripel = tripel;  
	}  
}  
  

  
public class Tripel {  
  
	public int a;  
	public int b;  
	public boolean n;  
	  
	public Tripel(){  
		this.a=-1;  
		this.b=-1;  
		this.n=false;  
	}  
	  
	/**  
	 * Ist subset teilmenge von this?  
	 * @param subset  
	 * @return  
	 */  
	public boolean isSubset(Tripel subset)  
	{  
		if(subset.a!=-1)  
		{  
			if(this.a !=subset.a && this.b != subset.b)  
			return false;  
		}  
		if(subset.b!=-1 )  
		{  
			if(this.a !=subset.b && this.b != subset.b)  
			return false;  
		}  
		if(subset.n)  
		{  
			if(!this.n)  
				return false;  
		}  
		return true;  
	}  
}  

gibt es eine möglichkeit das zu "stark" zu beschleundigen? zb über sogenannte "Assembler" oder über C?

ich kenne mich mit den dingen "hinter" einer programmier sprache noch nicht gut aus, daher würde ich mich auch über grundlegende informationen (wie man an solche laufzeit probleme rangeht) sehr freuen.

[unknown]

Wenn du dir Controller.stations.get(i).tripel zwischenspeicherst kannst du ein wenig Laufzeit sparen, aber eine Iteration über 100.000.000 Elemente dauert einfach lange.

Du könntest deine beiden Listen (listNs, listOhneNs) auch schon beim Einfügen in Controller.stations aufbauen, dann ist das ganze vielleicht ein wenig verteilter in der Laufzeit.

[Hm...]

Wenn du dir Controller.stations.get(i).tripel zwischenspeicherst kannst du ein wenig Laufzeit sparen, aber eine Iteration über 100.000.000 Elemente dauert einfach lange.

Du könntest deine beiden Listen (listNs, listOhneNs) auch schon beim Einfügen in Controller.stations aufbauen, dann ist das ganze vielleicht ein wenig verteilter in der Laufzeit.

danke. und wäre ich schneller, wenn ich das zb in C programmieren würde?

[Tron]

hallo,

Du könntest deine beiden Listen (listNs, listOhneNs) auch schon beim Einfügen in Controller.stations aufbauen, dann ist das ganze vielleicht ein wenig verteilter in der Laufzeit.

danke. und wäre ich schneller, wenn ich das zb in C programmieren würde?

probier es doch einfach aus. Ich denke ja, falls du es richtig machst.

[Hm...]

hallo,

Du könntest deine beiden Listen (listNs, listOhneNs) auch schon beim Einfügen in Controller.stations aufbauen, dann ist das ganze vielleicht ein wenig verteilter in der Laufzeit.

danke. und wäre ich schneller, wenn ich das zb in C programmieren würde?

probier es doch einfach aus. Ich denke ja, falls du es richtig machst.

danke, leider kann ich in C derzeit nichts ausführen. ich habe das hier probiert:

#include <stdio.h>
int main (void) {
printf("Hello world\n");
return 0;
}

in main.c

all: main
clean: rm -f *.o main.exe

in makefile

fehlermeldung:
Description Resource Path Location Type
*** No rule to make target -f', needed by clean'. Test -1 C/C++ Problem
Description Resource Path Location Type
*** No rule to make target \*.o', needed by clean'. Test -1 C/C++ Problem
Description Resource Path Location Type
*** No rule to make target rm', needed by clean'. Test -1 C/C++ Problem

hm...?

[MudGuard]

Hi,

hallo,

Du könntest deine beiden Listen (listNs, listOhneNs) auch schon beim Einfügen in Controller.stations aufbauen, dann ist das ganze vielleicht ein wenig verteilter in der Laufzeit.

danke. und wäre ich schneller, wenn ich das zb in C programmieren würde?

probier es doch einfach aus. Ich denke ja, falls du es richtig machst.

danke, leider kann ich in C derzeit nichts ausführen. ich habe das hier probiert:

#include <stdio.h>
int main (void) {
printf("Hello world\n");
return 0;
}

in main.c

all: main
clean: rm -f *.o main.exe

in makefile

IIRC:

target: dependencies
      command

(vor command ein Tab, keine Leerzeichen!)

cu,
Andreas

[Martin Rettberg]

wäre ich schneller, wenn ich das zb in C programmieren würde?

Deine Fragestellung impliziert, dass du von C bisher nur „gehört“ hast. C lernt man nicht mal eben zwischen Frühstück- und Mittagessen. Lern es ruhig – wenn auch nur zum Spaß –, aber erwarte keine Zauberei von einem _Werkzeug_!

[Alexander (HH)]

Moin Moin!

Deine Fragestellung impliziert, dass du von C bisher nur „gehört“ hast. C lernt man nicht mal eben zwischen Frühstück- und Mittagessen. Lern es ruhig – wenn auch nur zum Spaß –, aber erwarte keine Zauberei von einem _Werkzeug_!

Assembler, Kinder, hochoptimierter Assembler! Denn nur in Assembler kann man sich noch viel effizienter in die Füße schießen als in C.

Im Ernst: Programme in Sprachen, die zur Laufzeit ein paar CPU-Zyklen einsparen, werden von der "langsameren" Sprache auf der nächsten CPU-Generation oft überholt.

Was bleibt also? Zwei oder drei CPU-Generationen aussetzen oder an Algorithmen und Datenstrukturen arbeiten.

Wenn Algorithmen und Datenstrukturen maximal optimiert sind, kann man immer noch zeitkritische Teile nach C oder Assembler portieren. Das bringt aber meist weit weniger Performance-Gewinn als die vorherigen Optimierungsschritte.

Alexander

[Martin Rettberg]

Assembler, Kinder, hochoptimierter Assembler! Denn nur in Assembler kann man sich noch viel effizienter in die Füße schießen als in C.

C
“You shoot yourself in the foot.”

Assembler
“You try to shoot yourself in the foot only to discover you must first reinvent the gun, the bullet, and your foot.”

Im Ernst: Programme in Sprachen, die zur Laufzeit ein paar CPU-Zyklen einsparen, werden von der "langsameren" Sprache auf der nächsten CPU-Generation oft überholt.

„Hardware nachlegen“ ist nicht immer eine Option. Bei vielen eingebetteten Systemen, beispielsweise in der Medizin- und Verkehrstechnik, verlassen wir uns ja schließlich auf ihre Echtzeitfähigkeiten.

Aber prinzipiell hast du Recht; Hardware ist billig und gute Programmierer sind teuer. In der Regel ist sowieso das Netzwerk o. Ä. der Flaschenhals, nicht die Anwendung.

Wenn Algorithmen und Datenstrukturen maximal optimiert sind, kann man immer noch zeitkritische Teile nach C oder Assembler portieren. Das bringt aber meist weit weniger Performance-Gewinn als die vorherigen Optimierungsschritte.

Full ACK.

[Alexander (HH)]

Moin Moin!

Im Ernst: Programme in Sprachen, die zur Laufzeit ein paar CPU-Zyklen einsparen, werden von der "langsameren" Sprache auf der nächsten CPU-Generation oft überholt.

„Hardware nachlegen“ ist nicht immer eine Option.

Exakt, das ist so ziemlich die schlechteste aller Optimierungsmöglichkeiten. Wenn man schon ein extrem ausgefuchstes System hat, und so ziemlich alle anderen Optimierungsmöglichkeiten ausgereizt hat, dann kann das sinnvoll sein. Oder wenn Optimierung auf Neuschreiben hinausläuft und wesentlich länger dauert und teurer wird als stumpf die beste verfügbare Hardware zu kaufen und mit dem aktuellen Stand der Optimierung weiter zu arbeiten.

Manchmal heißt Optimierung auch, den aufwendigen Kern des Problems mit einem oder einigen ASICs oder FPGAs zu erschlagen, die das spezifische Problem schneller als eine Universal-CPU durchrechnen könnnen. Dann sind wir aber schon bei sehr speziellen Problemen.

Aber prinzipiell hast du Recht; Hardware ist billig und gute Programmierer sind teuer.

Richtig. Deswegen sollte man den Programmierern schnelle Hardware zur Verfügung stellen, damit die nicht den ganzen Tag auf Build-Läufe warten müssen. Was aber nicht zwingend heißen muß, dass jeder Programmierer an einer High-End-Workstation arbeiten muß.

Und was ganz sicher nicht heißt, dass Programmierer keine Ahnung von Algorithmen und Datenstrukturen haben müssen und alles per Brute Force erschlagen sollen. Ganz im Gegenteil! Die große Kunst ist, auf einem schnellen Rechner Software zu entwickeln, die auch auf einem langsamen Rechner noch schnell genug ist.

In der Regel ist sowieso das Netzwerk o. Ä. der Flaschenhals, nicht die Anwendung.

Das kommt sehr auf das Problem an, so generell würde ich das nicht sagen.

Alexander

[Alexander (HH)]

Moin Moin!

Was ist Dein eigentliches Problem? Bist Du sicher, dass eine Linked List die optimale Datenstruktur für Dein Problem ist?

Alexander

[Hm...]

Moin Moin!

Was ist Dein eigentliches Problem? Bist Du sicher, dass eine Linked List die optimale Datenstruktur für Dein Problem ist?

Alexander

hi,

bei "arraylist" hatte ich eine heapspace exeption.

ich möchte herausfinden, welche "NodeData", welche anderen "NodeData" in meiner markovkette erreichen können. diese NodeData speichere ich dann in der liste von NodeData als nachbar.

dazu habe ich einen algorithmus entwickelt der in O(n^2/2) läuft. allerdings kann ich meine 100.000.000 node anscheind nichtmal in O(n) durchlaufen ohne stunde/tage lang warten zu müssen (habs bisher nur 20 min laufen lassen).

[dedlfix]

Tach!

bei "arraylist" hatte ich eine heapspace exeption.

Hattest du die gleich mit einer Kapazität etwas größer als der zu erwartenden Elementeanzahl angelegt, oder durft sie sich beim Hinzufügen von Elementen immer wieder neuen Speicher anfordern und sich umkopieren?

dedlfix.

[Hm...]

danke für die antworten, da muss ich drüber nachdenken

Tach!

bei "arraylist" hatte ich eine heapspace exeption.

Hattest du die gleich mit einer Kapazität etwas größer als der zu erwartenden Elementeanzahl angelegt, oder durft sie sich beim Hinzufügen von Elementen immer wieder neuen Speicher anfordern und sich umkopieren?

dedlfix.

ich starte das programm direkt mit -Xmx16000M, falls du das meinst.

das mit der baumstruktur werde ich mir überlegen, ich habe das gefühlt, dass das eine gute lösung sein könnte :)

[Alexander (HH)]

Moin Moin!

bei "arraylist" hatte ich eine heapspace exeption.

Hattest du die gleich mit einer Kapazität etwas größer als der zu erwartenden Elementeanzahl angelegt, oder durft sie sich beim Hinzufügen von Elementen immer wieder neuen Speicher anfordern und sich umkopieren?

dedlfix.

ich starte das programm direkt mit -Xmx16000M, falls du das meinst.

Dedlfix spielt auf ArrayList(int initialCapacity) bzw ArrayList.ensureCapacity() an, und wohl insbesondere auf den folgenden Satz aus der Dokumentation:

"An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation."

ArrayList dürfte auf 2.147.483.647 Einträge begrenzt sein, weil dann nämlich der Datentyp int überläuft. Das wird Dich bei etwas größeren Datenmengen vermutlich auch noch beißen.

Alexander

[Alexander (HH)]

Moin Moin!

hi,

bei "arraylist" hatte ich eine heapspace exeption.

Noch einmal: Denkst Du, dass eine Liste die optimale Datenstruktur für deine Daten ist?

Die Exception dürfte in der Implementation von ArrayList begründet sein, was vermutlich beim Wachsen ein neues Array anlegt und die Daten des alten Arrays rüberkopiert. Ist das Array größer als der freie Heap, kann kein neues, größeres Array mehr angelegt werden. Mit anderen Worten: Im Worst Case kann ArrayList nur den halben zur Verfügung stehenden Speicher nutzen.

Java hat hier ein Philosophie-Problem: Dem Programmierer werden alle möglichen Werkzeuge zur Verfügung gestellt, jedes hoch spezialisiert und jedes mit individuellen Einschränkungen. Es ist Job des Programmierers, diese Details zu kennen (bzw. in der Doku nachzulesen) und das zur jeweiligen Anforderung des Projekts passende Werkzeug auszuwählen. Andere Sprachen nehmen dem Programmierer diesen Job ab, es gibt dann z.B. stumpf ein generisches Ding namens Array, das so ziemlich alles erschlägt, was Java hinter Arrays, Listen, Vektoren und Kollektionen versteckt. Allerdings ist der Maschinencode hinter nicht für jeden Anwendungsfall optimal, und der Programmierer hat selten Möglichkeiten, an Implementationsdetails zu drehen. Dafür hat er Zeit, sich um die wirklich wichtigen Dinge zu kümmern, statt über 20 verschiedenen mehr oder weniger geeigneten Pseudo-Array-Konstrukten zu brüten.

ich möchte herausfinden, welche "NodeData", welche anderen "NodeData" in meiner markovkette erreichen können. diese NodeData speichere ich dann in der liste von NodeData als nachbar.

[Deine Shift-Taste setzt aus.]

Deine Nodes haben eindeutige IDs, richtig?

Und für eine Verbindung zwischen zwei Nodes kannst Du auch IDs vergeben, im einfachsten Fall abgeleitet aus den beiden Nodes.

Wenn Du nach diesen IDs suchen willst, ist eine unsortierte Liste so ziemlich der Worst Case. Natürlich ist sie schnell aufgebaut, aber katastrophal bei der Suche.

Sortiert kombiniert mit einer binären Suche wird's schon schneller. Du mußt einmalig beim Aufbau der Liste etwas mehr Aufwand treiben, den Du dann aber bei der Suche wiederholt einsparst.

Bäume solltest Du auch in Betracht ziehen.

Alexander

[Alexander (HH)]

Moin Moin!

Um mal einen Zaunpfahl zu schwenken: In Baumstrukturen kann man nach Schlüssel-Werten dramatisch viel schneller suchen als in Listen.

Und noch eines:

  
                for(int i=0;i<Controller.stations.size();i++)  
                {  
                        if(Controller.stations.get(i).tripel.n && (Controller.stations.get(i).tripel.a!=-1 || Controller.stations.get(i).tripel.b!=-1))  
                                listNs.add(i);  
                        else if(!Controller.stations.get(i).tripel.n)  
                                listOhneNs.add(i);  
                }  

Du ruft hier Controller.stations.get(i) bis zu vier Mal pro Durchlauf auf, wo ein einziger Aufruf reichen würde:

  
                for(int i=0;i<Controller.stations.size();i++)  
                {  
                        Tripel t=Controller.stations.get(i).tripel;  
                        if(t.n && (t.a!=-1 || t.b!=-1))  
                                listNs.add(i);  
                        else if(!t.n)  
                                listOhneNs.add(i);  
                }  

Tadaa! 300.000.000 Aufruf von Controller.stations.get(i) eingespart, und nebenbei wird der Code auch noch kürzer und lesbarer.

Dann noch merken, dass das zweite if so nicht sein muß, und ein paar Klammern für die Lesbarkeit dazu:

  
                for(int i=0;i<Controller.stations.size();i++)  
                {  
                        Tripel t=Controller.stations.get(i).tripel;  
                        if (t.n) {  
                                if (t.a!=-1 || t.b!=-1) {  
                                    listNs.add(i);  
                                }  
                        } else {  
                                listOhneNs.add(i);  
                        }  
                }  

Alexander

[Christopher]

Hi,

  

> for(int i=0;i<Controller.stations.size();i++)  
> {  
>     Tripel t=Controller.stations.get(i).tripel;  
>     if (t.n) {  
>         if (t.a!=-1 || t.b!=-1) {  
>             listNs.add(i);  
>         }  
>     } else {  
>         listOhneNs.add(i);  
>     }  
> }  

Sehr schön. Und dem Clean-Code-Pattern folgend, hier eine Lösung ohne verschachtelte Anweisungen und mit einem klareren Kontrollfluss (*):

  
for(int i=0;i<Controller.stations.size();i++)  
{  
    Tripel t=Controller.stations.get(i).tripel;  
  
    if (!t.n) {  
        listOhneNs.add(i);  
	continue;  
    }  
  
    if (t.a!=-1 || t.b!=-1) {  
        listNs.add(i);  
    }  
}  

Und als Einzeiler mittels Ternary-Operation, aber in der Tat schlechter lesbar (*):

  
for(int i=0;i<Controller.stations.size();i++)  
{  
    Tripel t=Controller.stations.get(i).tripel;  
    (!t.n) ? listOhneNs.add(i) : (t.a!=-1 || t.b!=-1) ? listNs.add(i) : continue;  
}  

MfG
Christopher

* uncompiled, untested

[dedlfix]

Tach!

if(Controller.stations.get(i).tripel.n && (Controller.stations.get(i).tripel.a!=-1 || Controller.stations.get(i).tripel.b!=-1))
  listNs.add(i);
else if(!Controller.stations.get(i).tripel.n)
  listOhneNs.add(i);
mit Controller.stations.size==100.000.000 (Controller.stations ist eine linkedList), diese berechnung dauert sehr, sehr lange.

Du weißt aber schon, wie eine Linked List aufgebaut ist, und was man tun muss, um das x-te Element zu finden - und das ganze im ungünstigsten Fall auch noch vier Mal?

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

gibt es eine möglichkeit das zu "stark" zu beschleundigen? zb über sogenannte "Assembler" oder über C?

Nimm erst einmal eine Datenstruktur, die besser auf indexierten Zugriff ausgelegt ist. Alternativ lauf mit dem ListIterator durch, der hangelt sich schrittweise an den Elementen entlang, ohne jedes Mal von vorn (oder hinten) zu beginnen. (Vielleicht geht auch foreach, wenn das den ListIterator verwendet.)

Wenn du mit einem Objekt - noch dazu einem, dessen Ermittlung aufwendig ist - mehrere Dinge tun möchtest, solltest du es in einer lokalen Variable ablegen. (Weil es ein Objekt ist, wird das eine Referenz auf das Original.)

Die Folgefrage ist auch noch, ob du wirklich den Index-Wert brauchst, oder ob du nicht eigentliche lieber eine Referenz auf das eigentliche Element in deinen list(Ohne)Ns ablegen willst (und ob das nicht auch einfache statt verlinkter Listen sein können).

dedlfix.

[Whouzuo]

hi Leute,

ich habe folgenden Java Code:

Bitte erstmal fachlich beschreiben, was du da tust. Mir scheint, dein Problem ist mathematischer Natur und lässt sich höchstwahrscheinlich um Größenordnungen schneller lösen als jetzt.
Außerdem bitte _alle_ benutzten Klassen angeben.

[Whouzuo]

hi Leute,

ich habe folgenden Java Code:

Bitte erstmal fachlich beschreiben, was du da tust. Mir scheint, dein Problem ist mathematischer Natur und lässt sich höchstwahrscheinlich um Größenordnungen schneller lösen als jetzt.
Außerdem bitte _alle_ benutzten Klassen angeben.

Achja, und: wir leben im 21. Jahrhundert und können glücklicherweise auf (im Vergleich zu einigen Jahrzehnten) Unmengen an Speicher und CPU Power zurückgreifen. Daher sei doch so nett und gib deinen Variablen vernünftige Variablen und nicht sowas wie "a", "b" oder "n". Die Zeit die du dir sparst, wenn du Abkürzungen (oder gar einzelne Buchstaben) schreibst, wird 100mal wieder dadurch verbraucht, dass niemand versteht, was du da tust.
Vermutlich hätte ich dir bei vernünftigen Variablen jetzt schon die Lösung präsentieren können. ;)