for schleife einfacher loesen < Matlab < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:36 Mi 07.05.2008 | | Autor: | walterW |
| Aufgabe | datensatz b (ziemlich gross, 1.7 mio punkte)
ich hab ein zeitfenster mit laenge T dass ueber b gezogen wird und zwar immer um s weiter
a soll ein vektor werden in den von jedem zeitfenster der maximale wert rausgeschrieben wird |
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:gomatlab
ich hab das mit einer for schleife geloesst:
a=zeros(floor((length(b)-T)/s),1);
for i=s:s:(length(b)-T)
maxpeaka=max(b(i:T+i));
a(i/s)=maxpeaka;
end
allerdings dauert das ziemlich lange (15 minuten fuer den ganzen datensatz b, und ich muss das fuer ziemich viele
datensaetze machen)
kann man das auch einfacher und schneller loesen?
|
|
| |
|
Hi,
> datensatz b (ziemlich gross, 1.7 mio punkte)
> ich hab ein zeitfenster mit laenge T dass ueber b gezogen
> wird und zwar immer um s weiter
> a soll ein vektor werden in den von jedem zeitfenster der
> maximale wert rausgeschrieben wird
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:gomatlab
>
> ich hab das mit einer for schleife geloesst:
>
> a=zeros(floor((length(b)-T)/s),1);
>
> for i=s:s:(length(b)-T)
> maxpeaka=max(b(i:T+i));
> a(i/s)=maxpeaka;
> end
>
> allerdings dauert das ziemlich lange (15 minuten fuer den
> ganzen datensatz b, und ich muss das fuer ziemich viele
> datensaetze machen)
> kann man das auch einfacher und schneller loesen?
erste loesung fuer schneller: in einem mex-file zb. mit C implementieren. solche schleifengeschichten, die nicht vektorisierbar sind, werden dann um ein vielfaches schneller.
algorithmische optimierung: haengt denke ich von der schrittweite s im verhaeltnis zu T ab. ist s>=T, wuesste ich nicht, wie man das optimieren soll. ist allerdings s deutlich kleiner als T (zb. s=1, T=50), laesst sich bestimmt etwas machen. dann kannst du evtl. das maximum aus dem vorhergehenden schritt fuer die berchnung des neuen maximums verwenden. Ist nur eine idee, ausknobeln muesstest du das schon selber...
gruss
matthias
|
|
|
| |
|
Hallo,
gerade für den Fall [mm] $s\geq [/mm] T$ wüsste ich eine Lösung:
b2=reshape(b(1:end-mod(length(b),s)), s, []); b2max=max(b2(1:T, :));
Hier werden zwar die letzten Elemente, die nicht mehr ins Vielfache von s hineinpassen, abgeschnitten, aber darum kann man sich gesondert kümmern.
Für 1,7 Mio. Werte dauert es bei mir ca. 120ms (für unterschiedliche T und s), also doch recht schnell.
Für T>s würde ich den Datenvektor jeweils um s verschoben vervielfachen und analog mit reshape umformen. Der worst case ist dabei, wenn s und T teilerfremd sind.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:42 Di 13.05.2008 | | Autor: | walterW |
die idee find ich ganz interessant,
du stellst also eine matrix auf in der du aus jeder zeile(von 1 bis T) dann das maximum nimmst
es ist bei mir aber in der tat so dass T groesser ist als s ( s=10 und T=36000, also nicht teilerfremd ;)
aber was ich nicht ganz versteh wie du das mit dem vervielfachen meinst
mein fenster geht ja ueber mehrere s
was ich mir noch gedacht hab ist eine matrix aufzustellen in der die Zeilen meine Zeitfenster sind jeweils um s verschoben. aber das funktioniert nicht weil ich dann eine matrix bekomm die 36000x170000 eintraege hat und das laesst matlab nicht mehr zu..
@matthias: ich kenn mich leider in C nicht aus. matlab is des einzige was ich mal n bischen gelernt hab..
|
|
|
| |
|
Hi,
> die idee find ich ganz interessant,
> du stellst also eine matrix auf in der du aus jeder
> zeile(von 1 bis T) dann das maximum nimmst
> es ist bei mir aber in der tat so dass T groesser ist als
> s ( s=10 und T=36000, also nicht teilerfremd ;)
in diesem fall solltest du das algorithmisch optimieren koennen. Lass uns der einfachheit halber mal die zeitfenster [0,T] und [s,s+T] betrachten. fakt ist, dass der bereich, ueber den du maximierst sich 'fast gar nicht' aendert. der bereich [s,T] ist ja in beiden fenstern enthalten und macht in deinem fall ca. 99,997% des gesamtbereiches aus!
Ich wuerde deshalb so vorgehen:
sei [mm] $m_1=max [/mm] [0,T]$ (du weisst, wie ich das meine)
im ersten schritt wuerde ich nun checken, ob das maximum aus der delta menge [0,s] stammt, also
1. ist [mm] $m_1=max [/mm] [0,s]$?
-> falls nein, stammt [mm] m_1 [/mm] aus dem gemeinsamen bereich [s,T] und muss auch bei der berchnung von [mm] $m_2=max [/mm] [s,s+T]$ beruecksichtigt werden. dann ist aber einfach
[mm] $m_2=max(m_1,max [/mm] [T,s+T])$
beachte, dass du in diesem fall, der SEHR wahrscheinlich ist (s.o.) nur ueber fenster der laenge s maximieren musst statt ueber das riesige T fenster!
-> falls ja, musst du das maximum wie gehabt ueber das ganze fenster T berechnen. Wie gesagt, wenn die daten mehr oder weniger zufaellig verteilt sind (und nicht gerade monoton fallend...), hat dieser fall nur eine verschwindend kleine wahrscheinlichkeit.
Ich denke, mit diesem vorgehen, kannst du die rechenzeit deutlich verringern.
gruss
matthias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:38 Mi 14.05.2008 | | Autor: | walterW |
hallo,
also ich hab mal versucht das so zu machen wie du gesagt hast, ich hoff ich habs richtig verstanden
ich hab dann einfach mal einen beispieldatensatz x genommen
aber irgendwas muss ich aber falsch gemacht haben es dauert naja ich weiss nicht wielang nach 15 minuten hab ich abgebrochen..
du hast das schon mit einer if anweisung gemeint oder?
x=rand(1,1782000);
T=30*60*20;
s=10;
M=zeros(1,((length(x)-T)/s-1)); %ich hab gehoert vorher den vektor zu
%implementieren soll schneller gehen
for i=1:((length(x)-T)/s-1); %i geht von 1 bis zum begin des letzten
%fensters
m=max(x(s*i-s+1:T+s*i-s+1)); %m=maximum aus dem fenster
if m==max(x(s+1:T+s*i-s+1));
M(i+1)=max(m,max(x(T+s*i-s+1:T+s*i-s+1+s))); %m2=max(m1,max[T,s+T]),
else
M(i+1)=max(x(s*(i+1)-s+1:T+s*(i+1)-s+1)); %m2=max[s,T+s] falls es doch in
%dem kleinen bereich liegen sollte
end
M(i)=m; %M soll dann der Vektor sein in dem aus
%jedem fenster das maximum steht
end
|
|
|
| |
|
Hi,
> hallo,
> also ich hab mal versucht das so zu machen wie du gesagt
> hast, ich hoff ich habs richtig verstanden
> ich hab dann einfach mal einen beispieldatensatz x
> genommen
>
> aber irgendwas muss ich aber falsch gemacht haben es dauert
> naja ich weiss nicht wielang nach 15 minuten hab ich
> abgebrochen..
> du hast das schon mit einer if anweisung gemeint oder?
>
>
> x=rand(1,1782000);
> T=30*60*20;
> s=10;
>
> M=zeros(1,((length(x)-T)/s-1)); %ich hab gehoert vorher
> den vektor zu
> %implementieren soll schneller gehen
>
> for i=1:((length(x)-T)/s-1); %i geht von 1 bis zum
> begin des letzten
> %fensters
>
> m=max(x(s*i-s+1:T+s*i-s+1)); %m=maximum aus dem
> fenster
nee, das stimmt so nicht: so berechnest du ja doch wieder in jedem schritt das maximum des grossen fensters...
>
> if m==max(x(s+1:T+s*i-s+1));
>
> M(i+1)=max(m,max(x(T+s*i-s+1:T+s*i-s+1+s))); %m2=max(m1,max[T,s+T]),
> else
> M(i+1)=max(x(s*(i+1)-s+1:T+s*(i+1)-s+1));
> %m2=max[s,T+s] falls es doch in
> %dem kleinen bereich liegen sollte
> end
> M(i)=m; %M soll dann der Vektor sein in dem aus
> %jedem fenster das maximum steht
> end
was ich meinte ist: man berchnet im ersten schritt das maximum ueber das grosse fenster (fallunterscheidung in der schleife, if i==1 then ... ), in allen weiteren checkt man zunaechst, ob das maximum des vorigen fensters aus der delta-menge stammte oder nicht. Dann die fallunterscheidung, wie ich sie gepostet habe.
gruss
matthias
|
|
|
|
