cs222 homework

minwise.py

from random import choice
import cPickle as pickle
from scipy.weave import converters
from scipy import weave
import numpy

def ran_sub(S, k):
    res = []
    len_res = 0
    while len_res < k:
        # sample a random element, and if already in list, don't take it
        new = choice(S)
        if new not in res:
            res.append(new)
            len_res += 1
    res.sort()
    return res

headers = ["<algorithm>", "<iostream>", "<map>"]

def run_trial(p, k):
    S = numpy.array(range(p))
    sub = numpy.array(ran_sub(S, k))
    base = numpy.array([0]*k)
    count_min = numpy.array([0]*k);
    code = """
           using namespace std;

           for(int i = 1; i < p; i++){
               /* update base */
               for(int j = 0; j < k; j++){
                   base(j) = (base(j) + sub(j)) % p;
               }

               /* make a sorted copy of base */
               int temp[k];
               for(int j = 0; j < k; j++){
                   temp[j] = base(j);
               }
               sort(temp, temp + sizeof(temp)/sizeof(temp[0]));

               /* update counts, as explained in write-up */
               int indices[k];
               map<int, int> inv_base;

               for(int j = 0; j < k; j++){
                   inv_base[base(j)] = j;
               }
               for(int j = 0; j < k; j++){
                   indices[j] = inv_base[temp[j]];
               }
               inv_base.clear();
               count_min(indices[0]) += p - temp[k - 1] + temp[0];
               for(int j = 1; j < k; j++){
                   count_min(indices[j]) += temp[j] - temp[j - 1];
               }
           }
               return_val = 0;
           """

    res = weave.inline(code, ['S', 'sub', 'base', 'count_min', 'p', 'k'], headers = headers, type_converters = converters.blitz)
    total_funcs = p*(p-1)
    f_1 = round(min(count_min)/float(total_funcs), 7)
    f_2 = round(max(count_min)/float(total_funcs), 7)
    return f_1, f_2

def n_trials(p, k, n):
    filename = 'trials' + str(p) + '_' + str(k) + '_' + str(n) + '.pkl'
    open(filename, 'w').close()
    f = open(filename, 'wb')
    result = []
    for i in xrange(n):
        result.append(run_trial(p, k))
    pickle.dump(result, f)
    f.close()

for p in (49937, 104729):
    for k in (16, 64, 256):
        n_trials(p, k, 1000)