Talk:Knuth's algorithm S: Difference between revisions
Content added Content deleted
(Names) |
(Algorithm R?) |
||
| Line 2: | Line 2: | ||
Are the names all that important for this task? The Tcl implementation uses different names rather than <tt>s_of_n_creator</tt> and <tt>s_of_n</tt> 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). –[[User:Dkf|Donal Fellows]] 06:01, 22 October 2011 (UTC) |
Are the names all that important for this task? The Tcl implementation uses different names rather than <tt>s_of_n_creator</tt> and <tt>s_of_n</tt> 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). –[[User:Dkf|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. -[[User:Abu|Abu]] 12:10, 27 October 2011 (UTC) |
|||
Revision as of 12:10, 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)