Content deleted Content added
m Algorithm D' was still actually algorithm X. I've changed it to D' now. |
Added a python imp. |
||
Line 51:
</ref>
for a practical overview with comparative simulation results.
=== Python Implementation of Knuth's CVM Algorithm ===
<syntaxhighlight lang="python3" line="1">
def algorithm_d(stream, s):
m = len(stream) # We assume that this is given to us in advance.
t = -1 # Note that Knuth indexes the stream from 1.
p = 1
a = 0
buffer = []
while t < (m - 1):
t += 1
a = stream[t]
u = uniform(0,1)
buffer = list(filter(lambda x : x[1] != a, buffer))
if u < p:
if (len(buffer) < s):
buffer.append([u, a])
else:
buffer = sorted(buffer)
p = max(buffer[-1][0],u)
buffer.pop()
buffer.append([u, a])
return len(buffer) / p
</syntaxhighlight>
=== CVM Algorithm ===
| |||