Hallo,
michl hat das doch schon richtig angedeutet.Du musst nur noch eine Summenwahrscheinlichkeit berechnen { und diese auf 0..1 skalieren, EDIT muss man nicht, sondern die maximale Summe merken } , dann kannst Du mit binärer Suche finden.
Ich habe mal eine Code-Schnipsel für Freepascal gepinselt.
Code: Alles auswählen
const
oBcnt = 1024*1024;
type
tWiIdx = 0..oBcnt-1;
tSumWiIdx = 0..oBcnt;
tWicht = array[tWiIdx] of double;
tSumWi = array[tSumWiIdx] of double;
var
Wichtungen : tWicht;
SumWi : tSumWi;
procedure InitWicht(var WI : tWicht);inline;
var
i : NativeInt;
begin
For i in tWiIdx do
Wi[i] := random;
end;
function InitSumWi(var WI : tWicht;var SWi: tSumWi):double;
var
i : NativeInt;
SumWi: double;
begin
SWi[0] := 0.0;
SumWi := 0.0;
For i in tWiIdx do
Begin
SumWi := Sumwi+WI[i];
SWi[i+1]:= Sumwi;
end;
InitSumWi:= Sumwi;
end;
function FindObj(x :double;var SWi: tSumWi):tWiIdx;
// Gibt den Index auf das passende Objekt zurueck
var
l,m,u: NativeUint;
Begin
l := Low(tSumWi);
u := High(tSumWi);
m := (l+u) DIV 2;
repeat
if (x>=SWi[m]) then
l := m
else
u := m;
m := (l+u) DIV 2;
until (m=l) OR (m=u);
IF x-SWi[m]< 0.0 then
Writeln(m,'Fehler',SWi[m]:10:7,x:12:10);
FindObj:= m;
end;
var
MaxSumwi,x: double;
i: NativeInt;
Begin
randomize;
InitWicht(Wichtungen);
MaxSumwi:= InitSumWi(Wichtungen,SumWi);
For i := 1 to 1000000 do
FindObj(MaxSumwi*Random,SumWi);
x := 0.0000*MaxSumwi;
i := FindObj(x,SumWi);
writeln(x:12:4,i:8,SumWI[i]:12:4,SumWI[i+1]:12:4);
x := 0.5*MaxSumwi;
i := FindObj(x,SumWi);
writeln(x:12:4,i:8,SumWI[i]:12:4,SumWI[i+1]:12:4);
x := MaxSumwi;
i := FindObj(x,SumWi);
writeln(x:12:4,i:8,SumWI[i]:12:4,SumWI[i+1]:12:4);
end.
Mit der Ausgabe:
Code: Alles auswählen
time ./test
0.0000 0 0.0000 0.6751
261993.2758 524240 261992.5269 261993.4640
523986.5516 1048575 523986.5322 523986.5516
real 0m0.445s
Die 1'000'000 Suchen sind also recht fix.Ich habe keine 8 MB Level 2 oder gar 3 Cache.Für eine Suche werden bei 2^20 Elementen auch immer 20 Schritte gebraucht.
Wie man jetzt aber verhindern will, dass nicht zweimal das selbe gewählt werden kann, ist dann aber viel aufwendiger.
Gruß Horst