Sprungsuche

freakC++

Hallo zusammen,
ich beschäftige mich momentan mit Suchverfahren. Dabei ist die Lineare Suche ja billig, doch möchte ich mich vor der binären Suche mit der Sprungsuche beschäftigen. Leider gibt Google nichts Gutes her, weshalb ich euch bitte, ob mir jemand kurz das Prinzip der Sprungsuche erklären könnte. Das wäre echt top von euch!

Vielen Dank
lg, freakC++

Don06

Der erste Treffer bei Google ist doch schon vielversprechend: Sprungsuche Da wird sogar noch erwähnt, was die optimale Sprungweite sein soll. Das Prinzip hinter der Sprungsuche sollte klar sein. Wie bei der binären Suche brauchst du eine sortierte Datenmenge.

Gruß
Don06

freakC++

Ja, das habe ich auch gelesen, doch ich muss ehrlich sagen, dass mir das nicht sehr geholfen hat. Daher hoffe ich auf eine einfache Erklärung von euch!

Vielen Dank
lg, freakC++

Don06

Dann schildere doch mal genau, ab wann du den Prozess nicht mehr verstehst. Das Prinzip ist ja noch ganz anschaulich. Du schaust dir z.B. in 10er-Schritten die Elemente an und prüfst, ob die kleiner/größer als dein gesuchter Wert sind. Sind deine Daten aufsteigend sortiert und ist der betrachtete Wert erstmals größer als der zu suchende Wert, muss sich der gesuchte Wert in einem der 10 Elemente vor dem betrachteten befinden. Die 10 kannst du dann linear absuchen, oder irgendein anderes Suchverfahren benutzen. Die Schrittanzahl kann natürlich variiert werden.

Gruß
Don06

freakC++

Danke, solch einen Satz habe ich benötigt.

Mehr wollte ich nicht!

lg, freakC++

freakC++

Welche Sprungweite ist dem idealsten? Es kommt ja auf die Arraygröße an, weshalb ich gedacht habe, dass ich diese zum Beispiel durch zehn teile. Gibt es vielleicht irgendeine Regel oder einen Tipp, wie groß ein Sprung sein sollte?

Ich habe die Sprungsuche jetzt mal implementiert. Sie scheint zu funktioniere, doch könntet ihr mal drüber schauen, ob man hier noch was vom Stil verbessern könnte? Das mit jump und step gefällt mir irgendwie nicht. step ist der Sprungschritt und jump die Summe der aktuellen Schritte.

bool jumpsearch(int* arr, int n, int srch, int step)
{
	int jump=0;
	while (jump < n)
	{
		if(arr[jump]==srch) 
			return true;
		else if (arr[jump] > srch)
		{
			int* temp = new int[step];
			for (int i=0; i<step; ++i)
				temp[i]=arr[jump-step+i];
			return linsearch(temp,step,srch); //Lineare Suche
		}
		jump+=step;
	}
}

Kann man denn hier überhaupt von einer eigenen Suche sprechen? Die "Sprungsuche" bedient sich doch sowieso nur an der Linearen oder Binären Suche. Sie leistet nur Vorarbeit?!

Vielen Dank
lg, freakC++

freaky

Sprungweite = sqrt((a/b)*n)

freakC++

Ah, danke. Warum ist das so? Oder ist das Informatikgeschichte? Ne, das bestimmt irgendwelche Effzienzgründe, aber welche?

Was ist a und was b? Ich vermute, dass n die Größe des Arrays ist?

Ich habe oben noch was reineditiert. Könntet ihr darüber noch schauen ?

Vielen Dank für die Hilfe
lg, freakC++

PS.: Ich sehe gerade, dass bereits Don06 die Sprungweite angesprochen hat. Sry. Dennoch frage ich mich was, a und b ist?

SeppJ

freakC++ schrieb:

Ah, danke. Warum ist das so? Oder ist das Informatikgeschichte? Ne, das bestimmt irgendwelche Effzienzgründe, aber welche?

Natürlich sind das Effizienzgründe. Und natürlich ist das eine Informatikgeschichte. Woher kommt denn der Wert 10, den du vorgeschlagen hast? Der ist doch reine Willkür. Das andere ist Mathematik.

Was ist a und was b? Ich vermute, dass n die Größe des Arrays ist?

Steht alles in dem allerersten Link erklärt, den du als allererste Antowrt in diesem Thread bekommen hast.

Ich habe oben noch was reineditiert. Könntet ihr darüber noch schauen ?

Tschuldige, ich gehe jetzt erstmal Mittagessen :xmas1:

freakC++

Jap, den ersten Link...siehe letztes Editieren.

Guten Appetit (was gibts denn :p )?

Die 10 war reine Willkür. Ich brauchte nur ein Beispiel.

Bis bald
lg, freakC++

PS: Mir wird leider aus dem Link auch nicht so ganz klar, was a und b bedeutet. Das steht nur, dass ein Sprung a kostet und ein sequentieller Vergleich b Einheiten...vll stelle ich mich auch doof an

SeppJ

freakC++ schrieb:

Jap, den ersten Link...siehe letztes Editieren.

Guten Appetit (was gibts denn :p )?

Das übliche: Formfleisch mit der Sauce des Tages, dazu die drei Standardbeilagen, die zwei Standardsalate und zwei von den vier Standarddesserts zur Auswahl.

PS: Mir wird leider aus dem Link auch nicht so ganz klar, was a und b bedeutet. Das steht nur, dass ein Sprung a kostet und ein sequentieller Vergleich b Einheiten...vll stelle ich mich auch doof an

Mit Einheiten ist hier Prozessorzeit gemeint. Ist natürlich schwer zu quantifizieren. Sprünge kosten auf Containern wie Arrays und Vectoren ungefähr 1 Prozessorschritt. Der Vergleich hängt natürlich stark davon ab, was sortiert werden soll. ints zu Vergleichen kostet auch ungefähr 1 Prozessorschritt, höchstens 2. Dann hätte man als optimale Sprungweite Wurzel(n). Wenn du aber beispielsweise große Bitmaps vergleichst, hast du a<<b und somit für nicht zu große n eine optimale Sprungweite von 0 (das heißt sequentielle Suche wäre das beste).

freakC++

Das Übliche? Isst du im Steigenberger? Bei mir gab es Kartoffeln mit Wurst und Salat

Also, das hört sich ja sehr kompliziert an und ich habe davon noch nie etwas gehört. Zwar wird mir durch deine Erklärung jetzt einiges klarer, doch kann ich a und b nicht ausrechnen. Vielleicht liegt das daran, dass ich in der Informatik noch nicht soweit gekommen bin, doch wie soll ich über Prozessorzeit die a u. b herausbekommen.

Ich will doch nur die Schrittweite...

Vielen Dank, SeppJ
lg, freakC++

SeppJ

Denk einfach, wie viele Befehle nötig sind, um das gewünschte zu erreichen, das gibt dir eine ziemlich gute Vorstellung.

Th69

Außerdem enthält dein Code noch ein Speicherleck und ist ineffizient.
Warum nicht einfach

...
else if (arr[jump] > srch)
{
   return linsearch(&arr[jump-step],step,srch);
}

?

freakC++

Stimmt!

Man, auf so etwas würde ich nie kommen, aber im Nachhinein ist es klar, dass dieser Stil viel besser ist. Naja, ich hoffe mit der Zeit komm ich auch darauf!

Vielen Dank
lg, freakC++

freakC++

Noch eine Frage bezüglich der Syntax.

Warum muss ich eigentlich mit dem Kaufmännischen Und "arr" an linsearch übergeben. Wenn ich "jumpsearch" aufrufe, übergebe ich doch auch einfach nur "arr" und nicht "&arr".

danke
lg, freakC++

Th69

'arr' bedeutet eigentlich '&arr[0]' - ist also nur eine Kurzschreibweise.

würdest du ja einen Wert übergeben und nicht die Adresse.

Bei den vielen Fragen, die du hast, solltest du aber vllt. noch mal ein C++ Buch durchgehen.
Löblich, daß du Algorithmen verstehen willst, aber dazu müssen die Grundlagen sitzen. Per "Trial and Error" kommt man damit nicht weit (hast du ja selber bei der Binärsuche gemerkt!).

freakC++ schrieb:

Welche Sprungweite ist dem idealsten? Es kommt ja auf die Arraygröße an, weshalb ich gedacht habe, dass ich diese zum Beispiel durch zehn teile. Gibt es vielleicht irgendeine Regel oder einen Tipp, wie groß ein Sprung sein sollte?

Sicher, die Hälfte der Arraygröße ist ideal (und beim nächsten Schritt davon wieder die Hälfte usw.).
IIRC ist das dann sowieso das, was man binäre Suche nennt.

hustbaer

Bei Suchen in einem Array im RAM wird die "Sprungsuche" wohl kaum jemals schneller sein als eine Binäre Suche. Oder irre ich mich da?

Kennt jemand ein Beispiel wo die "Sprungsuche" signifikant schneller ist als eine Binäre Suche? (Oder aus sonst irgendeinem Grund vorzuziehen wäre)
(Irgendein Beispiel, nicht eingeschränkt auf Array und/oder RAM)

Th69

Ich denke, die Sprungsuche macht nur Sinn bei Daten, welche nicht gleichzeitig im Hauptspeicher vorhanden sind (z.B. bei einer sortierten Datei), d.h. die Cachegröße entspricht dann dem Step.

Ich hatte vorher auch noch nicht von der Sprungsuche gehört (steht auch nicht in Sedgewick's "Algorithmen" drin - als Verbesserung der binären Suche nur die Interpolationssuche).