PROG×MATHS CHALLENGE←Mean Estimation.

Challenge: estimate the median of a set by constructing a cumulative frequency table of size n.
Deadline: June 21.

Basic Task
Inputs: set, n
Output: estimation of the median of set

Bonus Task
Input: set, n, q
Output: estimation of quartile q of set

Triple Word Score
Input: set, n, p
Output: estimation of percentile p of set

Inputs may be re-ordered, solutions may be rendered as methods on sets. Sample random sets of lengths 10, 100 and 1000 will each be tested.

Scoring: Entries will be scored on accuracy, number of tasks completed, readability and performance. Bonus points for Scheme entries that perform better in your implementation of Scheme than in a popular implementation of your choosing. Comparison may be limited to a single aspect (speed, memory use, etc.) No proof is required.

Winner Selection: Scores will be ignored, and the winner will be chosen by trial by flamewar over language choice or any other pedantic aspect of the participants choice. Notwithstanding the above, any correct entry written in Fjölnir producing better results for the Triple Word Score task than picking an element from set at random is an automatic immediate win. In this event the flame war shall still be had for the entertainment of the participants, and for the purposes of choosing runners-up.

Range

List freqTable := method(n, FreqTable fromList(self, n))
List getPx := method(x,
self sort at(self size * (x / 100))
)

FreqTableBucket := Object clone do(
incrPop := method(pop = pop + 1)
new := method(int,ord,
bucket := self clone do(
pop := 0
cum := 0
)

bucket ord := ord
bucket min := int * (ord -1)
bucket max := int * (ord)

bucket
)

getNth := method(n,
(n - (cum - pop)) * (max - min) / pop + min
)
)

FreqTable := Object clone do(
buckets := nil
max := nil
min := nil

initialize := method(ls,n,
n ifNil(n = 4)
self max := ls max
self min := ls min
self int := (max - min) / n
self buckets := 1 to(n) map(ord, FreqTableBucket new(int, ord))

ls foreach(x,
bucketNo := ((x - min) / int) ceil -1
buckets at(bucketNo) incrPop
)

acc := 0
buckets foreach(b,
acc = acc + b pop
b cum = acc
)
self
)

fromList := method(ls,n,
table := self clone
table initialize(ls,n)
)

estimatePx := method(p,
nth := (p * buckets last cum / 100) ceil
bin := buckets select(cum >= nth) first

bin getNth(nth)
)

estimateQ := method(q,
self estimatePx(q * 25)
)

estimateMedian := method(
self estimateQ(2)
)
)

genRandomSet := method(nElems,
1 to(nElems) map(Random value)
)

set := genRandomSet(100)
ft := set freqTable

("median " .. ft estimateMedian) println
("actual " .. set getPx(50)) println
"" println
("q3 " .. ft estimateQ(3)) println
("actual " .. set getPx(75)) println
"" println
("p80 " .. ft estimatePx(80)) println
("actual " .. set getPx(80)) println
"" println