Anonymous user
Talk:Knuth's algorithm S: Difference between revisions
→BBC BASIC and 100,000 Functions kept around
(→Names: rigid non-essential requirement) |
|||
Line 9:
"Algorithm S" in Knuth, Vol 2, 3.4.2 is the one with a known number of records. I think it is "Algorithm R" (Reservoir sampling) what we need here. -[[User:Abu|Abu]] 12:10, 27 October 2011 (UTC)
: Algorithm R has a second pass -- it's not a crucial distinction, though. Mathematically this task, R and S are all the same thing anyway, but maybe R is a better fit. --[[User:Ledrug|Ledrug]] 12:27, 27 October 2011 (UTC)
==BBC BASIC and 100,000 Functions kept around==
Hi RichardRussell, I read your comment:
:''"At each of the 100000 repetitions not only is a new function created but also new copies of its PRIVATE variables index% and samples%(). Creating such a large number of variables at run-time impacts adversely on execution speed and isn't to be recommended, other than to meet the artificial requirements of the task."''
I took a look at your example and it seems that function <code>FNs_of_n_creator</code> calculates and keeps each random sample from ten and you keep 100000 of them around before extracting their data for binning.
The Python example, (amongst others e.g. Ada), bin results as they go along and so don't have to keep so many functions around - maybe the BBC basic example could follow a similar scheme?
The task tries to:
# Introduce what could be a new algorithm to implementers
# Quickly show that the routine can generate a non-biased sample (without using too much stats).
It could well be thought of as artificial, but I hope I've explained the purpose. --[[User:Paddy3118|Paddy3118]] 07:45, 5 November 2012 (UTC)
| |||