Sprungsuche

[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!).

[Athar]

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).

[volkard]

Th69 schrieb:

steht auch nicht in Sedgewick's "Algorithmen" drin

Das sagt wenig.

[freakC++]

Hallo,
vielen Dank für die zahlreichen Antworten:

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

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

Darf ich zusammenfassen. Das Kaufmännische UND ist hier keine Referenz, sondern hier wird - aufgrund des Zeigers als Paramters - eine Adresse übergeben. Es wird also das Array ab [jump-step] übergeben bzw. die Adresse, sodass ab dieser Stelle mit dem Array gearbeitet wird. Falls das so ist, dann habe ich das verstanden.

Die Sprungsuche habe ich eigentlich nur angesprochen, um vollständig zu sein. Ich würde sonst auch die binäre Suche bevorzugen.

Bezüglich "Trial and Error": Ich hoffe, dass ihr mich nicht falsch versteht. Ich arbeit mit einem Buch, doch habe ich immer nur in den Ferien Zeit, da die Oberstufe schon Zeit beansprucht. Daher muss ich am Anfang der Ferien erstmal aufarbeiten, was ich wieder vergessen habe. Außerdem kommen immer wieder fragen auf, wenn man sich das alles selbst beibringt und nur ein Forum (aber ein sehr gutes ) hat, dass hilft. Ich hoffe, dass ihr somit über die ein oder andere "komische" Frage hinwegseht. Ich versuche mich stets zu verbessern.

Vielen Dank an alle
lg, freakC++