in der heutigen Vorlesung standen wir vor folgendem Problem:
Es soll ein Algorithmus entwickelt werden, der eine lineare Laufzeit aufweisst und bei Eingabe von 4 Zahlen, die Zahl/en ausgibt, die doppelt vorkommen.
Meine Überlegung war folgende:
Schritt 1: Eingabe der Zahlen
Schritt 2: für i =1 bis größte Zahl lege ein Hilfsfeld B an und B=0
Schritt 3: für j =1 bis 4 setze B [A[j]] = B[A[j]]+1
Schritt 4: für i=1 bis grösste Zahl prüfe if B =02 falls ja gebe "Doppelte Zahl" B aus ansonsten else Ausgabe B "keine doppelte Zahl"
Hier der Code:
(1) Eingabe A; //k=grösste Zahl
(2) for i = 1 to k do B = 0;
(3) for j = 1 to length[A] do B[A[j]] = B[A[j]] + 1;
(4) for i =1 to k do
(5) if B >=2 then printf("Doppelte Zahl: %d",B) else printf("keine doppelte Zahl:%d",B;
Meine Frage: Darf man in C in eine Zählerschleife eine if Abfrage reinpacken? Wie würde dann die richtige Syntax aussehen? Wie könnte man den Algorithmus eleganter lösen wenn man die Werte im Feld B anschaut und sobald der Wert >=2 ist handelt es sich ja um eine doppelte Zahl. Ich hänge an den Zeilen (4) und (5) fest, weil mir eien schöne Ausgabe fehlt.
Lieben Dank für den, der sich damit beschäftigt.
Viele Grüsse,
Student
Ich denke viel einfacher kann man das ganze nicht mehr machen (ich glaube, in C kann man den for-haeder noch ein bisschen verkleinern, das wars dann aber auch)
... und somit sind wir nicht mehr in linearer Laufzeit ;)
Lineare Laufzeit ganz kurz und knapp erkläert - "Soll man eine bestimmte Datenmenge im Algorithmus analysieren, so gilt bei linearer laufzeit : Doppelte Anzahl Datensätze -> doppelte Laufzeit; sprich Laufzeit O(n)
Im Gegensatz gibt jeipacks Code quadratische Laufzeit : Doppelte Datensatzmenge -> vierfache Laufzeit; sprich O(n*n)
R]... und somit sind wir nicht mehr in linearer Laufzeit ;)
Lineare Laufzeit ganz kurz und knapp erkläert - "Soll man eine bestimmte Datenmenge im Algorithmus analysieren, so gilt bei linearer laufzeit : Doppelte Anzahl Datensätze -> doppelte Laufzeit; sprich Laufzeit O(n)
Im Gegensatz gibt jeipacks Code quadratische Laufzeit : Doppelte Datensatzmenge -> vierfache Laufzeit; sprich O(n*n)
Hehe ihrgendwie dachte ich mir das schon..
Da aber immer einer konstante Anzahl (hier 4) von Zahlen eingegeben wird, dachte ich ich schreibs doch mal hin.
Hashfunktionen zerlegen die Eingabe in eine möglichst eindeutige Zahl. Dabei spielt es keine Rolle, um was für einen Datentyp es sich bei der Eingabe handelt. So kann man einen String in eine Zahl umwandeln, oder eine Zahl in eine Zahl. Das Merkmal dabei ist, dass der generierte key durch eine nachfolgende Komprimierungsfunktion in einen definierten Grössenbereich (zB Array) abgebildet werden kann. Dabei wird der key mit dem Wert (Value) abgespeichert.
Weitere Informationen findest du im Netz
Im vorliegenden Fall würde dies zu einem schlanken Algo führen, wenn man diesen Punkt im Hinterkopf behält.
Hey squeez
Ja grundsätzlich weiss ich was ein Hash ist.
Trozdem müssen danach ja wieder alle Hashwerte mit den schon generierten Hashwerten verglichen werden, was auch wieder zu einer quadratischen Funktion führt.
Ein leicht verständliches, und sehr ausführliches Dokument zur O-Notation findest du unter [1]. Das Dokument lässt sich auch ohne Kenntnisse der höheren Mathematik verstehen, da die in diesen Bereich fallenden Punkte ebenfalls erklärt werden.
Mir ist nun aber noch immer nicht klar wie man aus meiner Funktion [1] die eine Laufzeit von O(n²) hat eine mit O(n) hinbekommt.
Aber vielleicht kann ich das ja morgen lösen, wenn ich auch richtig Zeit hab :)
"3" weil im worst case 3 Durchläufe gebraucht werden.
"4" weil 4 Durchläufe gebraucht werden um eine Duplette zu finden
(n-1) und 1 leider keine ahnung
mit lim (n gegen unendlich) f(n)/g(n) = 3
daher: g(n) = n Lineares Verhalten, wie vermutet.
Allerdings funktioniert dieser Algorithmus nur bei ganzen Zahlen und nur soweit, wie es der Wertebereich des jeweiligen Datentyps zulässt.
Ist B nun ein Array mit der grösse der grössten Zahl?
Auf solch eine Lösung wäre ich nie gekommen..
Mhh ich weiss wiedermal eine blöde Frage: Dieser Algorithmus wird in der Praxis nicht angewendet, ist also nur für Übungszwecke gedacht? auch wenn er linear ist, verbraucht er ja viel mehr performance als die quadratische Lösung mit zwei ineinanderverschachtelten for Schleifen. Naja vielleicht unter gewissen Bedingungen: sehr hohe Anzahl von Zahlen und einem fest definierten, nicht zu hohen Maximalwert für diese Zahlen bringt dieser Algorithmus schon was.
Irrtum vorbehalten und lasse mich immer gern belehren :)
jeipack
Mhh ich weiss wiedermal eine blöde Frage: Dieser Algorithmus wird in der Praxis nicht angewendet, ist also nur für Übungszwecke gedacht? auch wenn er linear ist, verbraucht er ja viel mehr performance als die quadratische Lösung mit zwei ineinanderverschachtelten for Schleifen. Naja vielleicht unter gewissen Bedingungen: sehr hohe Anzahl von Zahlen und einem fest definierten, nicht zu hohen Maximalwert für diese Zahlen bringt dieser Algorithmus schon was.
Gegenbeispiele wieso eine lineare Rechenzeit der quadratischen vorzuziehen wäre :
- multiple Funktionsaufrufe, welche sehr oft Zwischenresultate benötigen
- ab n = 5 müsste eine lineare Version des Algorithmus seine Performance schon gegenüber der quadratischen Version ausspielen ... daher sollte man die "sehr hohe Anzahl" schön relativieren - Programmierer gehen meistens den einfachsten Weg um ans Ziel zu kommen, anstatt zu versuchen, Algorithmen zu optimisieren...
- n*n < 4 * n ab n=4 :) [ Bearbeitet Fr, 13. Apr 2007, 13:43 ]
Bei deiner Theorie vergisst du den Faktor c (guggst du 1). f(n) ist bei der liniaren Funktion schnell mal im Vorteil, allerdings ist c bei der quadratischen um einiges kleiner, von daher relativiert sich die "sehr hohe Anzahl" doch wieder nach oben ;)
PS:
R]- n*n < 4 * n ab n=4 :)
meinst du n² > 4*n ab n=4 ? =) .. naja Detail.
Aber weisst du was ich meine?
Gruss
1: Die angegebene Funktion f(n) soll unabhängig sein von systemspezifischen Details (tatsächlicher Zeitaufwand), daher ist von konstanten Faktoren c zu abstrahieren.
Jeps, handelt sich wohl um einen Flüchtigkeitsfehler meinerseits, Shift-Taste wirkt manchmal Wunder.
Richtig bemerkt dein Hinweis mit der Konstanten c, welcher man eine gewisse Laufzeit hinzufügen muss. Somit kann man grob gesagt ab n = 10 oder höher davon ausgehen dass die nichtlineare Laufzeit zum Problem werden kann. Ein praktisches Beispiel wäre die "maximal Execution Time" serverseitiger Skripte auf einem Webserver
hmmm... verstehe nicht wie du auf ca. "n=10" kommst? ist damit der "break even" gemeint ?
bsp:
f1(n) = 3n + 10
f2(n) = n + 100
beide linear und allgemein lässt sich sagen, daß bei gleichen Laufzeitverhalten auf die Konstante c ankommt. in diesem fall ist f1 bis n < 45 schneller als f2.
wenn man sich jetzt z.b. verschiedene laufzeitverhalten anschaut z.b. linear und quadratisch:
f1(n) = n + 1000
f2(n) = n*n +10
wird f1 erst ab n>32 schneller. auch in diesem fall kommt es auf die konstante c an.
um die genaue Definition des Break-Even zu definieren müsste ich meine damaligen Kursunterlagen zurücksuchen ... lang lang ist es her (ca 10 Semester).
Nichtsdestotrotz : ob n = 10, n = 32, n= 123 - Fakt bleibt dass die quadratische Laufzeit nicht als "Optimum" anzusehen ist. In der Praxis kann man zu *mal stark nachdenken* O(n * log n) kommen, je nach Problemstellung erreicht man auch noch ein O(n), allerdings unter Berücksichtigung eines relativ hohen c-Wertes ...
Um an dieser Stelle jetzt noch tiefer auf die Laufzeitoptimierung und n-Bestimmung der obigen kleineren Funktion einzugehen kommt einem Schuss mit der Kanonenkugel auf eine Fliege gleich ;)
Wenn du wüsstest mit was ich schon alles auf Fliegen geschossen hab ^^
Ich hab das nun mal praktisch mit Java getestet und als Durchschnitt bekomme ich ca. 270 --> d.h. wenn mehr als 270 Zahlen eingegeben werden, ist die lineare Funktion schneller. Dieses "sehr grosse Anzahl" muss ich also doch relativieren ^^
Hier der Code (vielleicht könnte man den linearen Algorithmus noch etwas verbessern und ob es in C eine Map gibt weiss ich natürlich auch nicht.)
[cli]public void durchschnitt() { // Durchschnitt von 100 durchläufen berechnen
int subResult=0;
for(int i=0;i<100;i++) {
subResult+=tester();
}
System.out.println(subResult/100);
}
public int tester() {
long quadTime=0;
long linTime=0;
int n=1;
int[] ints;
while(linTime<=quadTime && ++n<1000) {
ints=getInts(n);
quadTime=quadDoppeltScan(ints);
linTime=linDoppeltScan(ints);
}
return n;
}
public long quadDoppeltScan(int[] ints) { //quadratischer Alogorithmus
long startTime =System.currentTimeMillis();
for(int i=0;i<ints.length;i++) {
for(int j=0;j<ints.length;j++) {
if(i!=j && ints==ints[j])
System.out.println("quadDoppelt: " + ints);
}
}
return System.currentTimeMillis()-startTime;
}
public long linDoppeltScan(int[] ints) { //linearer Algorithmus
long startTime =System.currentTimeMillis();
Wenn du nun noch deine "System.out.println" Befehle über StringBuffer zwischenspeicherst, und die Schleifenvariablen-Initialisierung optimierst, und somit alle Ausgaben am Ende ausführen würdest, so bin ich fest der Meinung dass dein 270 um *mindestens* 50 runtergehen wird ...
Einen schnellen Algorithmus erreicht man eben nicht nur durch die Art und Weise wie du was berechnest, sondern auch indem du deinen Code optimierst :)
Jo klar, ich mein wenns mich nicht interessieren würde, hätte ich kein Engaschmont gezeigt.
Nun zur Optimierung.
/e: ah.. naja dieses System.out.println wird ja in beiden Algorithmen angewendet, somit wird also auch bei beiden Performance eingesparrt wenn man das via StringBuffer ausgibt.
Wie würdest du die Schleifenvariablen-Initialisierung optimieren?
Zu meiner Verteidigung muss ich noch sagen, dass ich noch nie einen Grund hatte meinen Javacode zu optimieren. Denn unser Flaschenhals ist mysql mit einem viel zu komplexen Datenmodell dahinter.
Aus zeitlichen Gründen kann ich hier auf die schnelle kein genaues Resultat abgeben (berufliche Verpflichtungen ...)
Zur Zeitbestimmung : in beiden Vergleichsfällen jeweils direkt vor den "for" Schleifen die startTime initialisieren, ansonsten kriegst du gerne eine Verfälschte Aussage ...
Die Resultate werden ebenfalls durch den "Integer" - Cast in der linearen Funktion leicht beeinflusst ...
Zur Variablen-Optimierung : auf Funktionsebene bzw Klassenebene können generell nutzbare Variablen definiert werden - am obigen Beispiel ist allerdings nach erster schnell-Analyse nicht mehr viel hier rauszuschlagen ...