[HaBo]

**CDW** · 25.01.09, 18:25

Bei einem Experiment werden Energieschwankungen im 10ms Abstand gemessen und in eine Datei geschrieben.
Format:

Code:

-1
2
-3

also (negative/positive) Zahlen, jeweils eine pro Zeile.

Diese Daten müssen ausgewertet werden - uns (bzw. die Experimentatoren) insteressieren lokale Maxima - also der/die (falls mehrere gleiche vorhanden) Zeitabschnitt(e), während dessen am meisten Energie abgegeben wurde.
Das sind die Stellen, an denen die Summe der Messwerte am höchsten ist.
Bsp:
Messdaten:
-1,-4,5,2,-4,-3,-3,7,-1,-2,2,-8,7,-1,6,-7,-10,-3,-3,-11,-10,-10,5
lokales Maximum: 7,-1,6 => Summe=12
Bsp2:
-4,2,-3,-1,5,-10,2,-5
l.max: 5
Bsp3:
-4,2,-3,-1,5,-10,2,-5,3,-2,4,-1,2,-10
l.Max:
3-2,4,-1,2 -> Summe=6

Hier sind einige Aufgaben dazu (müssen nicht alle erledigt werden ;) )

1. Schreibe einen kurzen, schönen Code, der aus den übergebenen Werten das lokale Maximum herausfindet und ausgibt.

2.Wenn es N Werte gibt - wieviele Möglichkeiten müssen (abhängig von N) getestet werden?

3.Schreibe eine "echte" Anwendung, die aus einer Datei die Messwerte ausliest und verarbeitet. Hier sollte nicht nur die Zahlenfolge ausgegeben werden, sondern entweder die Position in der Datei (Zeile) oder am besten die zeitliche Position (die Messungen werden im 10ms Abstand vorgenommen). Achtung: es kann durchaus mehrere Maxima geben (wenn die Summe der Werte gleich ist) - dann sollten auch alle ausgegeben werden.

Zum testen des Codes können die Beispiele oben genommen werden,
zum testen der Anwendung siehe Anhänge(jeweils 1000 und 6000 Einträge). Interessant wäre auch die (grobe) Performance - zur Orientierung: Prototype Code in Prolog braucht auf meinem Notebook (1,6 Ghz C2Duo, 1GB Ram, Sicstus 4.04) für messwerte1 ~7 sek, für messwerte2 ~1300 Sek

lagalopex · 26.01.09, 10:42

Hab mich auch mal an die Aufgabe gemacht...

1. "kurz und schön", wie soll man das verstehen?

Lösung zu 2.

Ergebnis zu 3.

Anzeige

- Anzeige -

**CDW** · 26.01.09, 12:13

1. heißt einfach kein komplettes, optimiertes Programm, sondern eine Funktion/Prozedur/sonstwas, so dass der Algorithmus und Funktionsweise ersichtlich sind

zu 3.

lagalopex · 26.01.09, 12:44

Lösung zu 1

zu 3

Wie bei 1 geschrieben, hab ich einen etwas anderen Ansatz, der anscheinent auch um einiges schneller ist. Wie bereits angedeutet, dauert die Messung2 nur knapp 2 Sekunden (mit laden, auswerten und ausgeben).
Die Entwicklungszeit hielt sich auch in Grenzen und mit etwa 150 Zeilen ist der Code auch recht übersichtlich (die eigentliche Auswerte Funktion ist 18 Zeilen lang, der Rest ist laden, Zeitmessung, UI).
Ausgabe:

Code:

$ ./mess test_messung1 test_messung2 test_messung3 haupt_messung1 haupt_messung2
test_messung1:
  Lade... 23 Messwerte geladen
  Auswerten.........
  Ergebnisse:
    Maximum: 12
      115ms - 145ms (7, -1, 6)
  Verarbeitung hat 252 us gedauert!

test_messung2:
  Lade... 8 Messwerte geladen
  Auswerten.........
  Ergebnisse:
    Maximum: 5
      35ms - 45ms (5)
  Verarbeitung hat 39 us gedauert!

test_messung3:
  Lade... 14 Messwerte geladen
  Auswerten.........
  Ergebnisse:
    Maximum: 6
      75ms - 125ms (3, -2, 4, -1, 2)
  Verarbeitung hat 41 us gedauert!

haupt_messung1:
  Lade... 1000 Messwerte geladen
  Auswerten.........
  Ergebnisse:
    Maximum: 45
      2575ms - 2835ms (6, -2, 8, 8, 3, 3, -4, -2, -11, 6, 8, -1, -4, 5, 2, 4, -3, -3, 7, 7, -2, 6, -8, 7, -1, 6)
  Verarbeitung hat 21 ms gedauert!

haupt_messung2:
  Lade... 6000 Messwerte geladen
  Auswerten.........
  Ergebnisse:
    Maximum: 439
      19555ms - 21175ms (16, 12, -13, 10, -4, 16, 13, -10, -4, -12, 4, 19, 18, 17, 17, 12, -18, 3, 12, 4, -8, 9, -3, -5, 0, -8, -9, -10, 1, 13, 11, 14, -6, -6, -2, -14, 15, 10, -19, -7, -19, 12, -4, 8, 10, 10, -14, 7, 19, 19, -7, 6, 16, 14, -19, 14, 16, -6, 14, -19, 14, -2, 9, -16, -15, -17, 5, -2, 13, -8, -3, 13, 19, 15, 18, 13, -6, 10, 11, 1, 14, 9, 19, -14, -5, 9, 3, 0, 19, 14, -3, 6, 18, 4, 11, -1, 19, 3, 8, -13, -15, -4, 19, -8, 8, -18, -13, 15, -5, -1, 10, -14, 2, -12, -19, 8, -20, 18, -7, 19, -16, -8, 5, -12, 2, 15, 10, 4, -8, -13, 14, -14, -2, 8, 19, -13, -15, -2, 11, -9, -14, 19, 17, 0, 11, -13, 11, 13, 10, 15, 14, 1, 4, 12, -7, 15, 9, 2, 18, -12, 5, 13)
      18765ms - 21175ms (11, 16, 17, 16, 6, 9, -12, 11, -15, 9, 16, 9, -18, 0, 7, 19, 16, -7, 4, 15, 4, -7, -6, -3, -4, 13, -2, -11, -7, -10, 14, -15, -2, -8, -20, -18, -13, 2, -19, 12, 16, -13, 12, 9, 2, -12, 18, -14, -10, 11, -20, 3, 12, -2, 15, -10, 1, 10, 1, -14, 2, 1, -12, 13, -8, 6, -15, -13, 7, -14, -7, 8, -2, 16, 8, -3, -18, -6, -7, 16, 12, -13, 10, -4, 16, 13, -10, -4, -12, 4, 19, 18, 17, 17, 12, -18, 3, 12, 4, -8, 9, -3, -5, 0, -8, -9, -10, 1, 13, 11, 14, -6, -6, -2, -14, 15, 10, -19, -7, -19, 12, -4, 8, 10, 10, -14, 7, 19, 19, -7, 6, 16, 14, -19, 14, 16, -6, 14, -19, 14, -2, 9, -16, -15, -17, 5, -2, 13, -8, -3, 13, 19, 15, 18, 13, -6, 10, 11, 1, 14, 9, 19, -14, -5, 9, 3, 0, 19, 14, -3, 6, 18, 4, 11, -1, 19, 3, 8, -13, -15, -4, 19, -8, 8, -18, -13, 15, -5, -1, 10, -14, 2, -12, -19, 8, -20, 18, -7, 19, -16, -8, 5, -12, 2, 15, 10, 4, -8, -13, 14, -14, -2, 8, 19, -13, -15, -2, 11, -9, -14, 19, 17, 0, 11, -13, 11, 13, 10, 15, 14, 1, 4, 12, -7, 15, 9, 2, 18, -12, 5, 13)
  Verarbeitung hat 1518 ms gedauert!

C++

Code:

#include <iostream>
#include <list>
#include <string>
#include <fstream>
#include <ctime>

using namespace std;

class timer
{
	struct timespec ts_start, ts_end;
	clockid_t id;
public:
	void start() {
		clock_gettime(id, &ts_start);
	}
	void stop() {
		clock_gettime(id, &ts_end);
	}
	timer(clockid_t clock = CLOCK_MONOTONIC) {
		id = clock;
		start();
	}
	friend std::ostream & operator<<(std::ostream& os, const timer &t);
};

std::ostream & operator<<(std::ostream& os, const timer &t)
{
	unsigned long ns = (t.ts_end.tv_sec - t.ts_start.tv_sec) * 1000000000 + t.ts_end.tv_nsec - t.ts_start.tv_nsec;
	string ext = "ns";
	if (ns >= 10000) {
		ns /= 1000;
		ext = "us";
	}
	if (ns >= 10000) {
		ns /= 1000;
		ext = "ms";
	}
	if (ns >= 10000) {
		ns /= 1000;
		ext = "s";
	}

	os << ns << " " << ext;

	return os;
}

class mess
{
public:
	int load(string file)
	{
		ifstream inf(file.c_str());
		values.clear();

		while (inf.good()) {
			int tmp;
			inf >> tmp;
			values.push_back(tmp);
		}
		values.pop_back();

		if (!inf.eof())
			return 0;

		return values.size();
	}
	void eval()
	{
		max = values.front();
		int com = values.size() * (values.size() + 1) / 2, ccom = 0, ocom = 0;
		for (int width = 1; width <= (int)values.size(); ++width) {
			list<int>::iterator it1 = values.begin(), it2 = values.begin();
			int cur = 0, n;
			for (n = 0; n < width; ++n, it2++)
				cur += *it2;
			check_max(cur, 0, width);
			++ccom;

			for (n = 1; it2 != values.end(); it1++, it2++, ++n, ++ccom) {
				check_max(cur += *it2 - *it1, n, width);
				while (10 * ccom / com > ocom) {
					cout << "." << flush;
					++ocom;
				}
			}
		}
	}

	void result()
	{
		cout << "    Maximum: " << max << endl;
		for (list<set>::iterator it = maxs.begin(); it != maxs.end(); it++) {
			cout << "      " << it->pos * 10 - 5 << "ms - " << (it->pos + it->count - 1) * 10 + 5 << "ms (";
			list<int>::iterator itd = values.begin();
			int n;
			for (n = 0; n < it->pos; ++n, itd++);
			for (n = 0; n < it->count; ++n, itd++)
				cout << *itd << ", ";
			cout << "\b\b)" << endl;
		}
	}

private:
	void check_max(const int &cur, const int &pos, const int &width)
	{
		if (cur == max)
			maxs.push_back(set(pos, width));
		else if(cur > max) {
			maxs.clear();
			maxs.push_back(set(pos, width));
			max = cur;
		}
	}

	list<int> values;
	int max;
	struct set
	{
		set(int p, int c) : pos(p), count(c) {}
		int pos;
		int count;
	};
	list<set> maxs;
};

int main(int argc, char *argv[])
{
	for (int i = 1; i < argc; ++i) {
		if (i != 1)
			cout << endl;
		mess m;
		timer t;
		cout << argv[i] << ":" << endl;
		cout << "  Lade... " << flush;
		int num;
		if (!(num = m.load(argv[i]))) {
			cout << "fehlgeschlagen" << endl;
			continue;
		}
		cout << num << " Messwerte geladen" << endl;
		cout << "  Auswerten" << flush;
		m.eval();
		cout << "\n  Ergebnisse: " << endl;
		m.result();
		t.stop();
		cout << "  Verarbeitung hat " << t << " gedauert!" << endl;
	}
	return 0;
}

**CDW** · 03.02.09, 15:36

zu 1

zu 3

SWI/Sicstus

Ein paar Messungen:

der Code ist zwar nicht ganz optimal (Prädikat check könnte noch etwas optimiert werden, anstatt Sequenzen könnte man nur Anfang+Ende der Position speichern), aber immerhin nun in O(n) und nicht O(n^2).

Code:

 ?- file_to_list('messwerte.txt',L),benchmark(find(L,R),100,Time),length(L,Messwerteanzahl).
L = [-7,1,0,1,-8,4,-4,-7,-2,5|...],
R = [(sum(45),seq([6,-2,8,8,3,3,-4|...]))],
Time = ms(4.04),
Messwerteanzahl = 1000 ?

Code:

?- file_to_list('messwerte2.txt',L),benchmark(find(L,R),100,Time),length(L,Messwerteanzahl).
L = [-12,5,10,-5,-11,-7,13,7,-10,13|...],
R = [(sum(439),seq([11,16,17,16,6,9,-12|...]))],
Time = ms(32.27),
Messwerteanzahl = 6000 ?

Eydeet · 03.02.09, 23:10

Ich habe auch einmal ein kleines Python-Programm gebastelt...
46 bzw. 68ms für die Eingabedateien sind inklusive Einlesen für eine Interpreter-Sprache schon nicht schlecht, denke ich. Die Laufzeit ist O(n).
Nachdem ich das Problem verstanden habe, war die Programmierung nicht weiter schwierig, ich habe mir allerdings keine große Mühe gegeben, das Ganze sonderlich zu optimieren.

python

ausgabe

Anzeige

- Anzeige -

26.01.09, 10:42	#2 (permalink)
lagalopex Registriert seit: 01.11.03 Likes: 0	Hab mich auch mal an die Aufgabe gemacht... 1. "kurz und schön", wie soll man das verstehen? Lösung zu 2. Bei N Messungen gibt es die Möglichkeiten: N mal Einzelmessung N-1 mal 2erMessung ... 1 mal N-Messung also Summe von n=1 bis N von n, was gerade der arithm. Reihe entspricht und sich zu N(N+1)/2 vereinfacht. Also O(N^2). Ergebnis zu 3. Fürs erste hab ich 45 mit einem Auftreten und für das zweite 439 mit zwei. Aber stimmt deine Zeit? Bei mir dauert nämlich auch das zweite nur wenige Sekunden... (amd64 3700+ singlecore)

26.01.09, 12:13	#3 (permalink)
CDW Moderator Themenstarter Registriert seit: 20.07.05 Likes: 202	1. heißt einfach kein komplettes, optimiertes Programm, sondern eine Funktion/Prozedur/sonstwas, so dass der Algorithmus und Funktionsweise ersichtlich sind zu 3. die Zeiten stimmen schon ;). Allerdings verwende ich die naive Vorgehnsweise - das Array wird in Teilarrays zerlegt und jedes einzelne getestet. Das wird einfach bei zu großen Arrays zu einem Speicherzugriffsproblem - schon das alleinige Zerlegen der zweiten Messwertedatei dauert ~20Sek (im Vergleich dazu: das 1 dauert nur ~0.5) Allerdings war dafür die "Entwicklungszeit" angenehm kurz - zusammen mit Dateiauslesen+Testen so um 25 Minuten :) Ich werde mir aber ein paar Gedanken dazu machen - schneller gehts aufjedenfall. Prolog Code: %Zerlegt ein Array in Teilsequenzen subseq([_\|T],R):-subseq(T,R). subseq(L,R):-seq(L,R). seq([R\|_],[R]). seq([H\|T],[H\|R]):-seq(T,R). check(Seq):- sumlist(Seq,Sum), %vergleicht einzelne Teilsequenzen mit subsequence(_,OldSum),!, %den in DB gespeicherten (Sum<OldSum ; (Sum>OldSum -> retractall(subsequence(_,_));true), asserta(subsequence(Seq,Sum))). max_subseq([H\|T],Result):- retractall(subsequence(_,_)), asserta(subsequence(H,H)), %initialisiere DB forall(subseq([H\|T],R),check(R)), findall((seq(Seq),sum(Sum)),subsequence(Seq,Sum),Result). PS: Habe übrigens dieselben Werte heraus. __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

03.02.09, 15:36	#5 (permalink)
CDW Moderator Themenstarter Registriert seit: 20.07.05 Likes: 202	zu 1 Ich habe mir folgende Sachen überlegt: man braucht nur 1 mal zu iterieren, sofern man sich bei der Iteration immer die vorherige Summe merkt und einen Speicher für "Kandidaten" hat. Ausgangssituation: eine Liste. Beim Durchgang werden die Zahlen addiert. Merke: vorherige Summe + Sequenz (alternativ Position) für die Ausgabe, speichere eventuelle Kandidaten. Suche am Ende die "größten" Kandidaten heraus. 1. am Ende der Liste ist man fertig 2. Ist die vorherige Summe+aktuelle Zahl < als aktuelle Zahl, so kann man die vorherige Summe sowie Sequenz verwerfen (denn größer wirds nicht). 3. Ist vorherige Summe+aktuelle Zahl > vorherige Summe, so kann man die Zahl zu der aktuellen Sequenz hinzufügen und mit der neuen Summe fortfahren 4.Ist vorherige Summe+aktuelle Zahl =<vorherige Summe, so kann es ja sein, dass es weiterhin noch kleiner wird - also bisheriges Ergebnis als Kandidaten speichern und fortfahren. Kandidaten Speichern: ob man nur die größte Sequenz oder alles speichert (und später für die Ausgabe filtert/sortiert) ist "Geschmackssache". 1:1 Umsetzung des obigen Algos (in Prolog - wer hätte es gedacht :) ): Code: check([],_). check([Val\|T],seq(Sum,_)) :- Sum+Val<Val,check(T,seq(Val,[Val])),!. check([Val\|T],seq(Sum,Seq)) :- NewSum is Sum+Val, NewSum>Sum,check(T,seq(NewSum,[Val\|Seq])),!. check([Val\|T],seq(Sum,Seq)) :- NewSum is Sum+Val, NewSum=<Sum, seq(Old,_),!,store(Old,seq(Sum,Seq)), check(T,seq(NewSum,[Val\|Seq])),!. "Nachteil" des Algorithmus : wenn eine Sequenz als Summe 0 ergibt und direkt darauf die "größte" Sequenz folgt, so wird die "0 Sequenz" nicht beachtet. Wobei das imho ein Definitionsfall ist, der auch berücksichtigt werden kann zu 3 SWI/Sicstus Code: :-use_module(library(lists)). find([H\|T],Res):-retractall(seq(_,_)),asserta(seq(H,[H])), check(T,seq(H,[H])), findall((sum(Sum),seq(Seq)),(seq(Sum,R),reverse(R,Seq)),Res). check([],_). check([Val\|T],seq(Sum,_)) :- Sum+Val<Val,check(T,seq(Val,[Val])),!. check([Val\|T],seq(Sum,Seq)) :- NewSum is Sum+Val, NewSum>Sum,check(T,seq(NewSum,[Val\|Seq])),!. check([Val\|T],seq(Sum,Seq)) :- NewSum is Sum+Val, NewSum=<Sum, seq(Old,_),!,store(Old,seq(Sum,Seq)), check(T,seq(NewSum,[Val\|Seq])),!. :- dynamic seq/2. store(Old,seq(New,Seq)):-Old>New; ( Old<New,retractall(seq(_,_)); Old=:=New ),asserta(seq(New,Seq)). file_to_list(File,List):- open(File,read,Stream), reader(Stream,List),close(Stream). reader(Stream,[]):-peek_char(Stream,end_of_file). reader(Stream,[Value\|Values]):-read_line(Stream,Codes), %für SWI: read_line_to_codes number_codes(Value,Codes), reader(Stream,Values),!. Anwendung: Code: file_to_list('messwerte.txt',List),find(List,Result). List = [-7,1,0,1,-8,4,-4,-7,-2,5\|...], Result = [(sum(45),seq([6,-2,8,8,3,3,-4\|...]))] ? ; no Ein paar Messungen: der Code ist zwar nicht ganz optimal (Prädikat check könnte noch etwas optimiert werden, anstatt Sequenzen könnte man nur Anfang+Ende der Position speichern), aber immerhin nun in O(n) und nicht O(n^2). Code: ?- file_to_list('messwerte.txt',L),benchmark(find(L,R),100,Time),length(L,Messwerteanzahl). L = [-7,1,0,1,-8,4,-4,-7,-2,5\|...], R = [(sum(45),seq([6,-2,8,8,3,3,-4\|...]))], Time = ms(4.04), Messwerteanzahl = 1000 ? Code: ?- file_to_list('messwerte2.txt',L),benchmark(find(L,R),100,Time),length(L,Messwerteanzahl). L = [-12,5,10,-5,-11,-7,13,7,-10,13\|...], R = [(sum(439),seq([11,16,17,16,6,9,-12\|...]))], Time = ms(32.27), Messwerteanzahl = 6000 ? __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Zahlen auslesen und Verarbeiten (Telefonbuch)	D31~$0u1	Code Kitchen	7	05.11.07 17:39
eml Dateien verarbeiten	ba2	(Web-) Design und webbasierte Sprachen	1	09.08.06 10:56
Batch Programmierung - Verarbeiten von Strings	inter.faiz	Code Kitchen	1	18.03.04 10:59
[C/C++] daten von stdandardin richtig verarbeiten	soox	Code Kitchen	0	22.11.03 21:26
XML mit PHP verarbeiten ? ? ?	MaX109	(Web-) Design und webbasierte Sprachen	0	25.04.02 12:37

[HaBo]

Messwerte verarbeiten