Horst_H - Di 29.11.05 11:43
Hallo,
Hier [
http://www.informatik.hu-berlin.de/~luetzken/sas/sas-smas.html] ist ja beschrieben, worum es geht.
Alpha - Quantil ist ja fuer Alpha = 0.5 der Midian.
Das erinnert an Quicksort, wobei das Alpha Quantil X(i) der Pivot ist.
Falls man von der selben Menge Werten verschiedene Quantile braucht, ist sortieren und anschliessendes direktes zugreifen ueber einen gerechneten Index das Leichteste.
Dazu musst Du Werte und alte Position zusammenfassen.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
| type
tWert : integer; tSortWert : packed record
pWert : ^tWert;
OrgIndex : integer
end;
tSortFeld : array of tSortWert;
var
Sortfeld : tSortFeld;
WertFeld : array of tWert;
Laenge := High(WertFeld)-Low(WertFeld) +1;
setlength(SortFeld,Laenge );
For i := Low(WertFeld) to High(WertFeld) do
With SortFeld[i-Low(WertFeld)] do
begin
pWert := @WertFeld[i];
OrgIndex := i;
end;
Sort(SortFeld,0,Laenge-1); |
Falls nur ein Alpha Quantil gefragt ist, kann man natuerlixch schneller daran kommen.Z.B. eine Art Quicksort, wobei aber nur der Abschnitt weiter rekursiv untersucht wird der zielführend ist.
Dein Alpha-Quantil liegt ja fest und laesst sich in einen Index des Sortfeldes umrechnen.
In der Abbruchbedingung von quicksort partition steht links direkt fuer das Alpha-Quantil.
Falls links das Alpha quantil dann ist alles gut,
sonst
.falls links > gesuchtespartition(0..links-1) falls links > gesuchtes
.sonst partition(links+1..rechts)
Im schlimmsten Fall wird es Alphaquantilindex mal aufgerufen, falls man immer genau das verbliebene Maximum als Pivot erwischt.
Gruss Horst
Alternativ Radixsort maessig.
Bestimme Minimum, Maximum um Spannweite zu den Wertebereich zu bestimmen, falls diese nicht schon ausreichend genau bekannt sind.
Teile diesen Bereich in 1000(000 wie es beliebt, falls es Sinn macht) Teile.
Jetzt ein Durchgang und zählen, wie haeufig Werte in seinen zugehoerigen Wertebereich fallen.
Der Index laesst sich ja berechnen aus
Delphi-Quelltext
1:
2:
3:
4:
5:
| ANZTEILE := 1000-1;
Zaehlfeld : array [0..ANZTEILE] of integer;
For i := Low(WertFeld) to High(WertFeld) do
inc(ZaehlFeld(round((Wert[i]-Minimum)/Spannweite*ANZTEILE)) |
Jetzt aus den Teilen die Summenhaufikeit bestimmen in welchen Abschnitt das gesuchte Alphaquantil liegen muss.
Sei dies zum Beispiel im Fach 763 von 1000 mit 12 Treffern.
Dann kann man in einem zusaetzlichen Durchgang genau diese 12 finden.