Laufzeitanalyse [Matlab]

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
Laufzeitanalyse [Matlab]
N'aabend zusammen.

Ich möchte in einer t x 3 Matrix eermitteln, wieviele (nb) von [0 0 0 ] verschiedene Zeilen sie hat.Die erste ist Zeile ist davon verschieden. Rein mathematisch müßte man das ja so machen können:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
nb=1;
for i=2:t
    if N(i,:)==[0 0 0]
        nb=nb;
    else
        nb=nb+1;
    end
end


Nun ist die Frage, ob das auch unter Laufzeitbetrachtungen noch geschickt ist. Es müssen so doch pro Zeile 3 Vergleiche gemacht werden, oder? verwirrt

Wie könnte man das reduzieren. Wenn der Eintrag 1 schon von Null verschieden ist, ist man ja für diese Zeile schon fertig. Analog für die zweite Position. Auf die Masse der Daten gilt folgende Vermutung: Je größer t, umso mehr Nullzeilen.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
nb=1;
for i=2:t
     if N(i,1) ~= 0
       nb=nb+1;
     else
           if N(i,2)~=0
              nb=nb+1;
           else
                if N(i,3)~=0
                   nb=nb+1;
                else
                    nb=nb;
                end
           end
      end
end


Bringt das was und stimmt das überhaupt so? t bewegt sich in der Größenordnung 1000²
sqrt(2) Auf diesen Beitrag antworten »

Der theoretische Informatiker würde jetzt sagen: Alles egal, alles . (Im Worst Case sind es auch gleich viele Vergleiche, wenn Matlab wirklich so vergleicht, wie du annimmst.)

Matlabs Vergleich ist auch eine Black Box für uns, woher wissen wir, was es tut? In so einem Fall gibt es eigentlich nur eines: Ausprobieren. (Ich bin mir übrigens ziemlich sicher, dass der direkte Vergleich von Matlab schneller ist.)

Deine Anweisung "nb=nb" ergibt übrigens nicht besonders viel Sinn.
tigerbine Auf diesen Beitrag antworten »

Also das Variante ! schneller ist. Nun gut, nachdem ich für diesen Teil des Programms nun schon 3 Stunden brauche und Matlab blink immer noch, dachte ich eben ich hätte "Mist programmiert".

Würdest Du diese Laufzeit für t=800² als ok ansehen. Ich hab nen Pentium M Prozessor, 1700MHz, 1.70GHz, 2.00GB RAM (Sagt die Systemsteuerung Big Laugh )

Edit: wie schreibe ich sonst, das sich nichts ändern soll verwirrt
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Also das Variante ! schneller ist. Nun gut, nachdem ich für diesen Teil des Programms nun schon 3 Stunden brauche und Matlab blink immer noch, dachte ich eben ich hätte "Mist programmiert".

Matlab ist nicht gerade für schnelle Ausführungsgeschwindigkeit bekannt, ganz im Gegenteil.

Zitat:
Original von tigerbine
Würdest Du diese Laufzeit für t=800² als ok ansehen. Ich hab nen Pentium M Prozessor, 1700MHz, 1.70GHz, 2.00GB RAM (Sagt die Systemsteuerung Big Laugh )

Nein, das ist völlig inakzeptabel. Auf meinem schwächeren Rechner schafft ein C-Programm, das das Array auch noch mit Zufallszahlen füllt, die Aufgabe in 750 ms.

Zitat:
Original von tigerbine
Edit: wie schreibe ich sonst, das sich nichts ändern soll verwirrt

Ach komm. smile
tigerbine Auf diesen Beitrag antworten »

Was in ms und ich warte hier schon den ganzen Tag das das Ding mir was sagt... böse Hammer

Du kennst ja auch meinen anderen Beiträgen schon das Problem worum es geht. Stichwort Dreiecke. Ich muss dass eben für große ts ausrechnen.

Matlab ist eben das was ich ich noch in der Schublade hatte. Ist ja auch noch die R12 Version. Keine Ahnung was man für solche aufgaben nehmen würde. Damals hat mir matlab gereicht. Aber ich mache ja auch keine Informatik. Ne 4x4 Matrix war immer mal drin.

Spass beiseite, welches Programm sollte ich mir zulegen. Möglichst als Download verfügbar, ich hab am Wochenende noch viel zu tun.

Bis n=200 lief das ganze noch in verträglicher Zeit. Von ms wollen wir aber mal nicht sprechen. Ich setzt das Programm mal rein. Vielleicht hast du ja den ulitmativen Tipp für mich. Muss nochmal kurz weg, bin aber gegen 23.45 wieder da. Antwort wäre spitze Freude

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
%Projektion am Ikosaeder 
%a:  Kantenlänge des Ikosaeders
%R:  Radius der zu produzierenden Kugel
%RU: Umkugelradius für a=1
%Zusammenhang: R=RU*a <=> a = R/RU 

%Ikosaedermittelpunkt
M=[0;0;0];

%Radius Umkugel Ikosaeder a=1
RU=0.25*sqrt(10+2*sqrt(5));

%******************************************************************************************************************
%Radius der zu produzierenden Kugel
%R=input('Kugelradius R: ');

%Berechnung der Kantenlänge a
%a= R/RU;

%Will man mit R arbeiten, muss man bei der Projektionsvorschrift die Variablen tauschen.
%******************************************************************************************************************

%Festlegung der Kantenlänge a
a=1


%Radius Umkreis gleichseitiges Dreieck (weiß)
ru=(sqrt(3)/3)*a;

%Radius Inkreis gleichseitiges Dreieck (weiß)
ri=(sqrt(3)/6)*a;

%Abstand "weißes Ikosaeder-Dreieck" und M (Höhe der Pyramide) 1/16=0.0625
hp=(sqrt(0.0625*(10+2*sqrt(5))-1/3))*a;

%Schwerpunkt/Umkreismittelpunkt des "weißen Ikosaeder-Dreiecks"
S=[0;hp;0];

%Eckpunkte eines "weißen Iskosaeder-Dreiecks "(liegen auf Umkugel)
E1=[(-0.5)*a;hp;ri];
E2=[(0.5)*a;hp;ri];
E3=[0;hp;-ru];

E1E2=[1*a;0;0];
E1E3=[(0.5)*a;0;-ru-ri];

%*******************************************************************************************************************
1
%Berechnung der inneren Punkte für n=Frequenz (Anzahl der Teilstrecken). Zeilenweise im Dreieck von Links nach Rechts. 
n=input('n: ');

%Blockmatrix erstellen 3*(n+1) x (n+1), M: Koordinaten im "weißen Ikosaeder-Dreieck"
k=-1;
for i=1:(n+1)
    %Erzeugt den Dreierblock xyz
    d=3*(i-1)+1;
    
    %Sorgt für die Dreieckgestalt
    k=k+1;
    
    for j=1:[(n+1)-k]
        M(d:d+2,j)=E1+((j-1)/n)*E1E2+((i-1)/n)*E1E3;
    end
end
M;
%*******************************************************************************************************************

%*******************************************************************************************************************
2
%Projektion der neuen (roten) Punkte auf die Umkugel. Wegen M=[0;0;0] ist für jeden Punkt W im "weißen Ikosaeder-Dreieck" 
%seine Projektion WP: WP=R*(1/norm(W))*W;

%Projektionsmatrix erstellen, P: Koordinaten 
i=1;
d=1; %für die Dreieckblöcke der Koordinaten
k=0;

%Erste Dreieckszeile
P(d:d+2,1)=M(d:d+2,1); %Eckpunkt E1 bleibt
    for j=2:[(n+1)-(k+1)]
        P(d:d+2,j)=RU*(1/(norm(M(d:d+2,j))))*M(d:d+2,j);
    end 
P(d:d+2,n+1)=M(d:d+2,n+1); %Eckpunkt E2 bleibt

%innere Dreieckszeilen
if n>1
    for i=2:n
        d=3*(i-1)+1;
        k=k+1;
        
        for j=1:[(n+1)-k]
            P(d:d+2,j)=RU*(1/(norm(M(d:d+2,j))))*M(d:d+2,j);
        end
    end
end

%Eckpunkt E3 bleibt
d=3*n+1;
P(d:d+2,1)=M(d:d+2,1);
        
P;
%********************************************************************************************************************

%********************************************************************************************************************
%Kontrollmatrix (Ob E1E2E3 unverändert geblieben sind)
K=P-M;
%********************************************************************************************************************

%********************************************************************************************************************
3
%Längenmatrizen erstellen V:Vertikal, H: Horizontal, D Diagonal

%Horizontale Längen-Matrix
k=-1;
for i=1:n
    d=3*(i-1)+1;
    k=k+1;
    for j=1:[n-k]
        H(i,j)=norm(P(d:d+2,j)-P(d:d+2,j+1));
    end
end
H;

%Vertikale Längen-Matrix
k=-1;
for i=1:n
    d=3*(i-1)+1;
    k=k+1;
    for j=1:[n-k]
        V(i,j)=norm(P(d:d+2,j)-P(d+3:d+5,j));
    end
end
V;

%Diagonale Längen-Matrix
k=-1;
for i=1:n
    d=3*(i-1)+1;
    k=k+1;
    for j=1:[n-k]
        D(i,j)=norm(P(d:d+2,j+1)-P(d+3:d+5,j));
    end
end
D;
%********************************************************************************************************************

%********************************************************************************************************************
4
%Matrix1 mit den Dreiecksangaben [Hor-Ver-Dia] (2 oben - 1 unten)
k=0;
for i=1:n
    for j=1:((n+1)-i)
        k=k+1;
        T1(k,1)=H(i,j);
        T1(k,2)=V(i,j);
        T1(k,3)=D(i,j);
    end
end
T1;

%Matrix2 mit den Dreiecksangaben [Hor-Ver-Dia] (1 oben - 2 unten)
k=0;

if n==1
   T2=[0 0 0];
end
   
if n>1
    for i=2:n
        for j=1:((n+1)-i)
        k=k+1;
        T2(k,1)=H(i,j);
        T2(k,2)=V(i-1,j+1);
        T2(k,3)=D(i-1,j);
        end
    end
end
T2;

%Alles in eine Matrix schreiben
%disp('Dreiecke (Hor Ver Dia) erst v dann ^');
T=[T1;T2];
%********************************************************************************************************************

%*********************************************************************************************************************
%Kontrollzahl der Dreiecke:
t1=0;
t2=0;
for i=1:n
    t1=t1+i;
end
for j=1:(n-1)
    t2=t2+j;  
end
disp('Kontrollzahl der Dreiecke');
t=t1+t2
%*********************************************************************************************************************

%********************************************************************************************************************
%Die Matrix T wird im ANSICHTmodus in der FESTpunktdarstellung long. Die Variable T eigent sich nicht zum sortieren
%da ihre Einträge im Formal double gespeichert sind. 
% WHAT YOU SEE IS NOT WHAT YOU 'VE GOT
%M%********************************************************************************************************************

%********************************************************************************************************************
%Radius der zu produzierenden Kugel %ÄNDERUNG von 10^5 auf 10^4!!!
R1=input('Kugelradius R(m): ');
R=R1*10^4;
A=R/RU;

TA=A*T;
%********************************************************************************************************************

%********************************************************************************************************************
%Matrixangaben auf 10^-5m vor Komma umrechnen. Dann Abrunden/schneiden mit intX
R5=int32(TA);
%********************************************************************************************************************

%********************************************************************************************************************
5
%Sortieren innerhalb Zeile
for i=1:t
    SR5(i,:)=sorty(R5(i,:));
end
SR5;

%Sortieren der Matrix
S=sortrows(SR5);
%*********************************************************************************************************************

%*********************************************************************************************************************
6
%Produzierbar?
HV=max(SR5);
H=max(HV);

LV=min(SR5);
L=min(LV);

I=[L H]

if H>21000
    disp('Möglich sind 0 bis 21000: !!!nicht möglich!!!');
else
    disp('Möglich sind 0 bis 21000: möglich :-)');
end
%*********************************************************************************************************************

%*********************************************************************************************************************
7
%Anzahl(Number) der verschiedenen Dreiecke bestimmen
SD=double(S);

N(1,:)=SD(1,:);
for i=2:t
    N(i,:)=SD(i-1,:)-SD(i,:);
end
N;

nb=1;
for i=2:t
    if N(i,:)==[0 0 0]
        nb=nb;
    else
        nb=nb+1;
    end
end
nb
%*********************************************************************************************************************

%*********************************************************************************************************************
%Wird auf die Dreiecke gesehen die Vielzahl geringer?
q=nb/t
%*********************************************************************************************************************
clear classes
    
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Spass beiseite, welches Programm sollte ich mir zulegen. Möglichst als Download verfügbar, ich hab am Wochenende noch viel zu tun.

Äh, ich würde sagen, du braucht einen Compiler zur Programmiersprache deiner Wahl; das dürfte noch mit verträglichem Aufwand schnell zu machen sein, du musst dir ja jetzt nicht gerade Gedanken darüber machen, welche FFT-Variante du implementieren möchtest...

Zitat:
Original von tigerbine
Bis n=200 lief das ganze noch in verträglicher Zeit. Von ms wollen wir aber mal nicht sprechen.

Ich hab keine Ahnung, was die Leute machen, die Matlab für Scientific Computing verwenden, das kann man ja auch irgendwie in einer Version für Supercomputer haben und was weiß ich nicht was. In dem Matlab-Einführungskurs an der Uni, den ich besucht habe, sind wir auf jeden Fall schnell an die Geschwindigkeitsgrenzen von Matlab gestoßen...
 
 
tigerbine Auf diesen Beitrag antworten »

Zitat:
Äh, ich würde sagen, du braucht einen Compiler zur Programmiersprache deiner Wahl; das dürfte noch mit verträglichem Aufwand schnell zu machen sein, du musst dir ja jetzt nicht gerade Gedanken darüber machen, welche FFT-Variante du implementieren möchtest...


Ok, ich würde sagen, Du hast für Dich in einer verständlichen Sprache geantwortet. Ich verstehe nun erstmal nicht so viel Big Laugh Muss an der Bahnhofsnähe meiner Wohnung liegen.

Zitat:
wikipedia
Ein Compiler (auch Kompilierer oder Übersetzer) ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm - genannt Quellprogramm - in ein semantisch äquivalentes Programm einer Zielsprache (Zielprogramm) umwandelt. Üblicherweise handelt es sich dabei um die Übersetzung eines von einem Programmierer in einer Programmiersprache geschriebenen Quelltextes in Assemblersprache, Bytecode oder Maschinensprache. Das Übersetzen eines Quellprogramms in ein Zielprogramm durch einen Compiler wird auch als Kompilierung bezeichnet.


Zitat:
sqrt
Programmiersprache deiner Wahl;


Na ich lag doch mit matlab schon daneben. Warum ist das dann eigentlich Standard an der Uni.... verwirrt Also da ich mich außerhalb von Übungszetteln nie mit sowas beschäftigt habe, habe ich keine Ahnung was nun zu wählen wäre.

Ich bräuchte was, was schnell mit Matrizen kann und auch Festpunktzahlen beherrscht. Ich will ja nur auf 0.5mm Genauigkeit am Ende vergleichen.

Du siehst eine Kundin im Kaufrausch vor Dir...Die ultimative Vetreter Chance. Big Laugh

Und nein, beim schnellen Fourier möchte ich heute Abend nichts mehr bestellen.
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Na ich lag doch mit matlab schon daneben.

Das Problem an Matlab ist ja, dass man die Programme nicht kompilieren kann...

Zitat:
Original von tigerbine
habe ich keine Ahnung was nun zu wählen wäre.

Müsst ihr keine Programmiersprache lernen bei euch?

Zitat:
Original von tigerbine
Ich bräuchte was, was schnell mit Matrizen kann und auch Festpunktzahlen beherrscht. Ich will ja nur auf 0.5mm Genauigkeit am Ende vergleichen.

Naja, so ein paar Matrizenoperationen hat man auch schnell selbst implementiert. Festkomma lässt sich zwar auch machen, aber da solltest du vielleicht besser eine Bibliothek dafür suchen.

Zitat:
Original von tigerbine
Du siehst eine Kundin im Kaufrausch vor Dir...Die ultimative Vetreter Chance. Big Laugh

Gute Compiler zu vielen Programmiersprachen gibt es auch als Freie Software und kostenlos.
tigerbine Auf diesen Beitrag antworten »

Nein, wir müssen keine Programmiersprache machen. C++ oder so was gibt es als freiwilligen Kurs.

Da meine Unterprogramme ja nicht so schwer sind, traue ich mir das schon zu.

Wie meinst Du das jetzt mit der Bibliothek?

Gegen kostenlos habe ich gar nichts. Nenn' mir doch einfach einen Namen und ich probier es dann damit. In Sachen Computer kann ich eben nur Programme benutzen...und selbst da kommt es zu Fehlern

http://www.outerlimit.de/errors/windows/break2.gif
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Wie meinst Du das jetzt mit der Bibliothek?

Naja irgendwer wird schon Werkzeuge für Festkommaoperationen geschrieben haben, die du dann weiterverwenden kannst. Musst halt suchen.

Zitat:
Original von tigerbine
Nenn' mir doch einfach einen Namen und ich probier es dann damit.

Kommt auf die Programmiersprache an... Die meisten Bibliotheken wird es einfach zu nutzen für C geben, da gibt es den gcc als Compiler. Einfacher zu lernen ist Pascal (etwa mit Freepascal als Compiler), aber du musst halt schauen, ob du was findest, was du weiterverwenden kannst.
tigerbine Auf diesen Beitrag antworten »

Wird C also in der "Praxis" häufiger verwendet. Wenn ich mich jetzt schon in was neues reinfriemle, dann soll es ja auch ein bisschen nützen.

Danke für die Geduld Wink
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Wird C also in der "Praxis" häufiger verwendet.

Ja. Das ändert aber nichts daran, dass es eigentlich eine grässliche Programmiersprache ist, und moderne Programmiersprachen mehr bieten. Pascal ist nicht moderner, aber hatte den Ansatz als Sprache in der Lehre eingesetzt zu werden und ist daher wegen der Typensicherheit einfacher zu handhaben und am Anfang weniger frustrieren. Was in der Wissenschaft noch ganz gerne verwendet wird, ist Fortran (in einem jüngeren Dialekt, nicht das Ding von 1977), aber das kenne ich nicht. Eine wirklich moderne Programmiersprache wäre beispielsweise Dylan, aber dafür gibt es auf der anderen Seite nicht viel zusätzliches Material.

Naja, du musst halt wissen, was du willst.
tigerbine Auf diesen Beitrag antworten »

Zitat:
sqrt(2)
Naja, du musst halt wissen, was du willst.


Mmh zunächst eine Sprache/ Programm, dass mir den geposteten Matlab-file (Also meine Dreiecksberechnung) in ms( Big Laugh ) macht. 2 PCs laufen immer noch und ich muss das ja für verschiedene Werte tabellieren und dann auch noch für andere Modelle machen. Die benutzen im Grunde den gleichen Algorithmus, nur andere Projektionsparameter (z.B. ändert sich ja der Umkugelradius).

Wenn das bei Pascal auch mit dem Festkomma, also das Runden am Ende möglich ist, warum nicht. Hauptziel ist die Bearbeitung des Kugelprobelms. Wenn C zu kompliziert ist, dann hat das jetzt keinen Sinn.

Freeware wäre dann wohl erstmal auch nicht verkehrt, weil wenn es nicht klappt und die Euros am ... sind, dann gibt's hier wieder nur Spaghetti... Big Laugh
nschlange Auf diesen Beitrag antworten »

O-Matrix ist angeblich schneller als Matlab, kann ich aber nichts zu sagen.
http://www.omatrix.com/
An sonsten kannst Du, sofern Du denn bei Matlab bleibst, mit tic und toc
den langsamsten Code finden und dann versuchen diesen so weit wie möglich
zu vektorisieren.

mfg
nschlange
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »