Author: Chris Warburton <chriswarbo@gmail.com>
Date: Sat Mar 19 05:08:22 PM UTC 2016
Parent: 9385c9a8faf0999c9b5ba587ecff25eb62d35edf
Log message:
Merge branch 'master' of /home/chris/Programming/repos/search-optimisation-streams
1: diff --git a/README b/README 2: old mode 100644 3: new mode 100755 4: diff --git a/biginteger.js b/biginteger.js 5: old mode 100644 6: new mode 100755 7: diff --git a/curry_speed.csv b/curry_speed.csv 8: new file mode 100755 9: index 0000000..e2c0271 10: --- /dev/null 11: +++ b/curry_speed.csv 12: @@ -0,0 +1,29 @@ 13: +runs, newtime, oldtime 14: +1, 0.9, 15: +2, 0.9, 16: +4, 1, 17: +8, 0.9, 18: +16, 1.1, 19: +32, 0.9, 20: +64, 1, 21: +128, 1, 22: +256, 0.9, 23: +512, 0.9, 24: +1024, 0.9, 25: +2048, 0.9, 26: +4096, 1.1, 27: +8192, 1.1, 28: +16384, 1.1, 29: +32768, 1.2, 30: +65536, 1.5, 31: +131072, 1.6, 32: +262144, 1.9, 33: +524288, 2.7, 34: +1048576, 4.1, 35: +2097152, 7.3, 36: +4194304, 13, 37: +8388608, 26, 38: +16777216, 51, 39: +33554432, 100, 40: +67108864, 200, 41: +134217728, 400, 42: \ No newline at end of file 43: diff --git a/fast_stats.csv b/fast_stats.csv 44: new file mode 100755 45: index 0000000..82255ad 46: --- /dev/null 47: +++ b/fast_stats.csv 48: @@ -0,0 +1,26 @@ 49: +Test number, time 50: +1, 1.1 51: +2, 1.3 52: +4, 1.8 53: +8, 1.5 54: +16, 1.5 55: +32, 2.4 56: +64, 3 57: +128, 3.6 58: +256, 6.7 59: +512, 12.8 60: +1024, 25.6 61: +2048, 53 62: + 63: +50| ______----- 64: +45| ______----- 65: +40| ______----- 66: +35| ______----- 67: +30| ______----- 68: +25| ______---- 69: +20| ______----- 70: +15| ______----- 71: +10| ______----- 72: + 5|__----- 73: + 0|_---_________________________________________________________________________________________________________ 74: +0 250 500 750 1000 1250 1500 1750 2000 75: diff --git a/run.js b/run.js 76: old mode 100644 77: new mode 100755 78: diff --git a/search.js b/search.js 79: old mode 100644 80: new mode 100755 81: index 8da7646..addcd26 82: --- a/search.js 83: +++ b/search.js 84: @@ -30,7 +30,7 @@ 85: // and state, but they must be curried into the 86: // stream functions. This minimises shared state 87: // and other such nastiness. 88: -// 89: +// 90: // As a consequence of this currying, we generally 91: // don't ending up define streams directly, but 92: // rather curryable functions (combinators, or 93: @@ -57,9 +57,7 @@ var c = curry = function(f) { 94: 95: var apply = function(f, args) { 96: // Returns f(args[0], args[1], ...) 97: - return eval('f('+args.map(function(val, key) { 98: - return 'args['+key+']'; 99: - }).join(', ')+')'); 100: + return f.apply(null, args); 101: }; 102: 103: var plus = c(function(a, b) { 104: @@ -379,6 +377,7 @@ var bbj = c(function(i, o, inc, input, n) { 105: ).quotient( 106: two.pow(pc) 107: ); 108: + 109: // Read the next word 110: var y = mem.remainder( 111: two.pow( 112: @@ -395,6 +394,7 @@ var bbj = c(function(i, o, inc, input, n) { 113: pc.add(w) 114: ) 115: ); 116: + 117: // Split the memory into above and below the bit to set 118: var higher = mem.subtract( 119: mem.remainder( 120: @@ -410,6 +410,7 @@ var bbj = c(function(i, o, inc, input, n) { 121: ) 122: ); 123: else lower = 0; 124: + 125: // Read the bit we're copying 126: var val = mem.remainder( 127: two.pow( 128: @@ -473,6 +474,7 @@ var bbj = c(function(i, o, inc, input, n) { 129: BigInteger(val) 130: ) 131: ).add(lower); 132: + 133: // Read the next word and jump where it says 134: pc = mem.remainder( 135: two.pow( 136: @@ -495,11 +497,111 @@ var bbj = c(function(i, o, inc, input, n) { 137: }; 138: }); 139: 140: -var bbj_pure = bbj([-1, -1], [-1, -1], -1, zeros()); 141: +var bbj_pure = bbj([-1, -1], [-1, -1], -1, function(){}); 142: 143: var bbj_io = bbj([0,1], [2,3], 4); 144: 145: -var bbj_outputter = bbj([-1, -2], [0, 1], 2, zeros()); 146: +var bbj_outputter = bbj([-1, -2], [0, 1], 2, function(){}); 147: + 148: +var bbj_lazy = function(){ }; 149: + 150: +///////////////////////////// 151: +// Streams and combinators // 152: +///////////////////////////// 153: + 154: +var constant = function(val) { 155: + // A constant stream always gives the same 156: + // value. This combinator makes constant 157: + // streams. 158: + return function() { 159: + return val; 160: + }; 161: +}; 162: + 163: +var zeros = function() { 164: + // A stream of 0s 165: + return constant(0); 166: +}; 167: + 168: +var ones = function() { 169: + // A stream of 1s 170: + return constant(1); 171: +}; 172: + 173: +var reduce = c(function(init, f, stream) { 174: + // Reduce combines the results of a 175: + // stream using a reduction function. 176: + // For function f, initial value init 177: + // and stream values a, b, c, ... 178: + // reduce returns: 179: + // f(init, a) 180: + // f(f(init, a), b) 181: + // f(f(f(init, a), b), c) 182: + // ... 183: + var comb = function() { 184: + comb = function() { 185: + init = f(init, stream()); 186: + return init; 187: + }; 188: + return init; 189: + }; 190: + return function() { 191: + return comb(); 192: + }; 193: +}); 194: + 195: +var counter = function() { 196: + // A useful example of a reduction. 197: + // Produces a stream of the Naturals 198: + return reduce(0, plus, ones()); 199: +}; 200: + 201: +var hoard = function(comb) { 202: + // A reducer which appends all results to an 203: + // array 204: + return reduce([], catenate, comb); 205: +}; 206: + 207: +var delayer = c(function(vals, stream) { 208: + // Returns each element of the given 209: + // array, then becomes the given stream 210: + var index = 0; 211: + return function() { 212: + if (index < vals.length) return vals[index++]; 213: + else return stream(); 214: + }; 215: +}); 216: + 217: +var delay = c(function(val, stream) { 218: + // Returns the given value, then becomes 219: + // the given stream 220: + return delayer([val], stream); 221: +}); 222: + 223: +var map = c(function(f, comb) { 224: + // Maps the given function over the given 225: + // stream. 226: + return function() { 227: + return f(comb()); 228: + }; 229: +}); 230: + 231: +var iterate = c(function(f, val) { 232: + // Takes a function f and a value x, returns 233: + // the stream f(x), f(f(x)), f(f(f(x))), ... 234: + var result = val; 235: + return function() { 236: + result = f(result); 237: + return result; 238: + }; 239: +}); 240: + 241: +var simple = function() { 242: + // SIMPLE, as defined by Jurgen Schmidhuber. 243: + // Returns every binary sequence in ascending 244: + // order. 245: + return carrying_counter(2); 246: +}; 247: 248: var fast = c(function(symbols, run) { 249: // FAST, as defined by Jurgen Schmidhuber. 250: @@ -511,7 +613,8 @@ var fast = c(function(symbols, run) { 251: // [p, output] where p can be anything, as 252: // long as it can be passed as step's 253: // input. step should also accept an array 254: - // of symbols. If no output is generated 255: + // of symbols instead, as this is how it's 256: + // initialised. If no output is generated 257: // in a step, then make the output [] 258: var phase = 1; 259: return map ( 260: @@ -626,6 +729,22 @@ var levy_flight = function() { 261: return random_walker(pareto()); 262: }; 263: 264: +var make_exponential = function(base) { 265: + // Gives random (natural) numbers from an 266: + // exponentially decaying probability distribution. 267: + return function() { 268: + var sample = 1 - Math.random(); 269: + var result = 0; 270: + while (1.0 / Math.pow(base, result+1) < sample) { 271: + sample -= 1.0 / Math.pow(base, result+1); 272: + result++; 273: + } 274: + return result; 275: + }; 276: +}; 277: + 278: +var binary_exponential = function() { return make_exponential(2); }; 279: + 280: var zip_with = c(function(f, comb1, comb2) { 281: // Combines two streams using the given function 282: return function() { 283: @@ -633,49 +752,53 @@ var zip_with = c(function(f, comb1, comb2) { 284: }; 285: }); 286: 287: -var guess = c(function(symbols, step) { 288: +var guess = c(function(step, symbols, symbol_choice, phase_choice) { 289: // GUESS, as defined by Jurgen Schmidhuber. 290: - // Creates random programs from the given 291: - // symbols and runs them for a random 292: - // number of steps. Returns the output 293: - // generated by the program. 294: - // The step function should curry its 295: - // program, which is a stream of symbols, 296: - // to give a stream of output ([] meaning 297: - // no output at this step). 298: + // Creates random programs and runs them 299: + // for a random number of steps. Returns 300: + // the output generated by the program. 301: + // [] means no output for a given step. 302: 303: // t controls each run to force halting 304: var t; 305: - // A random stream of input symbols. 306: + // A stream of input symbols. 307: // We decrease t as input is read, so 308: // that longer programs are given less 309: - // time 310: - var input = map( 311: - function(x) { 312: - t /= symbols.length; 313: - return symbols[x]; 314: - }, 315: - random_ints(symbols.length) 316: - ); 317: - var steps = filter( 318: - function(n) { 319: - if (n) return true; 320: - t *= symbols.length; 321: - return false; 322: - }, 323: - random_ints(symbols.length) 324: + // time. 325: + var input = finite_chooser( 326: + symbols, 327: + filter( 328: + function(x) { 329: + t /= symbols.length; 330: + return true; 331: + }, 332: + symbol_choice 333: + ) 334: ); 335: return function() { 336: - t = 1; 337: - steps(); 338: - return reduce( 339: - [], 340: - concat, 341: - step(input) 342: - ); 343: + t = phase_choice(); 344: + var steps_taken = 0; 345: + var max_cell = 0; 346: + var mem = function(index) { 347: + while (index > max_cell) { 348: + mem[max_cell++] = input(); 349: + } 350: + return mem[index]; 351: + }; 352: + 353: + var output = []; 354: + var instance = step(mem); 355: + var result; 356: + while (steps_taken <= t) { 357: + result = instance(); 358: + if (result !== []) output.push(result); 359: + }; 360: + return output; 361: }; 362: }); 363: 364: +var guess_bbj_out = function() { return guess(bbj_lazy, [0, 1], random_bits(), binary_exponential()); }; 365: + 366: var make_scattered = c(function(ns, nil, comb, choice) { 367: // Creates arrays a with lengths taken from ns. 368: // Element a[choice()] = comb(), everything else 369: @@ -705,6 +828,14 @@ var make_manhattan_steps = c(function(n, directions, steps) { 370: ); 371: }); 372: 373: +var finite_chooser = c(function(array, choices) { 374: + // Chooses values from the given array, according 375: + // to the indices given by choices 376: + return function() { 377: + return array[choices()]; 378: + }; 379: +}); 380: + 381: var chooser = c(function(streams, choices) { 382: // Interleaves N streams according to a stream of 383: // integer choices from 0 to N-1 384: @@ -1078,7 +1209,7 @@ var exhaustive = c(function(stream, symbols) { 385: return interleave([stream, enumerate(symbols)]); 386: }); 387: 388: -var tabu = function(ns, stream) { 389: +var tabu = c(function(ns, stream) { 390: // Remembers up to n previous results, 391: // and only gives out a value if it's 392: // not in it's remembered list. n is 393: @@ -1095,7 +1226,7 @@ var tabu = function(ns, stream) { 394: if (mem.length > n) mem.shift(); 395: return val; 396: }; 397: -}; 398: +}); 399: 400: var innovator = function(stream) { 401: // Remembers all previous values, 402: @@ -1106,4 +1237,17 @@ var innovator = function(stream) { 403: // For example, asking for 3 bits 404: // will hang! 405: return tabu(map(plus(1), counter()), stream); 406: -}; 407: \ No newline at end of file 408: +}; 409: + 410: +var aixi = function(predictor, experimentor, inputs, rewards) { 411: + // AIXI, as defined by Marcus Hutter. 412: + // AIXI tries to give output which 413: + // maximises the rewards, using 414: + // information from the input stream. 415: + // First we try to build a model of 416: + // the input an reward streams, which 417: + // predictor is used for. 418: + // Once we have a good model, we find 419: + // a good output for the model using 420: + // experimentor. 421: +} 422: diff --git a/tests.js b/tests.js 423: old mode 100644 424: new mode 100755 425: index f873b71..345c098 426: --- a/tests.js 427: +++ b/tests.js 428: @@ -1,7 +1,8 @@ 429: +var curry_test; 430: var tests = function(num) { 431: if (typeof num === typeof undefined) num = +Infinity; 432: var ts = [ 433: - function() { 434: + curry_test = function() { 435: // Use uncurried take and map, since we're testing curry! 436: var take = function(n, stream) { 437: var result = []; 438: @@ -490,7 +491,7 @@ var tests = function(num) { 439: stream = innovator(stream); 440: return function() { 441: var val = stream(); 442: - if (known.indexOf(val) !== -1){p(known);p(val); return 'innovator';} 443: + if (known.indexOf(val) !== -1) return 'innovator'; 444: known.push(val); 445: }; 446: }, // innovator 447: @@ -517,3 +518,35 @@ var tests = function(num) { 448: if (failed.length) return failed; 449: return true; 450: }; 451: + 452: +var countdown = function(n, s) { 453: + while (n-- > 0) s(); 454: +}; 455: + 456: +var p2 = function(a) { 457: + p(a); 458: + return a; 459: +} 460: + 461: +var d; 462: +var b = function(n) {countdown(n, filter( 463: + function(a) 464: + { 465: + p(a); 466: + return true; 467: + },innovator( 468: + //ratchet( 469: + // tag( 470: + // function(a) 471: + // { 472: + // return Math.sin( 473: + // parseInt( 474: + // a.join(''), 475: + // 2 476: + // ) 477: + // ); 478: + // }, 479: + fast_bbj_out() 480: + // ) 481: + //) 482: +)))}; 483: \ No newline at end of file