1000 Threads oder Iterativ?

vimar

Bekanntes Mitglied
Hallo,


ich arbeite derzeit mit 400.000 Objekten.

ich habe eine arraylist mit 1000 objekten, auf die sich die 400.000 objekte aufteilen nach einem algorithmus (kmeans).

beispiel:

Vektoren in Centroid949: 685
Vektoren in Centroid950: 361
Vektoren in Centroid951: 684
Vektoren in Centroid952: 190
Vektoren in Centroid953: 125

bei diesen vektoren handelt es sich um 128 dim vektoren.

für jedes objekt in der arraylist, also für alle objekte pro objekt in der arraylist muss ich mittelwerte bestimmen, abgleichen, neusetzten und wieder in eine gewisse whileschleife bis sie irgendwann breaked.

meine frage:

ich habe als ersten ansatz die arraylist durchlaufen(iterativ), hab also 1000 objekte, die ich sequentiell durchlaufe und dort mittelwerte berechne. hier wird nur ein cpu kern genutzt. im kleintest-format hab ich (anstatt 1000 objekten auf die sich 400.000 verteilen nur 3 objekte auf die sich die 400.000) verteilen eine rechnezeit von: 3m 45s.

2ter und 3ter ansatz(nachgelesen windows "native" threads was perfekt ist denke ich (kann linux wohl scheinbar nicht hehehehehehe(sorry musste sein ;P)) :

im 2ten ansatz: da für jedes objekt die selbe rechnung getätigt wird und die ereignisse auch in diesem schritt unabhängig sind, kam mir die idee mit threads. bei 3 objekten(die die 400.. blabla) hatte ich es so programmiert dass ich 3 threads gleichzeit habe, für jedes objekt 1 thread und mit join() auf die langsamsten gewartet (muss sein!). rechenzeit hier: 1m 45s.

im 3ten ansatz: weil meine cpu 2 kerne hat, war die idee immer nur 2 objekte gleichzeit anzusehen, also immer nur 2 threads zu starten, in dem sinne wenn ich 4 objekte habe, erst die ersten beiden rechnen, dann die nächsten beiden. rechenzeit hier: 2m 20s (für 3 objekte wie in den anderen ansätzen).

------

für mich klingt es komisch, "1000" threads zu erstellen (weil ich ja nun anstatt 3 obj nun 1000 nehme)

da die rechenzeit scheinbar nicht linear sondern exponentiell erscheint, soll ich nun 1000 threads erstellen ODER sequentiell durchlaufen lassen?

sind 1000 threads nicht ein bissl viel?

ich lasse derzeit mein prog laufen mit 1000 threads, das prog läuft seit 12 std und meiner vermutung nach noch so ca. 3 std. blockieren sich sooooo viele threads nicht gegenseitig ohne ende?


allgemeiner ablauf des programmteils:

--
whileschleife
1000 threads erstellen
berechnen
keine änderung = break
eine oder mehr änderungen = wieder in die whileschleife (d.h. wieder 1000 neue threads erstellen)
--




allgemeine settings:

OS: windows 8 customer edition
CPU: E2200 64bit 2,2ghz (2 kerne) oc auf 2,64 ghz , 1 MB lvl 2 cache.
RAM: 7 GB dd2

java settings:
-Xms4000m -Xmx4000m -XX:MaxPermSize=2500m


also 1000 threads gleichzeitig oder sequentiell?

danke für antworten & mfg

vimar
 
Zuletzt bearbeitet:
S

SlaterB

Gast
verwende maximal n=2, 4, 8 Threads oder sowas in der Richtung, angepasst an die CPU-Anzahl,
jeder Thread bekommt dann x/n Objekte, oder lege alle zentral ab und lasse die Thread sich (synchronisiert) welche holen,
solange noch welche da sind,

join() übrigens ruhig immer auf alle Threads aufrufen, dann ist es egal welcher der langsamste ist

x Stunden ohne Information zu warten ist doch dumm, logge zumindest nebenher, wieviel geschafft wurde, je Thread einzeln/ insgesamt,

kannst du mit verschiednen n testen und jeweils eine Stunde laufen lassen und vergleichen und den vielversprechendsten Ansatz dann komplett starten

bei Stunden an Laufzeit machen 1000 Threads einzeln vielleicht auch nicht soviel Overhead,
falls Java nicht komplett durchdreht und die Arbeit ständig wechselt und nichts geschafft wird
 

vimar

Bekanntes Mitglied
so rufe ich derzeit threads auf:

Java:
ArrayList <RCThread> AThread = new ArrayList <RCThread>();

        public rearrangeCentroids(){
            
        }

        public void startRearrange(ArrayList <cluster> ClusterList) throws InterruptedException{
             this.ClusterList = ClusterList;
            changedCentroid1 = false; //// TEEEEEEEEEEEEEEST !!
            AThread.clear();
            for (int i = 0; i < ClusterList.size();i++){ // für alle cluster

                AThread.add((new RCThread(this,ClusterList.get(i),i)));
     
            }
            for (int i = 0; i < ClusterList.size();i++){
                AThread.get(i).start();
            }
 
            for (int i = 0; i < ClusterList.size();i++){
                
                AThread.get(i).join();
            }
               
            }

diese methode rearrangeCentroids wird in einer while aufgerufen, falls ein thread oder mehrere threads einen boolean auf true setzen, wird die while erneut aufgerufen (was sehr oft passiert).

ich denke ich werde deinen ansatz verfolgen, wobei ich mir da noch wissen aneignen muss!
 

Landei

Top Contributor
Eine Alternative zu Threads sind Aktoren, und von denen kannst du durchaus 1000 oder mehr haben. Eine Bibliothek dafür wäre z.B. Akka
 
B

bygones

Gast
oder nutzt Callable struktur in zusammenhang mit Executoren - da musst du das wenigste dich um starten/joinen kuemmern
 
J

JohannisderKaeufer

Gast
im 2ten ansatz: da für jedes objekt die selbe rechnung getätigt wird und die ereignisse auch in diesem schritt unabhängig sind, kam mir die idee mit threads. bei 3 objekten(die die 400.. blabla) hatte ich es so programmiert dass ich 3 threads gleichzeit habe, für jedes objekt 1 thread und mit join() auf die langsamsten gewartet (muss sein!). rechenzeit hier: 1m 45s.

im 3ten ansatz: weil meine cpu 2 kerne hat, war die idee immer nur 2 objekte gleichzeit anzusehen, also immer nur 2 threads zu starten, in dem sinne wenn ich 4 objekte habe, erst die ersten beiden rechnen, dann die nächsten beiden. rechenzeit hier: 2m 20s (für 3 objekte wie in den anderen ansätzen).

Ich denke, hier liegt das Übel des ganzen. kmeans hat nicht nur was mit Berechnung, sondern auch was mit Suche zu tun. Und Dinge, die es nicht gibt, muß man auch nicht suchen.

So wie ich das sehe machst du folgendes.
Du hast 1000 (bzw. 3) Centroids und 400.000 Objekte mit jeweils 128 Merkmalen. Nun berechnest du für jedes Objekt, die Entfernung zu jedem Centroid um dann zu entscheiden welcher der nächste ist.

Das sind 51.200.000.000 Rechenoperationen.

Das Problem ist, dass du für jeden Centroid einen Thread erstellst.(Ob Executor oder Actor ist erstmal egal).

Nehmen wir an du hättest 3 Centroids 10 Objekte und jeweils 4 Merkmale

int[][] centroids = {[1,0,0,0][10,0,0,0][20,0,0,0]};

int[] einObjekt = {2,0,0,0}; //Das erste der 10.

Bisher berechnest du die Abstände zu jedem Centroid und bekommst dieses Ergebnis
int[] abstände = {1, 8, 18};

Meiner Meinung allerdings besser wäre es, den Abstand zum ersten Centroid zu berechnen.
=> Abstand 1 Centroid 1
Und nun nach jeder Berechnung eines Merkmals überprüfen, ob dieser Centroid noch näher sein kann als das gefundene Minimum
Merkmal 1. Objekt = 2, Centroid(2) = 10 => Abstand 8 => 8 > 1 => weitere Berechnung abbrechen, da Centroid 2 nicht mehr in Frage kommt.

Merkmal 1. Objekt = 2, Centroid(3) = 20 => Abstand 18 => 18 > 1 => weitere Berechnung abbrechen, da Centroid 3 nicht mehr in Frage kommt.

Und genau, diese Abbruchbedingung, die man so ähnlich auch in Suchalgorithmen findet nutzt du nicht, wenn du die Berechnung nach Centroids in Threads aufteilst.

Was du machen kannst und solltest, ist die Menge der Objekte in Threads aufteilen.
Sprich bei 2 Threads 200.000 Objekte für Thread A und 200.000 für Thread B.

Denn erst mit dieser Aufteilung kannst du Abbruchbedingungen effektiv nutzen und dir so einen ganzen Haufen an Berechnungen sparen.
 

vimar

Bekanntes Mitglied
@JohannisderKaeufer:

Ich denke mal mit Merkmal bezeichnest du die Dimension eines Vektors ( in deinem fall die position im array)

ich denke nicht dass du recht hast.

begründung:

du hast die zentroiden so gewählt dass nur das erste Merkmal(dimension) von 0 abweicht. die euklidische distanz berechtet sich nicht nur unter beobachtung eines merkmals(einer dimension), sondern ist die die wurzel aus der summe der differenzen der einzelnen dimensionen.

sqrt(9+9) != sqrt(9) + sqrt(9).

sqrt(9+9) = sqrt(81) = 9 ; sqrt(9) + sqrt(9) = 3+3 = 6 ; 9!=6

sqrt(9*9) == sqrt(9)*sqrt(9). (passiert aber bei distanzfunktion nicht)

daher kann ich nicht nach dem ersten abstand den ich berechnet habe für ein merkmal auf die "wirkliche" distanz schliessen.




falls ich dich nicht richtig verstanden habe, bitte erklär etwas deutlicher was du meinst. würde mir sicher sehr helfen danke
 
Zuletzt bearbeitet:
J

JohannisderKaeufer

Gast
Ja, das Beispiel war schon daraufhingedreht, dass es schnell ersichtlich ist um was es geht.
Du hast allerdings 128 merkmale. Das du nicht nach der ersten Dimension abbrechen kannst ist klar aber wenn nach der 64-Dimension schon absehbar ist, das das nichts mehr wird hast du hier schonmal die hälfte gespart.

Im 2-Dimensionalen Raum berechnest du eine entfernung mit sqrt(DeltaX² + DeltaY²)

Um zwei Entfernungen voneinander zu unterscheiden mußt du allerdings nicht die Wurzel ziehen
Bei
Code:
sqrt(DeltaX_1² + DeltaY_1²) < sqrt(DeltaX_2² + DeltaY_2²)

Kann man dass, daraus ableiten
Code:
DeltaX_1² + DeltaY_1² < DeltaX_2² + DeltaY_2²

Wenn dass gilt,
Code:
DeltaX_1² + DeltaY_1² < DeltaX_2²,
dann gilt das unabhängig davon wie DeltaY_2² aussieht.


Für einen Centroid mußt du immer alle Dimensionen berücksichtigen (am Schluß keine Wurzel ziehen!). Bei den weiteren Centroiden kannst du abbrechen, sofern bei den bereits berücksichtigten Dimensionen die Summe größer wird, als beim bereits besten gefundenen Centroiden,

Wobei bemerkt
sqrt(9+9) = sqrt(81) = 9 ; sqrt(9) + sqrt(9) = 3+3 = 6 ; 9!=6
sqrt(9+9) = sqrt(18) = 4,... ; sqrt(9) + sqrt(9) = 3+3 = 6 ; 4,...!=6

Bei kmeans geht es nicht um gleich und ungleich, sondern um größer, kleiner als

sqrt(128 * 1) < sqrt(129 + 127*0)
sqrt(128 * 1) < sqrt(64 + 65+ 126*0)
sqrt(128 * 1) < sqrt(32 + 32 + 65+ 125*0)

Die 128 stehen für die 128 Dimensionen.
Der Abstand in einer Dimension ist immer größer gleich 0.

Und das gilt auch, wenn man das sqrt, wegläßt.
 
J

JohannisderKaeufer

Gast
Nimm deinen Anfangs verwendeten Algorithmus(iterativ) mit den 400.000 Datensätzen und 3 Centroiden.

Nun suche nach den Stellen bei denen du für die Berechnung des Abstandes die Wurzel ziehst.
Kommentier das Wurzelziehen aus und speichere lediglich die Werte ab, die unter der Wurzel stehen. Also die Summe ohne Wurzel!

Laß das Programm laufen und sieh das selbe Ergebnis in einer kürzeren Laufzeit.
Bisher 3m 45s

Das sollte dir zumindest mal ein Beweis sein, daß ich nicht nur Blödsinn schreibe.
 

vimar

Bekanntes Mitglied
@JohannisderKaeufer

Hey, vielen dank! ich habs soweit überprüft und du hast recht. ein guter kumpel und diplommathematiker hat mri bestätigt dass du recht hast, hat irgendwas von strenger monotonie gebabbelt.

allerdings meinte er zu mir ich solle abschätzen ob (x -y)^2 .. (der kram unter der wurzel) nicht langsamer zu berechnen ist als Math.abs(x-y). also der betrag. weg von der euklidischen distanzfunktion hin zur manhatten R^1 distanzfunktion.

muss ich gleich mal testen. ich denke ich werde auf manhattendistanz gehen und eventuell die abbruchklausel einbringen von dir (falls distanz bei centroid 2 mitten in der summenbildung größer als bei gesamter centroid 1 distanzsumme usw).


danke nochmals und mfg vimar
 
J

JohannisderKaeufer

Gast
Klar, kann man verschiedene Variationen zur Berechnung der Distanz heranziehen.

Du mußt dir allerdings bewußt sein, dass das auch andere Ergebnisse zur Folge hat!

Im 2-Dimensionalen raum Object(0,0) Cent1(4,4) Cent2(6,0), wenn man das Wurzelziehen wegläßt

euklid
Cent1 => 4²+4² = 32
Cent2 => 6²+0 = 36
Cent1 nearest

Manhattan
Cent1 = 4+4 = 8
Cent2 = 6+0 = 6
Cent2 nearest
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
N 1000 MQTT Messages die Sekunde - 1000 Threads erstellen ? Allgemeine Java-Themen 10
H Summe aller Vielfachen von 3 oder 5 unter 1000. Allgemeine Java-Themen 7
MQue 16 Fehler pro 1000 Zeilen Allgemeine Java-Themen 11
R 1000 Zufallszahlen Allgemeine Java-Themen 9
rode45e Java Threads Allgemeine Java-Themen 4
M Threads Allgemeine Java-Themen 1
L Threads Threads in Chatroom Allgemeine Java-Themen 30
berserkerdq2 run-methode eines Threads so programmieren, dass 30x die Sekunde etwas ausgeführt wird. Allgemeine Java-Themen 44
berserkerdq2 Threads, wie genau läuft das in Java ab? (Ich kann Threads erstellen und nutzen, nur das Verständnis) Allgemeine Java-Themen 6
CptK Backpropagation parallelisieren: Kommunikation zwischen den Threads Allgemeine Java-Themen 7
J Eine Frage zu den Threads und Task Allgemeine Java-Themen 1
W Wieviele Threads sind sinnvoll? Allgemeine Java-Themen 8
W Alternative für Threads Allgemeine Java-Themen 6
V Threads Probleme beim Aufrufen von Methoden einer anderen Klasse (Threads) Allgemeine Java-Themen 14
T Multithreading: Wie viele Threads sollte ich erstellen? Allgemeine Java-Themen 12
G Threads vom Mainprogramm steuern Allgemeine Java-Themen 8
S BlockingQueue mit dynamischer Anpassung der Anzahl von Producer und Consumer Threads Allgemeine Java-Themen 1
x46 Threads Threads anhalten Allgemeine Java-Themen 1
J Threads verbessern die Performance NICHT ? Allgemeine Java-Themen 8
W Threads Problem Allgemeine Java-Themen 15
T Threads Tic Tac Toe mit Threads Allgemeine Java-Themen 1
M Threads über Kommandozeile Allgemeine Java-Themen 5
mrbig2017 Threads Chat Programm mit Threads? Allgemeine Java-Themen 2
J Threads - java.lang.IllegalThreadStateException Allgemeine Java-Themen 6
J Internet Broswer in Threads öffnen Allgemeine Java-Themen 1
B Threads Multithreading Threads sollen warten Allgemeine Java-Themen 12
D Threads Parallel laufende Threads Allgemeine Java-Themen 4
J Unvorhersehbares Verhalten - benutze ich die falsche Bedingungsprüfung oder brauche ich Threads? Allgemeine Java-Themen 12
D Eine Forschleife mit Threads abarbeiten um es zu schneller zu machen. Ist das möglich? Allgemeine Java-Themen 20
S Wie kann ich eine kleine Stelle in meinem Code mit multiplen Threads abarbeiten..? Allgemeine Java-Themen 20
P Threads Parallelisierte DB-Abfragen mit variabler Anzahl an Threads Allgemeine Java-Themen 4
J Threads Threads Allgemeine Java-Themen 9
Viktim Threads Liste In unterschiedlichen Threads bearbeiten Allgemeine Java-Themen 23
E Threads Ausführung in Threads ist langsamer als ohne Threads Allgemeine Java-Themen 13
A Anzahl an Threads Systemweit Allgemeine Java-Themen 2
Tausendsassa Input/Output Problem mit der gleichzeitigen Ausgabe zweier Threads Allgemeine Java-Themen 8
S Alle Methodenaufrufe eines Threads notieren..? Allgemeine Java-Themen 7
M Threads JPanel eingeforen mit Threads Allgemeine Java-Themen 2
F Threads Allgemeine Java-Themen 6
F Threads Allgemeine Java-Themen 2
M Sinn von Threads? Allgemeine Java-Themen 1
J Wie erschaffe ich einen sicheren Datenaustausch zwischen Thread und Nicht-Threads Allgemeine Java-Themen 8
L Abfragen ob Threads fertig Allgemeine Java-Themen 3
P Threads Java Zugreifen Allgemeine Java-Themen 6
K Problem: Java-Klasse mit mehreren Threads als eigenen Prozess starten Allgemeine Java-Themen 3
K KeyEvent in Threads Allgemeine Java-Themen 11
V Threads Weshalb funktionieren meine Threads nicht? Allgemeine Java-Themen 2
Thallius Speicherverhalten von Properties und mehreren Threads Allgemeine Java-Themen 5
L Threads beenden Allgemeine Java-Themen 4
P Threads Threads nicht gleichzeitig starten Allgemeine Java-Themen 3
S Threads Threads werden nicht beendet Allgemeine Java-Themen 2
S Start des zweiten Threads erst nach Beenden des ersten Threads Allgemeine Java-Themen 13
N Threads statische Methoden in Threads Allgemeine Java-Themen 5
P 4 Threads in einer Methode Allgemeine Java-Themen 2
M Eclipse Mehrere Threads, mehrere Konsolen Allgemeine Java-Themen 4
OnDemand Threads und synchronized Allgemeine Java-Themen 9
R LinkedList und Threads: Strukturprobleme bez. löschen von Elementen Allgemeine Java-Themen 3
R LinkedList und Threads - welche Methode ist besser? Allgemeine Java-Themen 2
OnDemand Threads und synvhronized Allgemeine Java-Themen 2
S Problem mit Threads Allgemeine Java-Themen 1
W Threads Threads warten lassen Allgemeine Java-Themen 5
H Optimierung durch Threads Allgemeine Java-Themen 31
B Threads halten sich irgendwie auf... Allgemeine Java-Themen 6
M Threads Allgemeine Java-Themen 8
K JNI: Methoden aus unterschiedlichen Threads aufrufen Allgemeine Java-Themen 3
A Applet Alle Threads beim schließen des Applets beenden Allgemeine Java-Themen 8
A Problem mit der Synchronisierung von Threads Allgemeine Java-Themen 15
R SecurityManager für einzelne Klassen/Threads? Allgemeine Java-Themen 38
O Threads und If Befehle Allgemeine Java-Themen 7
P Threads abwechseln lassen mit wait() und notify() Allgemeine Java-Themen 2
H Sehr viele Threads effizient Verwalten Allgemeine Java-Themen 13
C Threads und Exceptions Allgemeine Java-Themen 7
H java.lang.OutOfMemoryError bei der wiederholten Erzeugng von Threads Allgemeine Java-Themen 8
S Threads Abarbeitungsstatus von Threads in Datei schreiben Allgemeine Java-Themen 2
M Zugriff zweier Threads auf diesselbe Methode Allgemeine Java-Themen 16
E Threads Sudoku Threads Allgemeine Java-Themen 8
M Java Threads - Wait Notify - Verständnisproblem Allgemeine Java-Themen 5
Gossi Threads mit unterschiedlichen Aufgaben in einer Klasse? Allgemeine Java-Themen 9
G Threads Ablauf von Threads im Spezialfall Allgemeine Java-Themen 4
V Threads bei quadcore Allgemeine Java-Themen 10
4 Simple(?) Frage zu Threads Allgemeine Java-Themen 14
B Threads Game of Life - Threads Allgemeine Java-Themen 49
R Threads Exceptions von Threads abfangen im ThreadPool Allgemeine Java-Themen 5
S Threads Ende sämtlicher Threads abwarten Allgemeine Java-Themen 6
S Frage zu Threads (Sichtbarkeit und Verhalten) Allgemeine Java-Themen 11
M Java-Threads und Datentypen-Zugriffe Allgemeine Java-Themen 7
P Threads- Programming Allgemeine Java-Themen 2
G Threads Klasse Sound und Threads bleiben hängen Allgemeine Java-Themen 4
C Threads Zwei Threads greifen auf LinkedList zu. Allgemeine Java-Themen 12
M OutOfMemoryError in nebenläufigen Threads Allgemeine Java-Themen 6
M Threads dauerhafte bewegung mit threads Allgemeine Java-Themen 11
frankred Threads Auf eine Gruppe von Threads warten Allgemeine Java-Themen 11
J Eure Meinung: Threads verwenden, oder nicht? Allgemeine Java-Themen 6
K Warum wartet diese Funktion auf beenden des Threads? Allgemeine Java-Themen 3
F Mehrere Threads - ein Stack Allgemeine Java-Themen 6
O Wie kann ich das Ende eines Threads melden? Allgemeine Java-Themen 7
J Writer und Threads Allgemeine Java-Themen 2
G mehrere Threads starten/stoppen Allgemeine Java-Themen 4
E Verständnisfrage bezüglich Threads Allgemeine Java-Themen 4
K Zeitkritische Threads Allgemeine Java-Themen 14

Ähnliche Java Themen

Neue Themen


Oben