Talk:Knuth's algorithm S: Difference between revisions
Content added Content deleted
(Algorithm R?) |
|||
| Line 6: | Line 6: | ||
"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 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) |
|||
Revision as of 12:27, 27 October 2011
Names
Are the names all that important for this task? The Tcl implementation uses different names rather than s_of_n_creator and s_of_n for purely syntactic reasons, yet it is clearly the same algorithm, same behavior. I suppose I could dress the stuff up with aliases so that it appears to have those names, but they'd not add anything (and might slow things down). –Donal Fellows 06:01, 22 October 2011 (UTC)
Algorithm R?
"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. -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. --Ledrug 12:27, 27 October 2011 (UTC)