from __future__ import division

import random
import psyco

psyco.full()

num_sites = 50000
trials = 50
num_comps = 50
popular_limit = 100

fracs = [1.0/(i+1) for i in range(num_sites)]
max = sum(fracs)

cdf = [0,]
for i in fracs:
  cdf.append(float(i)/max + cdf[-1])
cdf.remove(0)

lists = []
for c in range(num_comps):
  site_list = []
  for i in range(trials):
    r = random.random()
    site_num = len([k for k in cdf if k < r])
    if site_num < popular_limit:
      site_num = (site_num + c) % popular_limit
    site_list.append(site_num + 5) #num in list does weird things when num = 0,1
  lists.append(site_list)

hits = 0
total = 0
for list in lists:
  for i in range(len(list)):
    prev_cached = False
    for other_list in lists:
      if other_list == list:
        continue
      if list[i] in other_list[0:i]:
        prev_cached = True
    if prev_cached == True:
      hits += 1
    total += 1