| Autor |
Beitrag |
Horst_H
 
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 29.11.10 22:48
Hallo,
mit meien -17 Dioptrien benutze ich im Browser gerne STRG - + 
Gruß Horst
|
|
Xion
Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: Mo 29.11.10 22:54
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
|
|
Horst_H
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 30.11.10 00:25
Hallo,
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:
| program Nichts;
{$IFDEF FPC}
{$Mode delphi}
{$R-}
{$I-}
{$V-}
{$OPTIMIZATION RegVar}
{$OPTIMIZATION Peephole}
{$OPTIMIZATION CSE}
{$OPTIMIZATION ASMCSE}
{$ENDIF}
{$AppType console}
uses
sysutils;
const
cZiehungen = 1000*1000*10;
cAnzahlNamen = 2000000;
cAnzahlNamen1 = cAnzahlNamen-1;
type
tIndexNamen = 0..cAnzahlNamen1;
tIndexNamen_1 = 0..cAnzahlNamen;
tNamenFeld = array[tIndexNamen] of string[10];
tZaehlFeld = array[tIndexNamen] of longint;
tIndexWahrschFeld = array[tIndexNamen_1] of LongInt;
var
Anteile : tZaehlFeld;
IndexFeld : array of tIndexNamen;
ZaehlFeld : tZaehlFeld;
IndexWahrschFeld : tIndexWahrschFeld;
T1,T0 : TDateTime;
SumAnteile,i : longint;
procedure ZaehlfeldLoeschen;
var
i : longINt;
begin
For i in tIndexNamen do
ZaehlFeld[i] := 0;
end;
function GesamtAnteile: longInt;
var
i : longInt;
begin
result := 0;
For i in tIndexNamen do
result := result+Anteile[i];
end;
procedure IndexFeldAufbauen;
var
i,j,k : longint;
begin
setlength(IndexFeld,SumAnteile);
k := 0;
For i in tIndexNamen do
For j := 1 to Anteile[i] do
begin
IndexFeld[k] := i;
k := k+1;
end;
end;
procedure IndexWahrschFeldAufbauen;
var
i,k : longint;
begin
k := 0;
IndexWahrschFeld[0] := 0;
For i in tIndexNamen do
begin
k := k + Anteile[i];
IndexWahrschFeld[i+1] := k; end;
end;
procedure ZaehlFeldAusgabe;
var
i : LongInt;
begin
i := high(tIndexNamen);
writeln(ZaehlFeld[i]:11,ZaehlFeld[i]/cZiehungen*sumAnteile:9:3,Anteile[i]:5);
end;
procedure IndexZiehungen;
var
i : longint;
begin
ZaehlfeldLoeschen;
For i := 1 to cZiehungen do
inc(Zaehlfeld[IndexFeld[random(SumAnteile)]]);
end;
procedure IndexWahrschFeldZiehungen;
var
i,o,u , m: longint;
p : longint;
begin
ZaehlfeldLoeschen;
For i := 1 to cZiehungen do
begin
p := random(sumAnteile);
o := cAnzahlNamen;
u := 0;
repeat
m := (o+u) div 2;
if p >= IndexWahrschFeld[m] then
u := m+1
else
begin
if (p >= IndexWahrschFeld[m-1]) then
break
else
o := m-1;
end;
until o< u;
inc(ZaehlFeld[m-1]);
end;
end;
procedure AnteileBelegen;
var
i : longint;
begin
For i in tIndexNamen do
Anteile[i] := random(116)+10;
end;
begin
randseed := 47110815;
AnteileBelegen;
sumAnteile := GesamtAnteile;
Writeln('Anzahl Farben ',cAnzahlNamen:12);
Writeln('Summe aller Anteile',sumAnteile:12);
Writeln('Anzahl Ziehehungen ',cZiehungen:12);
Writeln;
for i := 0 to 65536 div cAnzahlNamen do
begin
IndexFeldAufbauen;
IndexWahrschFeldAufbauen;
end;
randseed := 47110815;writeln('IndexFeld');
T0 := time;
IndexFeldAufbauen;
IndexZiehungen;
T1 := time;
ZaehlFeldAusgabe;
writeln;
writeln('Laufzeit ',FormatDateTime('hh:mm:ss.zzz',T1-T0));
randseed := 47110815;
writeln('Wahrscheinlichkeitsfeld');
T0 := time;
IndexWahrschFeldAufbauen;
IndexWahrschFeldZiehungen;
T1 := time;
ZaehlFeldAusgabe;
writeln;
writeln('Laufzeit ',FormatDateTime('hh:mm:ss.zzz',T1-T0));
end. |
Ausgabe:
  Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| Anzahl Farben 2000000
Summe aller Anteile 135016937
Anzahl Ziehehungen 10000000
IndexFeld
3 40.505 65
Laufzeit 00:00:02.871
Wahrscheinlichkeitsfeld
3 40.505 65
Laufzeit 00:00:06.240 |
Obwohl es jetzt 2 Mio Farben sind und ein IndexFeld von über 600 Mb entsteht ist diese Version immer noch schneller.
Die Ausgabe: 3 40.505 65
besagt, dass die letzte Farbe 3 mal gezogen wurde umgerechnet 40.505 statt der erwarteten 65, aber es zeigt, das beide Verfahren exakt die gleiche Ausgabe haben.Bei 31 Farben lies sich das ja noch komplett sehen.
Gruß Horst
Edit:
Mit einer anderen random Funktion www.delphipraxis.net...ndom-purepascal.html ist es schneller.
Dies verändert aber die Zahlenfolge.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
| var
myrandseed: cardinal;
function myrandom(range: cardinal): cardinal;
begin
myrandseed := myrandseed * $08088405 + 1;
result := (int64(range) * myrandseed) shr 32;
end; |
Wieder 2 Mio Farben und 10 Mio Ziehungen,
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| Anzahl Farben 2000000
Summe aller Anteile 134948857
Anzahl Ziehungen 10000000
IndexFeld
6 80.969 94
Laufzeit 00h00m02.006s
Wahrscheinlichkeitsfeld
6 80.969 94
mittlere binaere Suchtiefe 19.9512
Laufzeit 00h00m05.888s |
Wenn alles im level1 Cache ist bei 10e8 Durchläufen -> 29 CPU-Takte bei Indexzugriff statt 76.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| Anzahl Farben 255
Summe aller Anteile 17274
Anzahl Ziehungen 100000000
IndexFeld
207817 35.898 36
Laufzeit 00h00m00.965s
Wahrscheinlichkeitsfeld
207817 35.898 36
mittlere binaere Suchtiefe 7.0225
Laufzeit 00h00m06.976s |
|
|
VampireSilence 
Beiträge: 109
Erhaltene Danke: 5
C# (VS 2008 Express), PHP/MySQL, Windows XP
|
Verfasst: Mi 01.12.10 16:15
So, ich habe jetzt mal bei der Herangehensweise von Xion angesetzt und das Ganze als Bisektionsverfahren umgesetzt. Ich habe auch einen Benchmark geschrieben (siehe Code weiter unten) und beide Methoden darin verglichen.
Zum Vergleich habe ich verschiedene int[n] (n: Farben) verglichen, wobei ich die Gewichtung jeweils auf int[n] = n^2 festgelegt habe. Aufgrund der int.MaxValue ergab sich daraufhin auch das Maximum von 1860 Farben. Darüber ist ein Überlauf der Maxima aufgetreten.
Was sich ergeben hat war, dass die Binärsuche (kurz "Scan" genannt) bis n=10 noch geringfügig schneller ist. Bei n=11 und darüber hinaus ist das Bisektionsverfahren schneller (um n=1500 herum [also in dem Bereich, wo es für mich relevant wird], ist das Bisektionsverfahren ganze 34-mal schneller, als der Scan). Die Klasse ("WeightedChance") habe ich dann noch in eine Klassenbibliothek extrahiert und kompiliert, was einen zusätzlichen Geschwindigkeitsschub einbrachte.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| n, Scan [Run/s], Bisect [Run/s]
1, ~5300k, ~4700k
10, ~2750k, ~2700k
100, ~530k, ~1900k
200, ~270k, ~1700k
500, ~113k, ~1600k
1000, ~56k, ~1450k
1500, ~38k, ~1300k |
Gemittelt über: 1.000.000 Berechnungen
Testsytem: Windows 7, Energiesparmodus (Firewall + AVPersonal aktiv), Intel(R) Atom(TM) CPU N450 @ 1.66 GHz
Code: frmMain.cs
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:
| using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace WeightedChance
{
public partial class frmMain : Form
{
public frmMain()
{
InitializeComponent();
}
private void BenchBisect()
{
int _try;
if (!int.TryParse(this.txtColors.Text, out _try))
{
return;
}
int[] Chances = new int[int.Parse(this.txtColors.Text)];
for (int i = 0; i < Chances.Length; i++)
{
Chances[i] = (int)(Math.Pow(i + 1, 2.0) % int.MaxValue);
}
WeightedChance wc = new WeightedChance(Chances);
int runs = 1000000;
this.txtResult.Text = "Sei i(k) = k^2.";
DateTime start = DateTime.Now;
for (int i = 0; i < runs; i++)
{
wc.NextBisect();
}
DateTime end = DateTime.Now;
this.txtResult.Text += "\r\n" + end.Subtract(start).TotalMilliseconds + " ms needed.\r\n" + (int)(runs / end.Subtract(start).TotalSeconds) + " Runs per Seconds";
}
private void Benchmark()
{
int _try;
if (!int.TryParse(this.txtColors.Text, out _try))
{
return;
}
int[] Chances = new int[int.Parse(this.txtColors.Text)];
for (int i = 0; i < Chances.Length; i++)
{
Chances[i] = (int)(Math.Pow(i + 1, 2.0) % int.MaxValue);
}
WeightedChance wc = new WeightedChance(Chances);
int runs = 1000000;
this.txtResult.Text = "Sei i(k) = k^2.";
DateTime start = DateTime.Now;
for (int i = 0; i < runs; i++)
{
wc.Next();
}
DateTime end = DateTime.Now;
this.txtResult.Text += "\r\n" + end.Subtract(start).TotalMilliseconds + " ms needed.\r\n" + (int)(runs / end.Subtract(start).TotalSeconds) + " Runs per Seconds";
}
private void btnCheck_Click(object sender, EventArgs e)
{
this.Benchmark();
}
private void btnCheckBisect_Click(object sender, EventArgs e)
{
this.BenchBisect();
}
}
public class WeightedChance
{
int[] Maximum = new int[Int16.MaxValue];
int[] Minimum = new int[Int16.MaxValue];
int maxChance;
Random ran = new Random();
int check;
public WeightedChance(int[] ChanceData)
{
int lowBound = 0;
int id = 0;
foreach (int entry in ChanceData)
{
if (entry == 0)
{
continue;
}
Minimum[id] = lowBound;
Maximum[id++] = lowBound + entry - 1;
lowBound += entry;
}
if (lowBound == 0)
{
throw new Exception("Error 2: No chance for getting anything.");
}
maxChance = id - 1;
}
public int Next()
{
int hit = ran.Next(0, Maximum[this.maxChance]);
int id = 0;
while (true)
{
if (id == this.Maximum.Length)
{
throw new Exception("Error 1: Unexpected range value. Report this bug with source code, if possible.");
}
if (this.Maximum[id] < hit)
{
id++;
continue;
}
else
{
return id;
}
}
}
public int NextBisect()
{
int hit = ran.Next(0, Maximum[this.maxChance]);
int min = 0, max = this.maxChance;
while (true)
{
check = (min + max) / 2;
if (min > max)
{
check = min;
}
if (Minimum[check] <= hit && Maximum[check] >= hit)
{
return check;
}
else
{
if (Minimum[check] > hit)
{
max = check - 1;
}
else
{
min = check + 1;
}
}
}
}
}
} |
Code: frmMain.Designer.cs
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:
| namespace WeightedChance
{
partial class frmMain
{
private System.ComponentModel.IContainer components = null;
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}
#region Vom Windows Form-Designer generierter Code
private void InitializeComponent()
{
this.txtResult = new System.Windows.Forms.Label();
this.btnCheck = new System.Windows.Forms.Button();
this.btnCheckBisect = new System.Windows.Forms.Button();
this.txtColors = new System.Windows.Forms.TextBox();
this.label1 = new System.Windows.Forms.Label();
this.SuspendLayout();
this.txtResult.AutoSize = true;
this.txtResult.Location = new System.Drawing.Point(12, 38);
this.txtResult.Name = "txtResult";
this.txtResult.Size = new System.Drawing.Size(16, 13);
this.txtResult.TabIndex = 0;
this.txtResult.Text = "...";
this.btnCheck.Location = new System.Drawing.Point(195, 12);
this.btnCheck.Name = "btnCheck";
this.btnCheck.Size = new System.Drawing.Size(75, 23);
this.btnCheck.TabIndex = 1;
this.btnCheck.Text = "Scan";
this.btnCheck.UseVisualStyleBackColor = true;
this.btnCheck.Click += new System.EventHandler(this.btnCheck_Click);
this.btnCheckBisect.Location = new System.Drawing.Point(276, 12);
this.btnCheckBisect.Name = "btnCheckBisect";
this.btnCheckBisect.Size = new System.Drawing.Size(75, 23);
this.btnCheckBisect.TabIndex = 2;
this.btnCheckBisect.Text = "Bisect";
this.btnCheckBisect.UseVisualStyleBackColor = true;
this.btnCheckBisect.Click += new System.EventHandler(this.btnCheckBisect_Click);
this.txtColors.Location = new System.Drawing.Point(114, 14);
this.txtColors.Name = "txtColors";
this.txtColors.Size = new System.Drawing.Size(75, 20);
this.txtColors.TabIndex = 3;
this.label1.AutoSize = true;
this.label1.Location = new System.Drawing.Point(12, 17);
this.label1.Name = "label1";
this.label1.Size = new System.Drawing.Size(96, 13);
this.label1.TabIndex = 4;
this.label1.Text = "Anzahl Farben (=k)";
this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
this.ClientSize = new System.Drawing.Size(540, 200);
this.Controls.Add(this.label1);
this.Controls.Add(this.txtColors);
this.Controls.Add(this.btnCheckBisect);
this.Controls.Add(this.btnCheck);
this.Controls.Add(this.txtResult);
this.Name = "frmMain";
this.Text = "VampireSilence WeightedChance (Benchmark)";
this.ResumeLayout(false);
this.PerformLayout();
}
#endregion
private System.Windows.Forms.Label txtResult;
private System.Windows.Forms.Button btnCheck;
private System.Windows.Forms.Button btnCheckBisect;
private System.Windows.Forms.TextBox txtColors;
private System.Windows.Forms.Label label1;
}
} |
Einziger Wermutstropfen ist vllt, dass die Rohdaten aufsteigend geordnet sein müssen, aber das lässt sich ja relativ schnell realisieren. Eine Binary spare ich mir jetzt mal, die könnt ihr ja jetzt selbst kompilieren und ggf. auch direkt die Methoden für die beiden Benchmarks mit einfügen.
Ich weiss nur leider nicht genau, wie ich die Ergebnisse jetzt in CPU-Takte etc. umrechne bzw. wie ich diese ermittle. Wäre nett, wenn das noch einer von euch tun könnte, um dieses kleine Experiment zu vervollständigen. 
Danke nochmal für die Hilfe und die Anregung !
mfg
- VampireSilence
|
|
Horst_H
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 01.12.10 18:28
Hallo,
ich erkenne Deine Binärsuche in Zeile 131..154 nicht, das ist eine lineare Suche.
Die Binäresuche ist das Bisektionsverfahren.
Die Cpu Take bestimmst Du einfach aus der Laufzeit/n * CPU-Frequenz
200, ~270k, ~1700k
500, ~113k, ~1600k
Also 1700k 1/s -> Laufzeit = 1/(1700e3 1/s)= 578 ns * 1,66 Ghz = 959 CPU-Takte
//Bei mir Farben 2Mio ( 19 mal Bisec )Laufzeit 6,2s/ 10 Mio = 620 ns * 2.9 Ghz = 1800 CPU-Takte
//Bei mir Farben 255 ( 7 mal Bisec )Laufzeit 6.976s/ 100 Mio = 69,7 ns * 2.9 Ghz = 202 CPU-Takte
// also dauert einmal Bisec etwa 133 Takte bei Dir ~ 80..90 CPU-Takte
Das Gewicht ist nicht n^2, sondern (2*n-1) = (n^2 -(n-1)^2 ), also bezogen auf den Vorgänger.
Der relative Anteil (2*n-1)/ Summe( i= 1..n) i^2 )
int.Maxvalue müßte doch 2.1e9 sein dann ist Wurzel daraus 46340.
Das Verfahren huuuuuuh ist eindeutig schneller bei ganzzahligen Gewichten, die nicht ins Unendliche ( Summe aller Gewichte ) streben.
Gruß Horst
|
|
VampireSilence
Beiträge: 109
Erhaltene Danke: 5
C# (VS 2008 Express), PHP/MySQL, Windows XP
|
Verfasst: Mi 01.12.10 20:27
Achso, ich dachte die Binärsuche wäre das lineare Verfahren. Aber das Gewicht ist definitiv n^2, wie du in Zeile 32 und 65 nachlesen kannst.
Ein paar Fragen noch dazu:
Wie nennt man denn dann die lineare Suche ?
Was meinst du mit relativer Anteil ?
Und was berechnest du mit der Wurzel der int.MaxValue ?
mfg
- VampireSilence
|
|
Horst_H
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 01.12.10 21:43
Hallo,
| Zitat: | | Wie nennt man denn dann die lineare Suche ? |
lineare Suche nennt man lineare Suche.
binäre Suche ist dein Bisec genanntes Verfahren.
Einfache Intervallschachtelung.
Du hast recht mit deinen Gewichten wenn entry der Inhalt von ChanceData[id] ist:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| foreach (int entry in ChanceData)
{
if (entry == 0)
{
continue;
}
Minimum[id] = lowBound;
Maximum[id++] = lowBound + entry - 1;
lowBound += entry;
} |
Wenn chances= 1,4,9,16,25... ist, dann ist
Minimum[] = 0,1,(+4)5,(+9)14,...
Maximum[] = 0,(+4)4,(+9)13,(+16)29,..
| Zitat: | | Was meinst du mit relativer Anteil ? |
Summe Quadratzahle = n*(n+1)*(2*n+1)/6
Sei chances= 1,4,9,16,25 dann ist die Summe 5*6*11 /6 = 55
Dann ist der relative Anteil der Treffer auf chances[4] = 25 eben 25/55 = 5/11 also fast die Hälfte aller Treffer.
| Zitat: | | Und was berechnest du mit der Wurzel der int.MaxValue ? |
Du sagst Dein Program steigt bei n= 1860 aus.
Jetzt sehe ich das mit der Maximumbestimmung richtig, und kann es jetzt berechnen
n*(n+1)*(2*n+1)/6 muss kleiner int.Maxvalue sein.
Grob gerechent (3* int.Maxvalue)^(1/3) = 1860,73 aha? AHA!
Gruß Horst
EDIT: Mit Int64 kommst Du für die Felder Minimum und Maximum weiter bis knapp über 3 Millionen.
Aber Du brauchst nur ein Feld der Beiden, das um einen Feldplatz länger ist. Es beginnt dann mit 0 und entspricht Deinem Minimum-Feld, wo am Ende noch der höchste Wert ( bei mit sumAnteile, bei Dir der letzte Wert von lowbound) eingetragen wird.
Es wird bei der Binärsuche erst auf >= verglichen , wenn das nicht der Fall ist, muss es kleiner sein, also <=(Wert-1) , wenn es dann größer als der Wert darunter ist ( bei Dir Minimum ) ist es passend.
Delphi-Quelltext
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:
| procedure IndexWahrschFeldZiehungen;
var
i,o,u , m: longint;
p : longint;
begin
ZaehlfeldLoeschen;
For i := 1 to cZiehungen do
begin
p := random(sumAnteile);
o := cAnzahlNamen;
u := 0;
repeat
m := (o+u) div 2;
if p >= IndexWahrschFeld[m] then
u := m+1
else
begin
if (p >= IndexWahrschFeld[m-1]) then
break
else
o := m-1;
end;
until o< u;
inc(ZaehlFeld[m-1]);
end;
end; |
|
|
VampireSilence
Beiträge: 109
Erhaltene Danke: 5
C# (VS 2008 Express), PHP/MySQL, Windows XP
|
Verfasst: Do 02.12.10 13:13
Nachtrag. Ich habe die binäre Suche (Nochmal Sorry, ich habs nicht so mit den Begrifflichkeiten) jetzt so umgeschrieben, dass sie nur noch die Maximum[]-Werte benötigt. Aufgrund einer Ausnahme in Zeile 168, für den Fall check=0, musste ich jetzt allerdings eine Ausnahmecondition schreiben, die alles in allem so aussieht:
C#-Quelltext
1:
| if ((check == 0 || Maximum[check - 1] < hit) && Maximum[check] >= hit) |
Unter der Annahme, dass (Maximum[check - 1] < hit) genau so teuer ist, wie (Minimum[check] <= hit), kostet mich die zusätzliche Condition (check == 0) allerdings fast 40% der Geschwindigkeit. Der einzige Vorteil ist, dass ich mir die Definition (und damit auch den Speicher) für Minimum[] spare. Wie so oft ist es nun also die Entscheidung zwischen Speicher und Performance. Und da muss ich sagen, dass ich einfach mehr Wert auf die Peformance lege, als auf den Speicher, zumal der Speicherunterschied nahezu marginal ist.
mfg
- VampireSilence
|
|
Horst_H
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 02.12.10 13:30
Hallo,
ich habe darüber auch geschrieben, dass ich das Feld eine Position länger gemacht habe.
Deshalb ist bei mir der check nicht notwendig.
Gruß Horst
|
|
VampireSilence
Beiträge: 109
Erhaltene Danke: 5
C# (VS 2008 Express), PHP/MySQL, Windows XP
|
Verfasst: Do 02.12.10 13:59
Ok, das is nen guter Trick. Jetzt hatte ich allerdings das Problem, dass die Gewichtung nach (Maximum[n] = lowBound + entry - 1) im Falle entry=0 auch Maximum[n] = 0 ergibt. Mein Array beginnt also mit den Werten [0, 0, ..] und das führt zu einer Endlosschleife. Das Problem habe ich jetzt gelöst, indem ich eine einzelne Condition vor die Schleife eingefügt habe, die folgendermaßen aussieht:
C#-Quelltext
1:
2:
3:
4:
| if (hit == 0)
{
return min;
} |
min habe ich dabei außerdem auf 1 korrigiert. Trotzdem habe ich jetzt allerdings eine Geschwindigkeitseinbuße von etwas mehr als 50% und das kann ich mir nicht erklären. Die Einzige Möglichkeit wäre die Operation (check - 1), aber das kann doch nicht so teuer sein, oder doch ?
mfg
- VampireSilence
|
|
|
Horst_H
