1000 Threads oder Iterativ?

[vimar]

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

 

[SlaterB]

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

 

[Marco13]

Verwende einen ThreadPoolExecutor mit etwa Runtime.availableProcessors()*2 Threads, und gib' ihm die Aufgaben (am besten mit invokeAll, das wartet automatisch auf die Rückgaben). Ansonsten auch mal [JavaSpecialists 149] - The Law of the Overstocked Haberdashery anschauen.

 

[vimar]

so rufe ich derzeit threads auf:

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]

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

 

[bygones]

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

 

[JohannisderKaeufer]

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]

@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

 

[JohannisderKaeufer]

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

sqrt(DeltaX_1² + DeltaY_1²) < sqrt(DeltaX_2² + DeltaY_2²)

Kann man dass, daraus ableiten

DeltaX_1² + DeltaY_1² < DeltaX_2² + DeltaY_2²

Wenn dass gilt,

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.

 

[JohannisderKaeufer]

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]

@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

 

[JohannisderKaeufer]

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