Talk:Knuth's algorithm S: Difference between revisions
Content added Content deleted
(→Names: rigid non-essential requirement) |
|||
| 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) |
||
: The task description is questionable. "Return a funciton" is not necessarily desirable or even possible for some languages, not to mention fixed function names. A names like "s_of_n" isn't all that descriptive to start with, and is patentedly against naming conventions in different languages, I don't see the point of sticking with them. --[[User:Ledrug|Ledrug]] 03:01, 12 November 2011 (UTC) |
|||
=== Algorithm R? === |
=== Algorithm R? === |
||
Revision as of 03:01, 12 November 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)
- The task description is questionable. "Return a funciton" is not necessarily desirable or even possible for some languages, not to mention fixed function names. A names like "s_of_n" isn't all that descriptive to start with, and is patentedly against naming conventions in different languages, I don't see the point of sticking with them. --Ledrug 03:01, 12 November 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)