Multi-Threaded Binäre Suche

[Sophie]

Hallo Zusammen

Ich habe eine Uebung in der ich eine multi-threaded Version einer Binären Suche machen soll.
Die Binäre Suche ist kein Problem und weiter habe ich mir ueberlegt das Array in 4 Teile zu zerlegen und dann jedem Teil jeweils einen Thread zuzuweisen. Das mit den Array zerteilen funktioniert noch nicht wirklich. Ich habe es mit System.arraycopy versucht in einer Methode teilen. Dabei ist das Problem, dass dann nur eine Hälfte des Arrays zurueckgegeben wird.


Ich weiss auch nicht, wie ich dann diesen geteilten Arrays die Threads zuweisen soll. Ich kann ja eigentlich nur die run() Methode aufrufen. Also muesste ich ja dann die geteilten Arrays zusammen mit der gesuchten Zahl uebergeben und auf jedes Objekt dann einzeln einen Thread aufrufen, oder?

Kann mir hier einer weiterhelfen?

 

[Spacerat]

Hier steht unter anderem ganz konkret ein Java-Beispiel für die Rekursiv-Methode einer Binärsuche. Ganz banal würde ich jetzt den Methodenrumpf in die "run()"-Methode einer eigenen Klasse schreiben, welche Thread erweitert und die Methodenparameter im Konstruktor aufnimmt. Aber jede Wette, das wäre zu simpel. Die Sache hat mit Sicherheit noch einen Haken.

 

[Noctarius]

Ab Java 7 hast du jetzt einen Fork-Join Ansatz für sowas

 

[ThreadPool]

Ab Java 7 hast du jetzt einen Fork-Join Ansatz für sowas

Den gab es auch schon seit 2000, nur war er nicht Teil der Standardbibliothek. Die Idee wurde hier skizziert: http://gee.cs.oswego.edu/dl/papers/fj.pdf

Und das dazugehörige concurrent-package "prä-Standardlib" findet man hier Overview of package util.concurrent Release 1.3.4.. Die betreffenden Klassen fangen mit FJ an. Wer bei Java 6 bleiben möchte/muss kann sich die ja extrahieren (public domain) und in ein eigenes Package packen und die Abhängikeiten anpassen etc.

Aber bevor man solche Späße startet kann man auch getrost zu Java 7 greifen und FJ darauf loslassen, anzumerken wäre das man sich noch RecursiveAction (Java Platform SE 7 ) anschaut.

 

[Noctarius]

Das der Ansatz nicht neu ist, ist klar. Ich meinte aber er kann ihn da dann direkt benutzen

 

[Firephoenix]

Hi,
mal ne Frage am Rande, reden wir hier gerade wirklich über binäre suche?
Wieviele Werte sollen denn in dem Array drin sein?
Im Worst-case hat binäre Suche nämlich log2(n), selbst wenn man den kompletten long-wertebereich von 2^64 in ein Array packen könnte (der TO nutzt ja offenbar ein array), landet man bei n = 64. Und das ist wirklich kein Wert bei dem man Multithreading auspacken muss oder?
Gruß

 

[Spacerat]

@FirePhoenix: Der (bzw. die ) TO offenbar schon. Ist zumindest eine Übungsaufgabe. Sieht nach HAG oder ähnlichem aus. Aber vllt. soll diese Suche ja auch nur threadsafe gemacht werden, also sprich ein Monitor auf das Array gesetzt werden.

 

[XHelp]

@Firephoenix, binäre Suche heißt nicht, dass du nur Zahlen suchen kannst. Binär heißt in diesem Fall, dass es in der Datenstruktur immer den "größer"-Teil und "kleiner"-Teil gibt.

 

[ThreadPool]

[...] das ist wirklich kein Wert bei dem man Multithreading auspacken muss oder?
Gruß

Du vergisst das die Datenstruktur für Binäre Suche nach einem Schlüssel sortiert sein muss. D.h. n (log n) für das Sortieren. Des Weiteren müssen die Schlüsselwerte nicht einfachen Zahlen entsprechen, so dass ein Schlüsselvergleich auch "teuer" werden kann. Für das Beispiel des TO ist es sicher nicht unbedingt nötig.

 

[Sophie]

Den gab es auch schon seit 2000, nur war er nicht Teil der Standardbibliothek. Die Idee wurde hier skizziert: http://gee.cs.oswego.edu/dl/papers/fj.pdf

Und das dazugehörige concurrent-package "prä-Standardlib" findet man hier Overview of package util.concurrent Release 1.3.4.. Die betreffenden Klassen fangen mit FJ an. Wer bei Java 6 bleiben möchte/muss kann sich die ja extrahieren (public domain) und in ein eigenes Package packen und die Abhängikeiten anpassen etc.

Aber bevor man solche Späße startet kann man auch getrost zu Java 7 greifen und FJ darauf loslassen, anzumerken wäre das man sich noch RecursiveAction (Java Platform SE 7 ) anschaut.

Ab Java 7 hast du jetzt einen Fork-Join Ansatz für sowas

Danke, fuer den Tip und die Links. Leider darf ich das nicht verwenden. Mein Dozent meinte, es sei ganz gut, dass ich darauf gekommen bin, aber ich soll es ohne versuchen ...

Also im Moment hab ich das Array aufteilen mit in der Run-Methode. Ich hab aber keine Ahnung, wie ich jetzt die Threads, die ich in meiner Testklasse habe dazu bringe, sich dann jeweils nur einen Teil heraus zu suchen und zu bearbeiten. Ist das ueberhaupt möglich?

public void run() {

		int end = arr.length;
		int zaehler = 0;

		if (arr.length == 0) {
			System.exit(0);
		} else if (end < beg) {
			System.out.println(zahl + " nicht im Array.");
			System.exit(0);
		} else {
			int mitte = beg + ((end - beg) / 2);
			zaehler++;
			int[] l1 = Arrays.copyOfRange(arr, 0, mitte);
			int[] l2 = Arrays.copyOfRange(arr, mitte, arr.length);
			
			BinaereSuche b1 = new BinaereSuche(l1, zahl);
			BinaereSuche b2 = new BinaereSuche(l2, zahl);

			if (zahl < arr[mitte]) {
				run();

			} else if (zahl > arr[mitte] && beg != mitte) {
				run();

			} else if (zahl == arr[mitte]) {

				if (zahl > arr.length) {
					int erg = arr[mitte] - zaehler ;
					System.out.println(zahl + " an position " + erg);
					System.exit(0);
				} else {
					System.out.println(yahl + " an position " +mitte);
					System.exit(0);
				}
			}
		}
	}

 

[0x7F800000]

Es geht doch nicht darum, ob man's mit FJ oder sonstwie anstellt, es geht imho darum, dass die Binäre suche grundsätzlich nicht parallelisierbar ist ???:L Was soll es bringen, das Array in 4 Teile zu unterteilen, wenn nach einer einzigen Iteration sowieso 3 der 4 Threads ihre Arbeit einstellen müssen? Bis man die ganzen Threads erstellt hat, hat man schon tausend mal mehr Zeit verbraten, als nötig wäre, den gesamten verfügbaren Speicher mit der normalen Binärsuche durchzulaufen.

Einfache suche (nicht binär) würde da noch irgendeinen Sinn machen, aber multithreaded-binary-search hört sich nach totalen Humbug an.

Das einzige, was man parallelisieren könnte, wäre die evtl extrem aufwendige Vergleichsfunktion: wenn der "Vergleich" so aussieht, dass zwei Bots eine ganze Serie von stundenlangen Kämpfen in einer realistischen physikalischen Umgebung ausfechten, könnte man das natürlich parallelisieren, aber das ist ja nicht mehr der Zuständigkeitsbereich der Binären Suche.

 

[Marco13]

Jupp, eine echte Binäre Suche ist wohl kaum Sinnvoll zu parallelisieren. Ein Array mit 1 Million Elementen zu durchsuchen braucht 20 Vergleiche, bei 1 Milliarde sind es auch nur 30...

Sicher, dass eine Binäre Suche (und keine lineare Suche mit Divide-And-Conquer) gemeint ist?

 

[Firephoenix]

Deswegen hatte ich ja oben auch schonmal gefragt
Das einzige das lange dauert (danke an die vielen Korrekturen ) ist das vergleichen von einzelnen Elementen untereinander, aber in der binären suche wie ich sie kenne findet immer nur ein Vergleich gleichzeitig statt und dieser gibt dann das nächste Teilstück vor.
Man könnte natürlich versuchen möglichst viele Teilstücke vorzurechnen, würde wie oben beschrieben aber jedes mal die hälfte umsonst kalkulieren.

Bei einem Mergesort oder irgend einer unsortierten Datenstruktur würde ich den Ansatz mit mehreren Threads eher nachvollziehen können, aber es scheint ja eher um den Übungszweck zu gehen.
Gruß

 

[Sophie]

Es geht nicht darum, ob das sinvoll ist oder nicht. Das ist eine Übung und deshalb muss ich dass zu mindest versuchen. Die Übung ist nicht für einen Java Kurs sondern für Betriebssysteme und erschein deshalb vielleicht etwas eigenartig( oder sinnlos)
Nachdem wir diese multi-threadet version implementiert haben sollen wir dann, die perfomance messen (und an dieser Stelle wohl feststellen, dass es sinnlos ist )

 

[0x7F800000]

Es geht hier nicht darum, ob das sinvoll ist oder nicht. Das ist eine Übung und deshalb muss ich dass zu mindest versuchen.

Was willst du denn versuchen? Zufälligen code eintippen, bis da ein Algorithmus rauskommt, den es nicht geben kann? :noe:

Ich würde dir raten aufzuhören, dich an Tippfehlern in der Aufgabenstellung festzubeißen, evtl. nochmal nachfragen, was gemeint war, und am Ende die parallelisierte lineare Suche implementieren: der Aufgabensteller kann nichts anderes gemeint haben, weil es eben keine parallele binäre suche gibt (zumindest nicht so einfach, wie du das angedeutet hast).

PS: Es sei denn, es ist dieses Werk von Z. Chen gemeint, da geht es aber nicht um binäre Suche, sondern um Multiple Search Problem.

 

[Sophie]

Was willst du denn versuchen? Zufälligen code eintippen, bis da ein Algorithmus rauskommt, den es nicht geben kann? :noe:

Ich würde dir raten aufzuhören, dich an Tippfehlern in der Aufgabenstellung festzubeißen, evtl. nochmal nachfragen, was gemeint war, und am Ende die parallelisierte lineare Suche implementieren: der Aufgabensteller kann nichts anderes gemeint haben, weil es eben keine parallele binäre suche gibt (zumindest nicht so einfach, wie du das angedeutet hast).

Die Aufgabenstellung hat keinen Tippfehler, ist völlig ernst gemeint und ich habe mich auch nicht verlesen.
Die Lineare Suche ist der zweite Teil der Aufgabe, aber zuerst die Binäre Suche.

 

[0x7F800000]

Die Aufgabenstellung hat keinen Tippfehler, ist völlig ernst gemeint und ich habe mich auch nicht verlesen.

Okay. Dann habe ich wohl meinen Verstand verloren. Ich werde mich umgehend in der nächstgelegenen psychiatrischen Heilanstalt freiwillig ergeben :autsch:

 

[tfa]

Okay. Dann habe ich wohl meinen Verstand verloren. Ich werde mich umgehend in der nächstgelegenen psychiatrischen Heilanstalt freiwillig ergeben :autsch:

Tu das. Vielleicht triffst du da ja den Verrückten, der dieses Paper geschrieben hat

 

[0x7F800000]

Tu das. Vielleicht triffst du da ja den Verrückten, der dieses Paper geschrieben hat

Hmm, irgendwie kommt mir der Kerl doch bekannt vor, ist es nicht der, den ich drei Zeilen davor verlinkt hab?

Es sei denn, es ist dieses Werk von Z. Chen gemeint, da geht es aber nicht um binäre Suche, sondern um Multiple Search Problem.

Was soll ich mit euch Leuten denn machen? Soll ich jetzt mit euch um geld wetten, dass die binäre suche nicht parallelisierbar ist, oder was? :noe:

 

[tfa]

Sry, ich hab nur den Abstract gelesen

 

[JohannisderKaeufer]

Der Unterschied zwischen Binärer Suche die den meisten hier so vorschwebt und dem was dieser Herr Chen macht ist, dass hier von einem einzigen zu suchenden Element ausgegangen wird, Chen aber im Gegensatz eine sortierte Liste von Elementen sucht.

Wenn die Binäre Suche eine Komplexität von log2(n) hat, dann hat das Problem, das Chen zu lösen versucht, mit einem einfachen Algorithmus der Binären Suche umgesetzt, eine Komplexität von m * log2(n), wobei m die Anzahl der zu Suchenden Objekte ist.

//Binäre Suche
public Object search(Object thisObject, SortedSet<Object> inThatSet)

//MultiSearchProblem, CHEN
public Object[] search(SortedSet<Object> thisObjects, SortedSet<Object> inThatSet)

Und wenn Chen was besseres wie m * log2(n) durch Parallelisierung rausbekommt, dann hat das bestimmt auch seine Berechtigung.

 

[Sophie]

:applaus:

 

[0x7F800000]

Und wenn Chen was besseres wie m * log2(n) durch Parallelisierung rausbekommt, dann hat das bestimmt auch seine Berechtigung.

Und der Algorithmus von Karger-Sudan-Motwani färbt einen 3-färbbaren Graphen mit [c]min {O(Δ^1/3 log^4/3Δ), O(n^1/4 log n)}[/c] Farben, das hat Zweifellos auch seine Berechtigung, nur ist es genausowenig eine Binäre suche, wie das MSP.

Jetzt im ernst: Ich habe noch nie eine Hausaufgabe gesehen, wo man im Teil a) so einen riesen-Algo wie den von Chen "implizit" aufgibt, um dann im Punkt b) mit der linearen Suche fortzufahren. Das ergibt für mich irgendwie keinen Sinn.

@Sophie
Solltest du tatsächlich den Algo von Chen im Rahmen einer Hausaufgabe in Java so hinkriegen, dass er bei n aus dem Bereich 1000-1000000 merkbar besser (30% oder so) als die "trivialerweise parallelisierte" Version (wo man die m Suchen einfach auf p Prozessoren verteilt) abschneidet, dann würde es mich wirklich sehr interessieren: wenn ich nicht ganz falsch liege, könnte es bei der Auswertung der Quantile-Trafo einer kumulierten empirischen Verteilungsfunktion nützlich sein.

 

[Sophie]

Jetzt im ernst: Ich habe noch nie eine Hausaufgabe gesehen, wo man im Teil a) so einen riesen-Algo wie den von Chen "implizit" aufgibt, um dann im Punkt b) mit der linearen Suche fortzufahren. Das ergibt für mich irgendwie keinen Sinn.

@Sophie
Solltest du tatsächlich den Algo von Chen im Rahmen einer Hausaufgabe in Java so hinkriegen, dass er bei n aus dem Bereich 1000-1000000 merkbar besser (30% oder so) als die "trivialerweise parallelisierte" Version (wo man die m Suchen einfach auf p Prozessoren verteilt) abschneidet, dann würde es mich wirklich sehr interessieren: wenn ich nicht ganz falsch liege, könnte es bei der Auswertung der Quantile-Trafo einer kumulierten empirischen Verteilungsfunktion nützlich sein.

Ne, um diesen Algorithmus von Chen geht es sicherlich nicht (hoffe ich). Ich bin gerade mal im zweiten Semester und hatte eine kurze Einführung zu Threads)
Ich denke der Sinn dieser Übung ist einfach herauszufinden, dass eine multi-threaded Binäre Suche keinen Sinn macht und im Vergleich dazu die Lineare Suche sehr wohl. (Diese Übung erscheint vielleicht sinnlos, aber ich habe jetzt schon mehr über Threads gelernt als hätten wir diese "PING PONG" Sache machen sollen)

Meine eigentliche Anfänger-Frage war ja auch nur, wo teile ich das Array am Besten auf, um sie dann auf die Threads zu verteilen .

Die Diskussion im Forum war trotzdem sehr hilfreich, da ich zu meinen Übungen auch jeweils eine verfassen muss. Also vielen Dank dafür!

 

[Ark]

Ich bin mir nicht sicher, ob ich gerade die richtige Frage beantworte, aber wenn du n Elemente hast, die von t verschiedenen Threads untersucht werden sollen (lineare Suche), dann kannst du die Arbeit so verteilen, dass alle Threads mindestens [c]n / t[/c] (Ganzzahldivision) Elemente untersuchen, wobei [c]n % t[/c] dieser Threads jeweils ein Element mehr untersuchen müssen. So kannst du die Arbeit leicht auf alle Threads möglichst gleichmäßig verteilen.

Beispiel: 3 Threads, 26 Elemente, also t = 3 und n = 26
Alle Threads müssen mindestens 26 / 3 = 8 Elemente untersuchen.
26 % 3 = 2 Threads müssen aber noch ein Element mehr (also 9 Elemente) untersuchen.
Also bekommen z.B. die ersten beiden Threads 9 Elemente, der dritte Thread bekommt 8. (9 * 2 + 8 = 26 --> passt)
Sind die Indices von 0 bis 25 (inkl.) durchnummeriert, bekommt also Thread 1 die Indices 0 bis 8 aufgebrummt, Thread 2 die Indices 9 bis 17 und Thread 3 die Indices 18 bis 25.

Ark

 

[Marco13]

Und nebenbei: Diese Threads sollten wohl NICHT Kopien von Arraysegmenten bearbeiten, sondern die Arraysegmente selbst. Also nicht

suche(Arrays.copyOfRange(array, min, max));
...
int suche(int teilArray[]) { ... }

sondern

suche(array, min, max);
...
int suche(int ganzerArray[], int min, int max) { ... }

Das Kopieren des Arrays würde sämtliche möglichen Geschwindigkeitsvorteile zunichte machen.

 

[0x7F800000]

Das Kopieren des Arrays würde sämtliche möglichen Geschwindigkeitsvorteile zunichte machen.

Nnee... eehm... njain. Es kommt darauf an, wie groß und wie geartet das Cache ist. Wenn man auf dem gesamten Array mit random access arbeitet, dann kann dieser evtl nicht am Stück in den cache geschoben werden. Wenn man es dagegen so zerstückelt, dass die einzelnen Blöcke in den Cache eines Prozessors reinpassen, könnte es passieren, dass die einzelnen Stückchen in den Cache rübergeladen werden können, wo die Zugriffszeit um vielfaches kürzer ist, was das Programm insgesamt beschleunigt. Wenn du dir beispielsweise Code für Matrixmultiplikation bei einigen gängigen Paketen anguggst, dann wirst du dort unter Umständen feststellen, dass man scheinbar sinnfreie umkopier-Operationen durchführt, die bei einer vereinfachten Aufwand-Analyse nach purer Verschwendung aussehen, aber eben den Cache besser auslasten.

 

[Marco13]

Das ist dann nochmal eine ganz andere Kategorie. Unabhängig von der Frage, ob man solche potentiell höchst architekturspezifischen Optimpierungen machen sollte (und riskieren, dass es auf dem Test-PC 10% schneller und auf einem anderen 3x langsamer läuft) greift das erst bei einer bestimmten Arraygröße... oder Arraykleine Also, man sollte dann vermutlich zumindest noch sowas einbauen wie

if (array.length/numThreads > 100000000) lassDasMitDemKopierenMalLieber();
if (array.length/numThreads < 100000) joaDasKönnteInDenCachePassen();

 

[0x7F800000]

if (array.length/numThreads > 100000000) lassDasMitDemKopierenMalLieber();
if (array.length/numThreads < 100000) joaDasKönnteInDenCachePassen();

Im wesentlichen: so in etwa. Nur nicht ganz so einfach. Das ganze läuft unter dem Stichwort "automatically optimized code", man führt ein programm aus, welches automatisch verschiedene Einstellungen ausprobiert, den konfigurierten/neuerzeugten code laufen lässt, und am ende mehr oder weniger optimale Einstellungen aussucht. Dieser Rocket-Science taugt im allgemeinen jedoch nicht als Zweitsemestler-Hausaufgabe. Und überhaupt: was soll den zwischen 100000 und 100000000 passieren? :joke:

 

[Marco13]

Ich hatte schon überlegt, dort als :joke: sowas wie

else throw new UnsupportedArraySizeException("Use a smaller or a larger array");

hinzuschreiben