Algorithmusfrage

23 Beiträge29.03.2007Archiviert
Student29.03.2007 · Beitrag #12788
Avatar
Mitglied seit: 29.03.2007
Forenbeiträge: 6
Besuche: 39
Hallo,

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

[ Bearbeitet ]
Helms29.03.2007 · Beitrag #12790
Avatar
Mitglied seit: 08.02.2005
Forenbeiträge: 517
Besuche: 1267
Eine kurze Frage am Rande. Ist C als Sprache vorgeschrieben oder dürft ihr auch eine andere verwenden?

Liebe Grüße
Helms
Student29.03.2007 · Beitrag #12791
Avatar
Mitglied seit: 29.03.2007
Forenbeiträge: 6
Besuche: 39
Ja C ist als Programmiersprache vorgegeben.

Viele Grüsse,
Student
[ Bearbeitet Do, 29. Mär 2007, 20:42 ]
s4!ph30.03.2007 · Beitrag #12795
Avatar
Mitglied seit: 15.07.2005
Forenbeiträge: 378
Besuche: 638
@student

warumm soll man in C nicht for-schleifen in if's packen können?!?
geht auch andersrum!
und im kreis!
und alles in allem hin und hehr!

TIP:
http://www.pronix.de/pronix-925.html

[ Bearbeitet Fr, 30. Mär 2007, 16:05 ]
jeipack30.03.2007 · Beitrag #12796
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
Hi Student
Ich kann zwar programmieren habe es aber nie offiziell gelernt. Was bedeutet also lineare Laufzeit ?

also mein Vorgehen wäre:
eingabe in Array w[4] speichern.

for(int i=0;i<w.size();i++) {
for(int j=0;j<w.size();j++) {
if(i!=j && w==w[j]) treffer();
}
}

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)

Historischer Benutzer30.03.2007 · Beitrag #12797
Avatar
Mitglied seit: 27.06.2006
Forenbeiträge: 100
Besuche: 469
... 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)
squeez01.04.2007 · Beitrag #12814
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag

Hashing

Worst Case O(n).

hth
Marco
jeipack11.04.2007 · Beitrag #12980
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
So bin von meinen Ferien zurück.. leider

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.

@squeez: was meinst du mit Hashing ?

Grüsse
squeez11.04.2007 · Beitrag #12985
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag


@squeez: was meinst du mit Hashing ?


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.

hth

Marco
jeipack11.04.2007 · Beitrag #12989
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
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.

Gruss
squeez12.04.2007 · Beitrag #13014
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag

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.

hth

Marco

[1]http://www.linux-related.de/index.html?/coding/o-notation.htm


[ Bearbeitet Do, 12. Apr 2007, 23:07 ]
jeipack13.04.2007 · Beitrag #13016
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
Oh vielen Dank
ein gutes Dokument.

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

Grüsse


1:
for(int i=0;i<w.size();i++) {
for(int j=0;j<w.size();j++) {
if(i!=j && w==w[j]) treffer();
}
}
Student13.04.2007 · Beitrag #13023
Avatar
Mitglied seit: 29.03.2007
Forenbeiträge: 6
Besuche: 39
Super! Danke für das Dokument!
Habe mir folgendes überlegt, in Psydo-Code:

1. Eingabe von Feld A

2. Suche nach der grössten Zahl im Feld A:
maxpos = 1
for i=2 to n
A(i) > A(maxpos) ?
falls ja: maxpos = i
--> lineare Laufzeit

3. Anlegen von Hilfsfeld B und mit 0ern auffüllen:
for i = 1 to maxpos
B(i) = 0
--> lineare Laufzeit

4. In Feld B an Stellen inkrementieren, wo Zahlen in Feld A vorkommen
for j=1 to length (A)
B (A(j)) = B(A(j)) + 1
--> lineare Laufzeit

5. In Feld B Stellen suchen, wo B(A(j))>=2, wenn ja Ausgabe i
for i von 1 bis n
B(A(j)) >= 2 ?
falls ja Ausgabe i
--> lineare Laufzeit


An der Tafel hatten wir folgendes Struktogramm gezeichnet:

1. for i = 1 bis n
B(A(i)) = 1 ?
fallls ja Ausgabe i, B(A(i))
falls nein: B(A(i)) = i

für das Laufzeitverfahren sind wir folgendermaßen vorgegangen:

f(n) = (n-1) *3 + 1 * 4
g(n) = n <--- lineares Verhalten vermutet

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

Grüsse,
Student
jeipack13.04.2007 · Beitrag #13024
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
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
Historischer Benutzer13.04.2007 · Beitrag #13026
Avatar
Mitglied seit: 27.06.2006
Forenbeiträge: 100
Besuche: 469
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 ]
jeipack13.04.2007 · Beitrag #13027
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
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.
Historischer Benutzer13.04.2007 · Beitrag #13029
Avatar
Mitglied seit: 27.06.2006
Forenbeiträge: 100
Besuche: 469
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

mfg,

J[@]R
Student13.04.2007 · Beitrag #13031
Avatar
Mitglied seit: 29.03.2007
Forenbeiträge: 6
Besuche: 39
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.

viele Grüße,
Student
[ Bearbeitet Fr, 13. Apr 2007, 21:03 ]
Historischer Benutzer14.04.2007 · Beitrag #13032
Avatar
Mitglied seit: 27.06.2006
Forenbeiträge: 100
Besuche: 469
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 ;)

Greetz,

J[@]R
jeipack16.04.2007 · Beitrag #13052
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
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();

Map counter = new HashMap();

for(int i=0;i<ints.length;i++) {
counter.put(ints, 0);
}
for(int i=0;i<ints.length;i++) {
counter.put(ints, (Integer)counter.get(ints)+1);
if((Integer)counter.get(ints)>1) System.out.println("linDoppelt: "+ints);
}
return System.currentTimeMillis()-startTime;
}[/cli]
Historischer Benutzer16.04.2007 · Beitrag #13072
Avatar
Mitglied seit: 27.06.2006
Forenbeiträge: 100
Besuche: 469
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 :)

nichts für ungut ;)

mfg, J[@]R
jeipack17.04.2007 · Beitrag #13082
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
R]nichts für ungut ;)

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.

Gruss
jeipack
[ Bearbeitet Di, 17. Apr 2007, 09:15 ]
Historischer Benutzer17.04.2007 · Beitrag #13092
Avatar
Mitglied seit: 27.06.2006
Forenbeiträge: 100
Besuche: 469
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 ...