Skip to content

Instantly share code, notes, and snippets.

@amakelov
Created November 19, 2012 22:00
Show Gist options
  • Save amakelov/4114334 to your computer and use it in GitHub Desktop.
Save amakelov/4114334 to your computer and use it in GitHub Desktop.
cs222 homework
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment