Messwerte verarbeiten

CDW

CDW

0
Mitarbeiter
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
 
Hab mich auch mal an die Aufgabe gemacht...

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

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

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)
 
1. heißt einfach kein komplettes, optimiertes Programm, sondern eine Funktion/Prozedur/sonstwas, so dass der Algorithmus und Funktionsweise ersichtlich sind ;)

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.
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.
 
Ich iteriere einfach über die Größe (1 bis N, zur Festlegung der Anzahl berücksichtigter Messungen), dann lese ich dementsprechend die ersten Messungen ein, vergleiche, ziehe den linken Wert ab und addiere den neuen rechten Wert (spart das komplette itererieren für jede Auswertung), wieder vergleichen usw. dann das ganze für eine Messung mehr...

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!
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;
}
 
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

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 ?
 
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. ;)
Code: 
import sys
if len(sys.argv) != 2:
    print "usage:", sys.argv[0], "<input file>"
    exit(1)

f = open(sys.argv[1])
werte = []
for line in f:
    werte.append(int(line))

start = 0
best = [[0, 1, werte[0]]]
prev = max(0, best[0][2])

for i in xrange(1, len(werte)):
    wert = werte[i]
    if prev + wert > best[-1][2]:
        best.append([start, i, prev + wert])
    if prev + wert > 0:
        prev += wert
    else:
        prev = 0
        start = i

i = len(best) - 1
while best[-1][2] == best[i][2] and i > 0:
    print "Nach %d ms:" % (best[i][0] * 10),
    print best[i][2], werte[best[i][0]:best[i][1]]
    i -= 1

Code: 
$ time python messwerte.py messwerte.txt 
Nach 2560 ms: 45 [-8, 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]

real	0m0.041s
user	0m0.023s
sys	0m0.000s

$ time python messwerte.py messwerte2.txt 
Nach 19540 ms: 439 [-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]

real	0m0.068s
user	0m0.033s
sys	0m0.003s
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben