Haskell Quiz/Sampling: Difference between revisions
KetilMalde (talk | contribs) (comments on similar code) |
BrettGiles (talk | contribs) (→The Problem: heading case) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
The object of this problem | The object of this problem is to generate a sorted random number sample. | ||
==The | ==The problem== | ||
* http://www.rubyquiz.com/quiz39.html | * http://www.rubyquiz.com/quiz39.html | ||
| Line 10: | Line 10: | ||
* [[Haskell Quiz/Sampling/Solution Kuklewicz|Chris Kuklewicz]] -- linear performance | * [[Haskell Quiz/Sampling/Solution Kuklewicz|Chris Kuklewicz]] -- linear performance | ||
I did something similar to select random records from a file. Obviously, IO was more time consuming than random generation, so it's probably not a | I did something similar to select random records from a file. Obviously, IO was more time consuming than random generation, so it's probably not a contender. Code is at [http://www.ii.uib.no/~ketil/bioinformatics/repos/rselect/RSelect.lhs]. One optimization I do is that if you ask for more than half the range, the problem is inverted. | ||
I also experimented with selecting the k'th "empty slot" in the Set of already chosen numbers, but in the end it turned out to be faster just to keep selecting numbers until a new one was found. With more access to the internals of Data.Set, this could possibly be competitive. --[[User:KetilMalde|KetilMalde]] 08:00, 31 October 2006 (UTC) | I also experimented with selecting the k'th "empty slot" in the Set of already chosen numbers, but in the end it turned out to be faster just to keep selecting numbers until a new one was found. With more access to the internals of Data.Set, this could possibly be competitive. --[[User:KetilMalde|KetilMalde]] 08:00, 31 October 2006 (UTC) | ||
[[Category:Haskell Quiz|Sampling]] | |||
Latest revision as of 18:43, 13 February 2007
The object of this problem is to generate a sorted random number sample.
The problem
Solutions
- Dan Doel
- Chris Kuklewicz -- linear performance
I did something similar to select random records from a file. Obviously, IO was more time consuming than random generation, so it's probably not a contender. Code is at [1]. One optimization I do is that if you ask for more than half the range, the problem is inverted.
I also experimented with selecting the k'th "empty slot" in the Set of already chosen numbers, but in the end it turned out to be faster just to keep selecting numbers until a new one was found. With more access to the internals of Data.Set, this could possibly be competitive. --KetilMalde 08:00, 31 October 2006 (UTC)