Was ist effizenter?

[deung]

Hey,

neulich im Infounterricht hatte wir die Aufgabe ein Programm zu einem Diätrotz zu schreiben.
Das Programm sollte die Dauer des Abnehmporzesses berrechnen, wenn man pro Woche 2% seines Körpergewichtes verliert.

Da ich mit meinem Nachbar natürlich besonders schlau sein wollte, haben wir das ganze als Exponentialfunktion gesehen und uns folgendes gedacht.

Code: Alles auswählen

wunschGewicht = startGewicht * 0,98^Zeit

umgestellt heißt das dann:

Code: Alles auswählen

log(0,98) (wunschGewicht/startGewicht) = Zeit
// 0,98 ist dabei die Basis und (wunschGewicht/startGewicht) der Nummerus

zum Vergleich die Schleife würde so aussehen:

Code: Alles auswählen

int time;
while (wunschGew > Gewicht){
  Gewicht= 0.98*Gewicht;
  time++;
}

Was ist jetzt effizienter? Braucht der Computer mehr Power für die Schleife oder mehr für den Logerithmus?
Eins ist klar der Logerithmus ist um Welten genauer, zumindestens wenn man eine Woche mit 5 Nachkommastellen angeben will

[cloidnerux]

Hi und Willkommen im Forum.

Was ist jetzt effizienter? Braucht der Computer mehr Power für die Schleife oder mehr für den Logerithmus?
Eins ist klar der Logerithmus ist um Welten genauer, zumindestens wenn man eine Woche mit 5 Nachkommastellen angeben will

Das kann man so nicht beantworten. Das Problem liegt darin, wir der Compiler/Interpreter Code umsetzt.
Hier haben wir mal Code gegeneinander getestet:http://www.proggen.org/doku.php?id=project:wordcount
Herausgekommen war, dass ich einen Code geschrieben habe, den der Compiler so gut umgesetzt hat, auch ohne zusätzliche Optimierungen, dass er unter den ersten drei ist, wohingegen "optimierter" code langsamer war.

Natürlich kann man grob abschätzen, wie lange etwas dauern wird. Eure Lösung mit Logarithmus hat eine annähernd konstante Laufzeit, egal für welche Zahlen. Die Schleife wird mit zunehmender Differenz zwischen Start- und Endgewicht immer länger brauchen und bietet eben nur eine Wochen genaue Bestimmung.

Aber ungeachtet der Laufzeit sehe ich in der Lösung mit Logarithmus den sinnvolleren Ansatz, da es hier absolut keine Notwendigkeit für Schleifen gibt und vor allem für große Zahlen der Logarithmus besser Funktioniert.
Zudem habt ihr damit auch einen Beweis/Beleg für die Korrektheit eures Ergebnisses gegeben.

MfG cloidnerux.

[deung]

ok.
Vielen Dank für die Schnelle Antwort.

[Xin]

Logarithmus ist weniger eigener Code => weniger eigener Wartungsaufwand (falls der fremde Code funktioniert).

Was schneller ist, kann schnell zu einer Frage der Schleifendurchläufe werden.
Teste es doch mal, ab wieviel Wochen der Logarithmus schneller als die Multiplikation wird.

[Fisherman]

Was ist jetzt effizienter? Braucht der Computer mehr Power für die Schleife oder mehr für den Logerithmus?

Ich habe mir die Mühe gemacht ein kleines Programm in C zu schreiben um diese interessante Frage beantworten zu können.
Generell könnte man sagen: Es ist egal welche der beiden Varianten man benutzt solange man nur einmal oder ein paar Mal die Berechnung durchführt. Erst bei höheren Iterationen (~> 50.000) fällt ein Unterschied bei dem gegebenen Scenario auf.

Testumgebung: Linux - Debian, I3, 6GB Ram, Laptop

Code: Alles auswählen

[Parameter]
 Gewicht start       : 100.000000
 Gewicht ende        : 80.000000
 Prozentuale Abnahme : 2.000000
 Zeit bis erreichen  : 11.045229
 Durchläufe          : 1000000
[/Parameter]
[Ergebnisse]
 Dauer Logarithmus : 120000 clicks (0.120000 sec.)
 Dauer Schleife    : 100000 clicks (0.100000 sec.)
[/Ergebnisse]

[Parameter]
 Gewicht start       : 100.000000
 Gewicht ende        : 75.000000
 Prozentuale Abnahme : 2.000000
 Zeit bis erreichen  : 14.239779
 Durchläufe          : 1000000
[/Parameter]
[Ergebnisse]
 Dauer Logarithmus : 110000 clicks (0.110000 sec.)
 Dauer Schleife    : 130000 clicks (0.130000 sec.)
[/Ergebnisse]

Wer diesen Test bei sich selbst durchführen möchte :

Code: Alles auswählen

#include <stdio.h>
#include <math.h>
#include <time.h>

/*
	Benchmark: Log vs. Schleife
	(c) J.Sauer Dez. 2012 [Fisherman (==) proggen.org]
        Compile: cc ./speedtest.c -o speedtest -lm
        Test: ./speedtest > ./log.txt
*/


// Berechnung der Abnahmezeit mittels Logarithmus
float abnahmezeit_log(float start, float ende, float prozent)
{
 return (log(ende/start)/log((1-(prozent/100.0))));
}


// Berechnung der Abnahmezeit mittels Schleife
int abnahmezeit_schleife(float start, float ende, float prozent)
{
 int zeit = 0, tmp = start;
 while (tmp > ende)
 {
 tmp = (1-(prozent/100.0)) * tmp;
 ++zeit;
 }
 return (zeit);
}


// Test - Durchführung
void scenario(int iterationen, float gewicht_start, float gewicht_ende, float prozentsatz)
{
 clock_t t;
 int i;
 // Ausgabe der Parameter
 printf("[Parameter]\n");
 printf(" Gewicht start       : %lf\n",gewicht_start);
 printf(" Gewicht ende        : %lf\n",gewicht_ende);
 printf(" Prozentuale Abnahme : %lf\n", prozentsatz);
 printf(" Zeit bis erreichen  : %lf\n",abnahmezeit_log(gewicht_start, gewicht_ende, prozentsatz));
 printf(" Durchläufe          : %i\n",iterationen);
 printf("[/Parameter]\n");
 printf("[Ergebnisse]\n");
 // Abnahmezeit mit Log berechnen
 float erg_a;
 int erg_b;
 t = clock();
 for (i=0; i<iterationen;++i)
   erg_a = abnahmezeit_log(gewicht_start, gewicht_ende, prozentsatz);
 t = clock() - t;
 printf(" Dauer Logarithmus : %d clicks (%f sec.)\n",t,((float)t)/CLOCKS_PER_SEC);

 // Abnahmezeit mit Schleife berechnen
 t = clock();
 for (i=0; i<iterationen;++i)
   erg_b = abnahmezeit_schleife(gewicht_start, gewicht_ende, prozentsatz);
 t = clock() - t;
 printf(" Dauer Schleife    : %d clicks (%f sec.)\n",t,((float)t)/CLOCKS_PER_SEC);

 printf("[/Ergebnisse]\n\n");

}

int main()
{
 // Parameter
 int   it = 1000000;	// Iterationen
 float gs = 100.0;	// Startgewicht
 float ge =  90.0;	// Zielgewicht
 float pr =   2.0;	// Prozentuale Abnahme

 float gstop = 50.0;	// Stop Bedingung Gewicht

 while (ge > gstop) 
 {
  scenario(it,gs,ge,pr);// Test Durchführen
  ge = ge - 5.0;	// Gewicht um Wert verringern für neuen Test
 }
 return 0;
}

Viel Spaß und Gruß

Fisherman

[Xin]

Was ist jetzt effizienter? Braucht der Computer mehr Power für die Schleife oder mehr für den Logerithmus?

Ich habe mir die Mühe gemacht ein kleines Programm in C zu schreiben um diese interessante Frage beantworten zu können.

clock() ist hier vielleicht nicht optimal. Du siehst hoffentlich auch, dass die Aussage eher ein Indiz als eine Aussage ist.

Aber trotzdem ist das genau der richtige Weg, an Informationen zu bekommen: Ausprobieren.

Man könnte jetzt noch einen Graphen zeichnen lassen, ab welcher Steller die Berechnung der Schleifendurchläufe signifikant langsamer werden als die Berechnung der Logarithmen und das dort gefundene Ergebnis in eine If-Abfrage eintragen, so dass je nach gewünschtem Gewichtsverlust die eine oder andere Methode verwendet wird.

[Fisherman]

Quelle: http://www.willemer.de/informatik/cpp/timelib.htm Author: http://www.willemer.de/

Mit der Funktion clock() wird die verbrauchte CPU-Zeit ermittelt. Das heißt, dass Zeiten anderer parallel laufender Prozesse nicht in die Zeitmessung mit einfließen. Dazu werden die verbrauchten CPU-Ticks seit dem Start des Programms ermittelt. Um auf Sekunden zu kommen, muss der Wert durch die Konstante CLOCKS_PER_SEC geteilt werden. Diese Funktion eignet sich vor allem für Performance-Messungen.

Mir ging es eigentlich nur um das genannte Scenario ... Wer die "Nase vorn hat"

[Xin]

Quelle: http://www.willemer.de/informatik/cpp/timelib.htm Author: http://www.willemer.de/

Ich kenne diese Ticks... allerdings ist der Unterschied zwischen den Zeitmessungen in der Regel nicht 1 Tick, sondern in der Regel massiv größer.
Wenn Du Glück hast, liegen zwischen Deiner Messung 2 Ticks. Wenn Du Pech hast nur einer.
Wie groß ist CLOCKS_PER_SEC bei Dir? Das gibt entsprechend die ungefähre Genauigkeit der einzelnen Ticks an.

Mir ging es eigentlich nur um das genannte Scenario ... Wer die "Nase vorn hat"

Das Szenario hängt halt von der Eingabe der Parameter ab. Du musst also eine Reihe von Parametern gegeneinander austesten.

[Fisherman]

Die Parameter werden in dem Programm linear geändert - daher konnte ich, da gebe ich Dir Recht den Indiz dafür finden, dass bis zu einer gewissen Zeit "Schleife vor Log" liegt und ab dann signifikant langsamer wird.

Ich würde mich freuen, wenn du die Zeitmessung nach deinen Vorstellungen korrigieren und dann einmal eine einzelne Berechnung log vs. Schleife durchführen würdest. Wenn dort ein "messbares Ergebnis" herauskommt bin ich von deiner Methode überzeugt!

[Fisherman]

Code: Alles auswählen

Wenn Du Glück hast, liegen zwischen Deiner Messung 2 Ticks. Wenn Du Pech hast nur einer.
Wie groß ist CLOCKS_PER_SEC bei Dir? Das gibt entsprechend die ungefähre Genauigkeit der einzelnen Ticks an.

Bei mir CLOCKS_PER_SEC: 1.000.000

Dieses kleine Beispielprogramm soll Licht ins dunkel bringen :
g++ ./clocks.cpp -o clocks

Code: Alles auswählen

#include <iostream>
#include <time.h>

using namespace std;

int main () {

    for(int i = 0; i < 10 ; i++) {

        int first_clock = clock();
        int first_time = time(NULL);

        while(time(NULL) <= first_time) {}

        int second_time = time(NULL);
        int second_clock = clock();

        cout << "Actual clocks per second = " << (second_clock - first_clock)/(second_time - first_time) << "\n";

        cout << "CLOCKS_PER_SEC = " << CLOCKS_PER_SEC << "\n";

    }

    return 0;

}

Meine Ausgabe :

Code: Alles auswählen

Actual clocks per second = 940000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 1000000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 1000000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 1000000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 1000000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 990000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 990000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 1000000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 1010000
CLOCKS_PER_SEC = 1000000
Actual clocks per second = 1000000
CLOCKS_PER_SEC = 1000000