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.

Instructions not clear. What is n? Given a set A, I should already know n simply by computing size (uniq A). What are you blathering about >>1? I'm confuz.

This is less difficult than even the first exercise in SICP. I refuse to do something to beneath me. Go scrub somebody else's toilet.

>>3

Go scrub somebody else's toilet.

You're saying that as if it's something one ought to be ashamed of.

Also >>1 you said Mean estimation then you said Median... Are these the same? I think they are not.

>>2
n is defined (in >>1) as the size of the frequency table. You should take this to mean the number of entries (rows) in the table. It is an input, i.e. a formal parameter. The same applies to set, p and q.

>>4
Correct. The title is wrong. Refer to the body text.

What do you mean by estimation? It sounds like you're trying to get inaccurate results. Why not say ``calculation'' instead?

Also, this is piss easy. Are you looking for extreme efficiency or just entertainment?

What the fuck does n, q, and p mean? What the fuck is a `` cumulative frequency table'' and what does it mean to ``construct'' one? The fuck does median and mean estimation mean? What the fuck is set? Proof? Element?

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

>>8
what language is this? IO?

>>9
Yeah.

>>8,10
I LIKE IT!