Created
July 28, 2017 00:24
-
-
Save vznvzn/b9c48d93bac7943ebb37434cf3be64cb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'statsample' | |
def f2(n) | |
return n.odd? ? (n * 3 + 1) / 2 : n / 2 | |
end | |
def f1(n) | |
n = (n * 3 + 1) / 2 if (n.odd?) | |
n /= 2 if (n.even?) | |
return n | |
end | |
def dense(w, d) | |
w2 = w - 1 | |
a = (0...w2).to_a | |
s = '0' * w2 | |
(1..(d * w - 1)).map { a.delete_at(rand(a.size)) }.each { |x| s[x, 1] = '1' } | |
return ('1' + s).to_i(2) | |
end | |
def stat(l) | |
l = [0] if (l.empty?) | |
t = t2 = 0 | |
l.each \ | |
{ | |
|x| | |
t += x | |
t2 += x ** 2 | |
} | |
c = l.size | |
a = t.to_f / c | |
z = t2.to_f / c - a ** 2 | |
sd = Math.sqrt(z < 0 ? 0 : z) | |
return a, sd, l.max.to_f, l.min.to_f | |
end | |
def stat2(l, t, n) | |
return Hash[[["a#{n}", "sd#{n}", "mx#{n}"], stat(l)[0..2].map { |x| x / t }].transpose] | |
end | |
def d(s) | |
c = s.split('').select { |x| x == '1' }.size | |
d = c.to_f / s.length | |
return d | |
end | |
def data(n) | |
ns = n.to_s(2) | |
nl = ns.length | |
m = nl / 2 | |
nsh = ns[0..m] | |
nsl = ns[m..-1] | |
asdm1 = stat2(ns.split(/0+/).map { |x| x.length }, nl, 1) | |
l1 = ns.split(/1+/) | |
l1.shift | |
asdm0 = stat2(l1.map { |x| x.length }, nl, 0) | |
return {'n' => n, 'ns' => ns, 'nl' => nl, 'd' => d(ns), 'dh' => d(nsh), 'dl' => d(nsl)}.merge(asdm1).merge(asdm0) | |
end | |
def pair2(n, m) | |
n1 = n | |
m.times { n = f2(n) } | |
x = {0 => data(n1), 1 => data(n)} | |
x[1]['wr'] = x[1]['nl'].to_f / x[0]['nl'].to_f | |
return x | |
end | |
def pair(d, m) | |
w = 100 | |
return(pair2(dense(w, d), m)) | |
end | |
def dist(m) | |
w = 100 | |
d = 0.0 | |
c = 100 | |
l = [] | |
c.times \ | |
{ | |
|i| | |
l << pair(i.to_f / (c - 1), m) | |
} | |
# $stderr.puts("#{l.size} pts") | |
return l | |
end | |
def sum(l) | |
t = 0.0 | |
l.each { |x| t += x } | |
return t | |
end | |
def av(l) | |
return nil if (l.empty?) | |
return sum(l) / l.size | |
end | |
def corr(l, y1) | |
yp = "#{y1}_p" | |
ye = "#{y1}_e" | |
xav = av(l.map { |x| x[y1] }) | |
yav = av(l.map { |x| x[yp] }) | |
tx = ty = txy = e = 0.0 | |
m = nil | |
l.each \ | |
{ | |
|z| | |
x = z[y1] | |
y = z[yp] | |
txy += (x - xav) * (y - yav) | |
tx += (x - xav) ** 2 | |
ty += (y - yav) ** 2 | |
z[ye] = (x - y) | |
e1 = z[ye] | |
e += e1 | |
m = [m, e1.abs].compact.max | |
} | |
r = txy / (Math.sqrt(tx) * Math.sqrt(ty)) | |
e /= l.size | |
return {'r' => r, 'e_a' => e, 'e_m' => m} | |
end | |
def dot(x, z) | |
t = z['c'] | |
(z.keys - ['c']).each { |v| t += z[v] * x[v] } | |
return t | |
end | |
def predict(l, vy, z) | |
l.each \ | |
{ | |
|x| | |
x[1]["#{vy}_p"] = dot(x[0], z) | |
} | |
end | |
def fit(l, vx, vy) | |
a = {} | |
vx.each { |v| a[v] = l.map { |x| x[0][v] }.to_vector() } | |
a[vy] = l.map { |x| x[1][vy] }.to_vector() | |
ds = a.to_dataset() | |
r = Statsample::Regression.multiple(ds, vy) | |
# $stderr.puts(r.summary) | |
z = r.coeffs.merge({'c' => r.constant}) | |
predict(l, vy, z) | |
a = corr(l.map { |x| x[1] }, vy) | |
return z.merge!(a) | |
end | |
def fmt(a) | |
a2 = {} | |
a.each \ | |
{ | |
|k, v| | |
a2[k] = v.is_a?(Numeric) ? sprintf("%.3g", v).to_f : v | |
} | |
return a2 | |
end | |
def fit1(v, x, l) | |
a = fit(l, v, x) | |
l1 = l.map { |y| y[1][x] } | |
a.merge!({'mn' => l1.min, 'mx' => l1.max}) | |
# $stderr.puts(fmt({'x' => x}.merge(a.select { |k, v| ['r', 'e_m', 'e_a', 'mn', 'mx'].member?(k) })).inspect) | |
return a | |
end | |
def model(a) | |
(a['v'] + ['wr']).each \ | |
{ | |
|x| | |
a[x] = fit1(a['v'], x, a['l']) | |
} | |
# $stderr.puts | |
return a | |
end | |
def out(fn, a) | |
return if (fn.nil?) | |
f = File.open(fn, 'a') | |
f.puts(a.keys.join("\t")) if (f.size == 0) | |
if (a.nil?) | |
f.puts | |
else | |
f.puts(a.values.join("\t")) | |
end | |
f.close | |
end | |
def count(m) | |
a = {'l' => dist(m), 'v' => ['a1', 'a0', 'dh', 'dl', 'sd0', 'sd1', 'mx1']} | |
a = model(a) | |
return a | |
end | |
def opt(m, a) | |
l = [] | |
a['l'].size.times \ | |
{ | |
|i| | |
l << {'ns' => a['l'][i][0]['ns'], 'wr_e' => a['l'][i][1]['wr_e']} | |
} | |
c = 20 | |
w = 100 | |
1000.times \ | |
{ | |
|n| | |
c = l.size / 4 | |
l.sort_by! { |x| x['wr_e'] } | |
# l.reverse! | |
x = rand(c) | |
y = rand(c) | |
y += 1 if (y == x) | |
ns = ns1 = ns2 = nil | |
case rand(3) | |
when 0 | |
ns1 = l[x]['ns'] | |
ns = ns1.dup | |
i = rand(w - 1) + 1 | |
ns[i, 1] = (ns1[i, 1].to_i ^ 1).to_s | |
when 1 | |
ns1 = l[x]['ns'] | |
ns2 = l[y]['ns'] | |
ns = '' | |
w.times \ | |
{ | |
|i| | |
ns[i, 1] = [ns1[i, 1], ns2[i, 1]][rand(2)] | |
} | |
when 2 | |
ns1 = l[x]['ns'] | |
ns2 = l[y]['ns'] | |
i = rand(w) | |
ns = ns1[0...i] + ns2[i..-1] | |
end | |
w2 = ns.to_i(2).to_s(2).length | |
raise if (w2 != w) | |
next if (l.map { |x| x['ns'] }.member?(ns)) | |
x = pair2(ns.to_i(2), m) | |
(a['v'] + ['wr']).each \ | |
{ | |
|vy| | |
z = a[vy].select { |k, v| (a['v'] + ['c']).member?(k) } | |
predict([x], vy, z) | |
corr([x[1]], vy) | |
} | |
l.pop if (l.size > 2000) | |
l << {'ns'=> ns, 'wr_e' => x[1]['wr_e']} | |
# puts([l[0]['wr_e'], l[-1]['wr_e'], d(ns), ns].join("\t")) if (n % 40 == 0) | |
$stdout.flush | |
} | |
return l.first | |
end | |
def detect(x1, a, j, l) | |
x1 = x1.dup | |
i = 0 | |
c = 500 | |
x1['nl'] = 1 | |
loop \ | |
{ | |
x2 = {} | |
(a['v'] + ['wr']).each \ | |
{ | |
|vy| | |
x2[vy] = dot(x1, a[vy].select { |k, x| (a['v'] + ['c']).member?(k) }) | |
x2[vy] += l[j][1]["#{vy}_e"] if (!j.nil?) | |
x2[vy] = a[vy]['mn'] if (x2[vy] < a[vy]['mn']) | |
x2[vy] = a[vy]['mx'] if (x2[vy] > a[vy]['mx']) | |
} | |
x2['nl'] = x1['nl'] * x2['wr'] | |
x1 = x2 | |
i += 1 | |
break if (x1['nl'] < 1 || i == c) | |
} | |
return i == c ? nil : i | |
end | |
def count2(l, a, y) | |
t2 = 0 | |
l.size.times \ | |
{ | |
|i| | |
t2 += 1 if (detect(l[i][0], a, nil, l).nil?) | |
} | |
t = 0 | |
l2 = [] | |
l.size.times \ | |
{ | |
|i| | |
l1 = [] | |
l.size.times \ | |
{ | |
|j| | |
x = detect(l[i][0], a, j, l) | |
l1 << j if (x.nil?) | |
} | |
t += l1.size | |
l2 << l1 | |
$stderr.puts([i, t, l1].inspect) | |
} | |
return {"t#{y}" => t, "t#{y}2" => t2, "l#{y}" => l2} | |
end | |
def stat1(l) | |
return Hash[[['a', 'sd', 'mx', 'mn'], stat(l)].transpose] | |
end | |
def test(m, a) | |
l = dist(m) | |
(a['v'] + ['wr']).each \ | |
{ | |
|vy| | |
z = a[vy].select { |k, v| (a['v'] + ['c']).member?(k) } | |
predict(l, vy, z) | |
corr(l.map { |x| x[1] }, vy) | |
} | |
return count2(l, a, 'b') | |
end | |
def stats() | |
n = Dir.glob('tmp/*').size | |
f = File.open('outx.txt', 'w') | |
f2 = File.open('outy.txt', 'w') | |
f3 = File.open('outz.txt', 'w') | |
n.times \ | |
{ | |
|i| | |
a = Kernel.eval(File.open("tmp/out#{i}.txt").readlines[0]) | |
if (i % 10 == 0) then | |
l2 = a['lb'].map { |x| x.size } | |
l2.each_with_index { |x, j| f.puts([i / 10, j, x].join("\t")) } | |
f.puts | |
end | |
a['l'].each \ | |
{ | |
|x| | |
f2.puts([i, x[1]['wr_e'], x[0]['d']].join("\t")) | |
} | |
f3.puts([a['j'], a['l'][a['j']][0]['d'], a['x1'][1]['wr_e'], a['l'][a['j']][1]['wr_e']].join("\t")) | |
} | |
f.close | |
f2.close | |
f3.close | |
exit | |
end | |
stats() if (File.exists?(fn = 'out1.txt')) | |
srand(3) | |
File.delete(*Dir.glob('tmp/*')) | |
m = [ARGV[0], 50].compact.first.to_i | |
a = count(m) | |
File.open(fn, 'w').close | |
i = 0 | |
z = false | |
while (!z) | |
x = opt(m, a) | |
j = (0...a['l'].size).max_by { |x| a['l'][x][1]['wr_e'] } | |
a['x1'] = a['l'][j] | |
a['j'] = j | |
a['l'][j] = pair2(x['ns'].to_i(2), m) | |
a = model(a) | |
if (i % 10 == 0) then | |
x = stat1(a['l'].map { |x| x[1]['wr_e'] }).merge(count2(a['l'], a, 'a')).merge(test(m, a)) | |
out(fn, x.select { |k, v| !['la', 'lb'].member?(k) }) | |
z = (x['tb'] == 0) | |
a.merge!(x.select { |k, v| ['la', 'lb'].member?(k) }) | |
end | |
f = File.open("tmp/out#{i}.txt", 'w') | |
f.puts(a.inspect) | |
f.close | |
i += 1 | |
end | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment