fun with stochastics: randomized elite sampling

relite.py

import random

"""
DATA: 0.23 0.52 0.91 1.07 1.19 1.54 1.65 1.67 1.68 1.68 1.74 1.75 1.82 1.95 2.01
 2.27 2.28 2.47 2.56 2.76 2.80 2.99 3.08 3.27 3.51 3.56 3.65 3.75 3.92 3.93 3.94 
3.9 4.07 4.18 4.23 4.24 4.52 4.54 4.68 4.72 4.78 4.81 4.84 4.87 4.95 4.98 5.23 5.32 
5.38 5.64 5.64 5.69 5.69 5.91 5.92 6.21 6.24 6.38 6.38 6.39 6.39 6.39 6.49 6.72 6.73
6.77 6.87 6.98 7.01 7.05 7.09 7.09 7.16 7.16 7.18 7.22 7.32 7.32 7.68 7.72 7.75 7.84 
7.94 8.04 8.10 8.18 8.37 8.38 8.46 8.50 8.51 8.65 8.70 8.82 9.04 9.09 9.51 9.64 9.83 
9.84 

BEST:  0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.52 0.52 0.52 0.52 0.52 
0.52 0.52 0.52 0.52 0.52 0.91 0.91 0.91 0.91 0.91 0.91 0.91 0.91 0.91 1.07 1.07 
1.07 1.0 7 1.07 1.07 1.07 1.07 1.19 1.19 1.19 1.19 1.19 1.19 1.19 1.19 1.54 1.54 
1.54 1.54 1.65 1.65 1.65 1.65 1.65 1.65 1.65 1.67 1.67 1.67 1.67 1.67 1.67 1.67 
1.68 1.68 1.68 1.68 1.68 1.68 1.68 1.68 1.68 1.68 1.68 1.74 1.74 1.74 1.74 1.74 
1.75 1.75 1.75 1.75 1.75 1.82 1.82 1.82 1.82 1.82 1.95 1.95 1.95 1.95 1.95 1.95 
2.01 2.01 2.01 2.28 8.50 

REST: 1.95 2.47 2.80 3.08 3.51 3.94 3.98 3.98 4.07 4.18 4.23 4.24 4.52 4.52 4.54 
4.72 4.72 4.78 4.84 4.84 4.95 5.23 5.38 5.38 5.64 5.64 5.64 5.64 5.69 5.69 5.91 
5.91 5.92 5.92 6.21 6.21 6.24 6.38 6.38 6.38 6.38 6.39 6.39 6.39 6.39 6.39 6.49 
6.49 6.72 6.73 6.77 6.77 6.87 6.87 6.98 7.01 7.01 7.05 7.05 7.09 7.09 7.09 7.09 
7.16 7.16 7.16 7.16 7.22 7.32 7.32 7.32 7.32 7.68 7.68 7.72 7.75 7.84 7.94 7.94 
8.04 8.10 8.10 8.18 8.37 8.37 8.38 8.38 8.46 8.51 8.65 8.65 8.70 8.82 9.04 9.04 
9.09 9.51 9.64 9.83 9.84
"""

def model(max=10,
          repeats=100):
  return [random.uniform(0,max) 
          for x in range(repeats)]

def eat( data,          # stuff to eat
         want   = 1000, # i want to eat this much datum
         keep   = 100,  # only keep this many
         sample = 10):  # how many times to check new against kept
  def any(l): 
    return int(random.uniform(0,len(l)-1))
  best  = []
  rest  = []
  eaten = 0
  while True:
    for datum in data:
      eaten += 1  
      if len(best) < keep:
        best += [datum]
      else:
        for i in range(sample):
          j = any(best)
          if datum < best[j]:  
            rest += [best[j]]
            best[j] = datum
            break
    if  eaten < want : # not enough seen yet 
       continue      # again!
    return best,rest
   
def pretty(lst):
  return ' '.join(map(lambda x: "%3.2f" % x,
                      sorted(lst)))

data = model()
b,r  = eat(data)
print 'DATA:',pretty(data),"\n\nBEST: ",pretty(b),"\n\nREST:",pretty(r[:100])