2b:null 2c:["$","title",null,{"children":"Set alignment | dleeftink | Observable"}] 31:T4a7,plot = { let cols = new Map([...new Set([...init,...exit])].sort().map((d,i)=>[d,i+Math.random()])) let plot = Plot.plot({ inset:16, margin:8, y: {domain: [0,1],axis:null}, x: {axis:null}, height:124, width:Math.min(width,520), color: { scheme: "Cubehelix", type: "linear", reverse:true, domain:[-2,7] }, marks: [ Plot.text(reverse.length? exit : init,{ y:1,x:(d,i)=>i,text:d=>d,dy:-10,fontWeight:'600'}), Plot.text(reverse.length? init : exit,{ y:0,x:(d,i)=>i,text:d=>d,dy:10,fontWeight:'600'}), Plot.arrow([...moves.both.entries()].map((entry,i)=> Object.fromEntries( entry.flatMap((d,j)=>[[`loc${1+j}`,1-j],[`pos${1+j}`,d.item],['cell',cols.get(d.cell)]]))), { y1:'loc1',y2:'loc2',x1:'pos1',x2:'pos2', headLength: 16,inset:3,strokeOpacity:1, strokeWidth: (d) => Math.log(3/(Math.abs((d.pos1-d.pos2))+1)*10), stroke:(d,i) => Math.log(2/(Math.abs((d.pos1-d.pos2))+0.5)*5) }) // [...result.vals.entries()].map(entry=> // Plot.line(entry.map((d,i)=>[1-i,d.item].reverse()))), ] }) return plot }32:T7d4,// cleanup @ v2456 // pinned @ v2870 function setMap (init,exit) { let A = init, B = exit, C = A.slice(0), D = B.slice(0); let t1 = performance.now(); let span = Math.max(A.length,B.length) let getA = {}, getB = {};// binA = new Set, binB = new Set; let link = []; for (var i = 0;i < span ;++i) { let a = A[i], b = B[i]; getA[a] ? getA[a].push(i) : getA[a] = [i] getB[b] ? getB[b].push(i) : getB[b] = [i] } let both = Array.from(new Set(B.filter(b=>getA[b])).keys()) //Array.from(new Set(A.concat(B).filter( //ab => getA[ab] && getB[ab] ? true : ( getA[ab] ? binA.add(ab) : binB.add(ab), false ))).keys()); // Object.keys(getA); let size = both.length; for (var N = 0; N < size; ++N) { let cell = both[N]; let locs = [A,B] = [getA[cell], getB[cell]] let ties; if(A.length == B.length) { ties = Array.from(Array(A.length).keys()).map(n=>[A[n],B[n]]) } else { ties = A.length > B.length ? A.map(a=> B.map(b=> [a,b])) : B.map(b=> A.map(a=> [a,b])) ties = ties .map((zig,i,f) => Array.from(Array(zig.length).keys()) .map((j) => f[(i + j) % f.length][j])) // optionally sort here (e.g. by distance metric) to 'tidy' matrix .map((zag) => [zag.reduce((cost, [a,b]) => cost + Math.abs(a-b), 0), zag]) .sort((a,b) => a[0] - b[0])[0][1] } link.push(...ties.map(([a,b])=>[{item:(delete C[a],a),cell},{item:(delete D[b],b),cell}])) }; C = C.map((c,i)=> [{item:i,cell:c},{item:i,cell:undefined}]).filter(Boolean); D = D.map((d,i)=> [{item:i,cell:undefined},{item:i,cell:d}]).filter(Boolean); let diff = new Map(C.concat(D).sort((a,b)=>a[0].item-b[0].item || a[1].item-b[1].item)); link = new Map(link)//.sort((a,b)=>a[0].item-b[0].item || a[1].item-b[1].item)) let t2 = performance.now()-t1; return { both:link, diff, time:t2 } }33:T671,function setAlign(init,exit) { /* align common items with lowest movers costs todo : empty values todo : same scores todo : n > 2 */ let setA = init, setB = exit, A,B; let pack = new Set([...setA,...setB].filter(AB=> setA.includes(AB) && setB.includes(AB) && typeof AB)) let move = new Map([...pack].sort().flatMap((a,i,f)=> /* Destructure set indices in one go notice: ([A,B] = ... , ... ) parens shorthand */ ([ A,B ] = [setA, setB].map(set => set.reduce((s, b, i) => (a == b ? s.concat(i) : s), [])), /* 1. Calculate pairwise move costs 2. Transpose items when width > height 3. Get move costs on the diagonal ('zig') 4. Sort diagonals by total move cost ('zag') 5. Split pairs into unique objects for hash map 1 */ A.map((a,i) => B.map((b) => ({from:a,onto:b,cost:Math.abs(a-b)})))/* 2 */ .reduce((set, a, i, b) => a.length > b.length ? a .map((_,j) => [...(set[j] || []), a[j]]) : set.concat([a]),[])/* 3 */ .map((zig, i, f) => Array.from(Array(zig.length).keys()) .map((j) => f[(i + j) % f.length][j]) .sort((a, b) => a.cost - b.cost))/* 4 */ .map((zag) => [zag.reduce((pool, item) => pool + item.cost, 0), zag]) .sort((a, b) => a[0] - b[0]).at(0)?.at(1)/* 5 */ .map(({from,onto})=>[{item:from,cell:a},{item:onto,cell:a}]))) .sort((a,b)=>a[0].item-b[0].item) .filter(Boolean)); return move }34:T7f0,function alignLines(init,exit) { // determine longest sequence let affine = init.length == exit.length; let shrink = init.length >= exit.length, source = shrink ? init : exit; let expand = init.length < exit.length, target = expand ? init : exit; // read nested or plain text source = source.map(d=>d?.text ?? d) target = target.map(d=>d?.text ?? d) // prepare counts and hashmaps let slot = new Set(); let dict = new Map(); let enter = 0, leave = 0; let total = source.length + target.length; // match source to target // use previous j as search start // todo: binary search from nearest let setA = source.map((src,i)=> { let prev = (dict.get(src)??-1); let j = target.findIndex((tgt,n)=> n > prev && src==tgt); if( j > prev ) dict.set(src,j); let tgt = j >= 0 ? src: undefined; src = {line:i,text:src}; tgt = {line:j,text:tgt}; if( j < 0 ) { leave++ } else { slot.add(j); target[j] = tgt; // mutate item with reference; } let row = [src,tgt] return row }) // determine remaining lines // add linked reference to above object for consecutive strings let prev = {}; let rest = Array.from(Array(target.length).keys()).filter(i=>!slot.has(i)) let setB = target.map((tgt,i,f)=>{ if(rest.includes(i)) { enter++ let link = typeof f[i-1] == 'object' ? f[i-1] : prev; prev = tgt = {line:i,text:tgt}; return [link,[{line:-1,text:undefined},tgt]] } else { return undefined } }).filter(Boolean) // insert based on matched element above remaining // finds above element BY REFERENCE. for (let [above,entry] of setB) { let insert = setA.findIndex(([src,tgt],n)=> tgt == above) + 1; let offset = setA[insert]?.[1].text ? 0 : 1; setA.splice(insert+offset,0,entry); } return new Map(setA.map(d=> expand? d.reverse() : d)) // reverse direction when exit > init }35:T86c,v4_cross = { let A = //[...moves.diff.keys()].filter(d=>d.cell).map(d=>d.cell) corpus[0]//.slice(0,v4_firstN) let B = //diffed corpus[1]//.slice(0,v4_firstN) let t1 = performance.now() let stat = []; for (const list of [A,B]) { //let C = //A.concat(B) let span = list.length; let size = 3, dict = {}, heap = []; //C = C.map((str,i)=>{ for (let i = 0; i < span; ++i) { let str = process(list[i]) heap[i] = new Set(); for (let win = 2; win< size; ++win){ for (let j = 0; j < str.length-win; j++) { const hash = str.substring(j,(j+1)+win); ( dict[hash] ) ? ( dict[hash][i] ? ++dict[hash][i] : dict[hash][i] = 1 ) : ( dict[hash] = {}, dict[hash][i] = 1 ) heap[i].add(hash) } } } let keys = Object.keys(dict) for (let i = 0; i < keys.length; ++i) { // if sort, the samples are 'constrained' > tighter clustering ? dict[keys[i]] = Object.entries(dict[keys[i]])/*.sort((a,b)=>b[1]-a[1])*/.slice(0,32) } stat.push({dict,heap}) } for (let iter = 0; iter < 2; ++iter) { // swap dictionaries let heap = (iter ? stat[1] : stat[0]).heap; let dict = (iter ? stat[0] : stat[1]).dict; let span = heap.length for (let i = 0; i < span; ++i) { let hash = Array.from(heap[i]??[]); let freq = Array(span); for (let j = 0; j < hash.length; ++j) { let locs = dict[hash[j]] ?? [] for (let n = 0; n < locs.length; ++n) { freq[locs[n][0]] ? ++freq[locs[n][0]] /*+= locs[n][1]*/ : freq[locs[n][0]] = 1/*locs[n][1]*/; } } heap[i] = [iter == 0 ? A[i] : B[i]].concat( freq.map((d,i)=>[i,d]) .filter(d=>d[1]>2) .sort((a,b)=>b[1]-a[1]) .map(d => iter == 0 ? B[d[0]] : A[d[0]]) ) } iter == 0 ? A = heap : B = heap } // let rank = Object.entries(seen).sort((a,b)=>b[1]-a[1]).slice(32).map((d,i)=>[d,i]); // seqs = Object.entries(seqs).sort((a,b)=>b[1]-a[1]).map(d=>d[0].split('_').concat(d[1])) return { A,B,//dict,heap, time: performance.now()-t1 } }36:T902,v4_union = { let A = corpus[0] let B = corpus[1] let t1 = performance.now() let C = A.concat(B) let span = C.length; let size = 3, dict = {}, heap = [], link = {}; //C = C.map((str,i)=>{ for (let i = 0; i < span; ++i) { let str = process(C[i],{level:1}) heap[i] = []//new Set(); for (var win = 2; win< size; ++win){ let prev; for (var j = 0; j < str.length-win; j++) { const hash = str.substring(j,(j+1)+win); //( dict[hash] ) ? ( dict[hash][i] ? ++dict[hash][i] : dict[hash][i] = 1 ) : //( dict[hash] = {}, dict[hash][i] = 1 ) ( dict[hash] ) ? dict[hash].add(i) : ( dict[hash] = new Set(), dict[hash].add(i) ) if(prev) { let tie = prev+'|'+hash; link[tie]? ++link[tie]: link[tie] = 1 } heap[i].push(hash); prev = hash; } } } link = Object.entries(link) link = link.sort((a,b)=>b[1]-a[1]).slice(0,parseInt(link.length * 0.025)).map(d=>d[0].split('|')[1]) let skip = new Set(link) let keys = Object.keys(dict) for (var i = 0; i < keys.length; ++i) { //dict[keys[i]] = Object.keys(dict[keys[i]])//.sort((a,b)=>.025- Math.random()).slice(0,60) dict[keys[i]] = Array.from(dict[keys[i]]) } // TODO: iterate on max length, swap when init < exit // TODO: how to best splice arrays for (var i = 0; i < A.length; ++i) { let hash = heap[i] //Array.from(heap[i]??[]); let freq = Array(span); for (var j = 0; j < hash.length; ++j) { // filters A from B, B from A let entry = hash[j] if(skip.has(entry)) { continue } let locs = dict[entry].filter((ref,j)=> i < A.length ? ref >= A.length : ref < A.length ) // implicit casting for (var n = 0; n < locs.length; ++n) { let idx = locs[n]; freq[idx] ? ++freq[idx] : freq[idx] = 1; } } heap[i] = //[C[i]].concat( freq.map((d,i)=>[i,d]) .filter(d=>d[1]>1 /*&& (i < A.length ? d[0] > span*0.5 : d[0] <= span*0.5)*/) .sort((a,b)=>b[1]-a[1]).slice(0,16) // .map((d)=>'['+d[0]+']'+[C[d[0]],d[1]][0]) .map((d)=>parseInt(C[d[0]].split(/[\[\]]/)[1])).includes(i) //) } return { dict,heap,link,skip, time: performance.now()-t1 } }37:T700,// keep list of ngrams appearing in multiple strings v3 = { let input = [...corpus[0].slice(0,1000),...corpus[1].slice(0,1000)]; //zipf.slice(0,1000) let t1 = performance.now() let span = input.length; let max = 4; let dict = {}, heap = [], temp = new dw.Cache(512); // let win = 0; // console.clear() let nest = input.map((str,i)=>{ str = str.replace(/[aeoiu]/g,'') let key = i heap[key] = new dw.Cache(5); //let arr = [] for (var win = 3; win< max; ++win){ let sub = new Set(); for (var j = 0; j < str.length-win; ++j) { var hash = str.substring(j,(j+1)+win); let freq = dict[hash]; freq ? freq[key] ? ++freq[key] : freq[key] = 1 : (freq = dict[hash] = {}, freq[key] = 1) /* let loc = temp.get(hash); loc ? loc[key] ? (++loc[key]) : (loc[key] = 1) : (loc = {[key]:1}, temp.set(hash,loc))*/ sub.add(dict[hash]) //sub.add(loc) } for (var hash of sub) { let loc = Object.keys(hash); for (var n = 0; n< loc.length; ++n) { let idx = parseInt(loc[n]) let val = heap[idx].get(key) val ? heap[idx].set(key, ++val) : heap[idx].set(key, 1); // inverted key <--> idx improves results? val = heap[key].get(idx) val ? ++val : heap[key].set(key, 1) } } } return str }) return { dict,heap,temp, time: performance.now()-t1 } }38:T95c,v2 = { let input = [...corpus[0].slice(0,v2_firstN),...corpus[1].slice(0,v2_firstN)]; //input.sort(); let t1 = performance.now() let span = input.length; let max = 3; let dict = {}, heap = [], meta = {}; // let win = 0; // console.clear() let nest = input.map((str,i)=>{ let key = i // str = str.replace(/[aeoiu]/g,'') //str = ' ' + str + ' ' heap[key] = new Set(); for (var win = 2; win< max; ++win){ //let sub = new Set(); for (var j = 0; j < str.length-win; ++j) { var hash = str.substring(j,(j+1)+win); //dict[hash] ? dict[hash].push(i) : dict[hash] = [i]; let loc = dict[hash]; loc ? loc[key] ? loc[key] = [i,++loc[key][1]] : loc[key] = [i,1] : (loc = dict[hash] = [], loc[key] = [i,1]) //sub.add(dict[hash]) heap[key].add(hash) meta[hash] = dict[hash]; } } }) // sorting ngram arrays // per str, unify top-n ngram arrays // count and sort by ngram matches // each string now has a ranking of potential str matches // -> idea: build ranked ngram array from the get go to avoid large sorting operations let keys = Object.keys(meta) for (var i = 0; i < keys.length; ++i) { // d3.quickselect(dict[keys[i]],16,0,dict[keys[i]].length,(a,b)=>b?.[1]-a?.[1]) //dict[keys[i]].sort((a,b)=>b[1]-a[1]) //fst.inPlaceSort(dict[keys[i]]).desc([k=>k[1]]).slice(0,16) meta[keys[i]] = fst.inPlaceSort(meta[keys[i]]).desc([k=>k[1]]).slice(0,64) } /*heap = heap.map((h,i)=> fst.inPlaceSort( Object.entries( Array.from(h).flatMap(a=> a.slice(0,128)).map(d=>d[0]).reduce((pool,item)=> (pool[item]? ++pool[item] : pool[item]=1,pool),{}) ).filter(d=>d[0] >= 100 && d[1]>1) ).desc([e=>e[1]]) )*/ heap = heap.map((h,i)=> fst.inPlaceSort( Object.entries( Array.from(h).flatMap(hash=>meta[hash]).reduce((pool,[key,val])=> (pool[key]? ++pool[key] : pool[key]=1,pool),{}) ).filter(d=>d[0] >= span*0.5 && d[1]>2) ).desc([e=>e[1]]) ) return { dict,heap,meta, time: performance.now()-t1 } }39:Tb34,v1 = { let input = zipf.slice(0,1000) let t1 = performance.now() let span = input.length; let max = 3; let dict = {}, heap = []; // let win = 0; console.clear() let nest = input.map((str,i)=>{ //str = ' ' + str + ' ' heap[i] = [] //Array(span) //new Set(); for (var win = 1; win< max; ++win){ let sub = new Set(); for (var j = 0; j < str.length-win; ++j) { var hash = str.substring(j,(j+1)+win); //dict[hash] ? dict[hash].push(i) : dict[hash] = [i]; let loc = dict[hash]; loc ? loc[i] ? loc[i] += 1 //= [i,++loc[i][1]] : loc[i] = 1//[i,1] : (loc = dict[hash] = {}, loc[i] = 1 /*[i,1]*/) sub.add(dict[hash]) // heap[i].push(dict[hash]) // heap[i].push(structuredClone(dict[hash])) } for (var hash of sub) { let loc = Object.keys(hash); for (var n = 0; n< Math.min(loc.length); ++n) { let heapData = heap[i][loc[n]]; heapData ? ++heapData /*+= hash[loc[n]]*/ : heapData = heap[i][loc[n]] = 1 //hash[loc[n]] heap[loc[n]][i] = heapData } } //heap[i] = sub //[...sub].map(hash=> dict[hash].forEach((h,n)=> heap[i][n] ? heap[i][n] += h : heap[i][n]= h)) } return str }) /* let keys = Object.keys(dict) for (var i = 0; i < keys.length; ++i) { dict[keys[i]].sort((a,b)=>a-b) let hash = Object.keys(dict[keys[i]]) for (var j = 0; j < hash.length; ++j) { if(dict[keys[i]][hash[j]] !== dict[keys[i]][parseInt(hash[j])+1] ) { delete dict[keys[i]][hash[j]] } else { continue } } }*/ /*for (var hash in dict) { dict[hash].sort((a,b)=>a-b)//(a,b)=>b[1]-a[1]) for (var idx in dict[hash]) { if(dict[hash][idx] !== dict[hash][parseInt(idx)+1]) { delete dict[hash][idx] } } }*/ /*let keys = Object.keys(dict) for (var i = 0; i < keys.length; ++i) { let hash = Object.keys(dict[keys[i]]) for (var j = 0; j < hash.length; ++j) { if(dict[keys[i]][hash[j]] == 1) { delete dict[keys[i]][hash[j]] } else { continue } } }*/ //heap = heap.map(d=>[...d].map(n=>n[0]).sort((a,b)=>b[1]-a[1]))//n.slice(0,2))) /*for (var hash in dict) { for (var idx in dict[hash]) { if(dict[hash][idx] < 3 ){ delete dict[hash][idx] } else { continue } } }*/ // heap = heap.map(mat=>mat.map(a=>a.filter(x=>x>1))) // heap = heap.map(h=>h.flatMap(n=>Object.keys(n)).sort()) // heap = heap.map(h=>h.sort((a,b)=>b-a)) return { dict,heap, time: performance.now()-t1 } }3a:Tdb0,// from https://gist.github.com/matsadler/6087275 kdnear = { // returns the k nearest points to target as an array // k should be the number of points to return // kdtree should be a kdtree // target should be an array of points // results shouldn't be passes, it's used internally // example: // var closest = nearest(1, tree, [1,1]).first; function nearest(k, kdtree, target, results) { results = results || []; var axis = kdtree.axis, value = kdtree.value, result = { value: value, distance: distanceSquare(target, value), }, comparison, unsearched, axisDistance, maxDistance; if (!kdtree.left && !kdtree.right) { return priorityQueueAdd(distanceCompare, k, results, result); } comparison = target[axis] - value[axis]; if (comparison < 0) { unsearched = kdtree.right; if (kdtree.left) { nearest(k, kdtree.left, target, results); } } else if (comparison > 0) { unsearched = kdtree.left; if (kdtree.right) { nearest(k, kdtree.right, target, results); } } else { if (kdtree.left) { nearest(k, kdtree.left, target, results); } if (kdtree.right) { nearest(k, kdtree.right, target, results); } } axisDistance = axisDistanceSquare(axis, value, target); if (results.length) { maxDistance = results[results.length - 1].distance; } if (unsearched && (!maxDistance || axisDistance < maxDistance)) { nearest(k, unsearched, target, results); } return priorityQueueAdd(distanceCompare, k, results, result); } // helper functions function distanceCompare(a, b) { return a.distance - b.distance; } function distanceSquare(a, b) { var sum = 0, i; for (i = 0; i < a.length; i += 1) { sum += axisDistanceSquare(i, a, b); } return sum; } function axisDistanceSquare(axis, a, b) { return Math.pow(a[axis] - b[axis], 2); } // the following helper functions are pretty generic and could be extracted to // their own module // modifies queue function priorityQueueAdd(cmpFunc, max, queue, value) { queue = insertSorted(cmpFunc, queue, value); if (queue.length > max) { queue.pop(); } return queue; } // modifies array function insertSorted(cmpFunc, array, value) { if (!array.length) { return array.push(value); } var pivotComparison = index(cmpFunc, array, value), pivot = pivotComparison[0], comparison = pivotComparison[1]; if (0 < comparison) { array.splice(pivot, 0, value); } else { array.splice(pivot + 1, 0, value); } return array; } // returns an index and a signal value as an array, eg [index, signal] // if the signal is 0 then value === array[index], if signal is < 0 then // value < array[index] && value > array[index - 1], if signal is > 0 then // value > array[index] && value < array[index + 1] function index(cmpFunc, array, value) { var start = 0, length = array.length, finish = length, pivot, comparison; while ((length = finish - start) > 0) { pivot = start + Math.floor(length / 2); comparison = cmpFunc(array[pivot], value); if (0 > comparison) { start = pivot + 1; } else if (0 === comparison) { break; } else { finish = pivot; } } return [pivot, comparison]; } return nearest }3b:T45c,// https://github.com/mikolalysenko/union-find UnionFind = (function() { "use strict"; "use restrict"; function UnionFind(count) { this.roots = new Array(count); this.ranks = new Array(count); for(var i=0; i= 1 && hasProperty) { self.count--; //updating the value counter and reducing by one. if (self.store[maxKey].length > 1) { popped = self.store[maxKey].shift(); return popped.toString(); } else if (this.store[maxKey].length == 1) { //remove the key along with value popped = this.store[maxKey]; self.store = Object.keys(self.store).reduce(function (obj, key) { if (key != maxKey) { //key you want to remove obj[key] = self.store[key]; } return obj; }, {}); return popped.toString(); } } return null; // if queue is empty return null as nothing is removed }; /** * Get all priorities */ PriorityQueue.prototype.getAllPriorities = function () { //renamed the function to camel case so that its consistent with others return Object.keys(this.store); }; /** * Iterates through all the queue elements in priority-then-FIFO order */ PriorityQueue.prototype.forEach = function (callback) { let keys = Object.keys(this.store).sort((a, b) => b - a); // get keys(priorites) array in sorted order from highest to lowest if (callback && typeof callback === "function") { for (let i = 0; i < keys.length; i++) { callback(keys[i], i, this); } } }; /** * Update the priority of a value if exists and return true else return false */ PriorityQueue.prototype.changePriority = function (value, newPriority) { let foundItem = false; let self = this; //using only one for..in.. loop which is better for performance as compared to foreach..no need to have 2 foreach for (let priority in self.store) { let index = self.store[priority].indexOf(value); // Get the index of value from inside the array inside the priority if (index >= 0) { // if value exists if (self.store[priority].length > 1) { self.store[priority].splice(index, 1); // remove the item // this.count--; } else if (self.store[priority].length == 1) { self.pop(priority); // we also remove the priority from hash if it onlly had 1 value left to avoid empty priorities } self.add(value, newPriority); return !foundItem; //return true and exit the loop } } return foundItem; }; return PriorityQueue }3d:T549,// https://gist.github.com/duhaime/097f0a33ef57a100a1450a2ed5278dab LshIndex = function(args) { var args = args || {}; this.bandSize = args.bandSize || 4; this.index = {}; this.insert = function(key, minhash) { var hashbands = this.getHashbands(minhash); for (var i=0; i= 0 and <= maxHash this.randInt = function() { var x = Math.sin(this.seed++) * this.maxHash; return Math.floor((x - Math.floor(x)) * this.maxHash); } // initialize the minhash var config = config || {}; this.numPerm = config.numPerm || 128; this.seed = config.seed || 1; this.hashFunctions = []; this.hashvalues = []; this.permA = []; this.permB = []; // share permutation functions across all minhashes this.inithashvalues(); this.initPermutations(); };3f:[] 2f:{"id":"6c617058d2465e16","slug":"set-alignment","title":"Set alignment","thumbnail":"80a85213a946de52d9c38f2cb888b38bb4339a339f57fff630642ab874a70d8c","access_level":"public","create_time":"$D2023-05-22T09:59:23.528Z","update_time":"$D2025-02-12T06:52:09.285Z","view_time":null,"first_public_time":"$D2023-05-22T09:59:23.528Z","fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"10e70264ea4e147e","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":"starter_2024"},"version":10509,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"6cdb6324966da5d4","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":null}],"members":[{"type":"individual","id":"6cdb6324966da5d4","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Set alignment","cells":[{"id":0,"value":"# Set alignment\n## max items first in–least move\n\n___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":128,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":534,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1311,"value":"viewof reverse = Inputs.checkbox(['invert'],{label:html`Testing :`})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"init = ['d','a','-','e','a',,'x','x','-','a','d',,,'b','a','f','',,,,'hello',,,,'a','b','z','-','l']","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"exit = ['a','e','f','b','d','a','b','f','h',,,,'d','a','-','h','a','x','f','f','f','z','b','-','-']","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":24,"value":"moves = (reverse.length ? setMap(exit,init) : setMap(init,exit))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":290,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":98,"value":"a = Array.from({length:2**14},()=>(Math.random()*1000).toFixed(1))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":100,"value":"b = Array.from({length:2**14},()=>(Math.random()*100).toFixed(1))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":46,"value":"result = { \n\n let t1 = performance.now();\n let it = {} //setMap(a,b);\n\n return {vals:it,time:Math.round(performance.now()-t1)}\n\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":20,"value":"___\n\n### Static","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1409,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3166,"value":"___\n\n### Playground","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3171,"value":"string = 'abcdef'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3561,"value":"(' '+string+' ').split(new RegExp(`(?=(.{2}))`))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3527,"value":"{\n let size = 4;\n let pats = Array.from({length:size},(_,i)=> new RegExp(`(${Array(i+2).join('.')})`))\n let arr = [];\n \n for (let win = 1; win < size; ++win) {\n arr.push(string.split(pats[win]).concat(string.slice(1).split(pats[win])).filter(s=>s.length == win+1))\n }\n \n return arr\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7004,"value":"___\n\n### Data","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3978,"value":"diffed = [...[...moves.diff.entries()].map(e=>e.map(d=>d.cell)).map(([a,b])=>a).filter(Boolean),'elel','a','l']","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4707,"value":"random = a.slice(0,2**10).map(d=>(crypto.randomUUID()+crypto.randomUUID()).replace(/[\\d\\-]/g,' ').replace(/\\s+/g,'').replace(/ (.) /g,'$1').slice(0,8))//Math.random()*32))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5232,"value":"zipf = fetch('https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt').then(d=>d.text())\n.then(d=>d.split(/(\\w+\\n\\w+)\\n/g)\n//.then(d=>d.split(/\\n/g)\n //.sort().join('\\n').split(/(\\w+\\n\\w+\\n\\w+)\\n/g)\n.filter(Boolean).map(s=>s.replace(/\\n/g,' '))\n.sort(() => .5 - Math.random() )\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6941,"value":"corpus = {\n let corpus = (await fetch('https://raw.githubusercontent.com/gabrielStanovsky/template-oie/master/examples/sentences.txt')).text()\n corpus = (await corpus).replace(/[^\\w\\s]+|\\d+/g,'').split('\\n')\n .map(str =>[...Array(2).keys()].map(i=>str.trim().toLowerCase()/*.split(' ')\n .slice(parseInt(Math.random()*2),4+parseInt(Math.random()*7))\n .sort(() => .5 - Math.random() ).join(' ')*/.replace(/\\s+/g,' ').trim()))//.filter(d=>d[0]!==d[1])\n\n .slice(0,v4_firstN)\n \n return [corpus.map(d=>d[0].split(' ').slice(2,6).join(' ')),corpus.map((d,i)=>'['+i+']'+d[1].split(' ').slice(0,9).join(' ')).sort(() => .5 - Math.random() )]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7008,"value":"___\n\n### Imports","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6103,"value":"dw = (await import(\"https://esm.sh/dw-cache@0.0.105\")).default","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6623,"value":"lf = (await import(\"https://esm.sh/lfu-cache@0.1.0\")).default","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7051,"value":"fst = (await import('https://cdn.skypack.dev/fast-sort@3.4.0?min'))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7492,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":7537,"value":"corpus[0][0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7675,"value":"{ \n\n let t1 = performance.now()\n let keys = Object.keys(v4.dict);\n let freq = Object.values(v4.dict);\n let sums = freq.map((f,i)=>[keys[i],f,f.reduce((a,b)=>a+(b>0),0)]).sort((a,b)=>b[2]-a[2])//.slice(32)\n\n let span = sums.length\n let size = sums[0][1].length\n let mask = [];\n\n for (let i = 0; i < span; ++i) {\n let prev = sums[i-1]?.[1] ?? new Uint8Array(size).fill(1)\n let vals = sums[i][1];\n mask[i] = new Uint8Array(size)\n \n for (let j = 0; j < size; ++j) {\n mask[i][j] = (!!vals[j] && !!prev[j])\n }\n\n //sums[i][1] = mask[i]\n \n }\n mask = mask.map(m=>m.reduce((a,b)=>a+b,0))//.reduce((a,b)=>a+b,0)//(span*size)\n sums = sums.map((s,i)=>s.concat(mask[i]))\n return {\n mask,sums,span,size,\n time: performance.now()-t1\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7998,"value":"edges = {\n let prev = new Set(), next = new Set(), dag = [];\n \n let edges = v4.seqs\n\n dag.push(['',edges[0][0]])\n next.add(edges[0][0])\n\n for (let i = 0; i < edges.length; ++i) {\n\n let [l,r,n] = edges[i] \n if(next.has(l)) dag.push([l,r])\n \n prev.add(l); next.add(r);\n \n \n }\n\n return dag\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8102,"value":"findKthLargest = function(nums, k) {\n\n function swap(arr, i, j){\n let temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n\n function quickselect(arr, l, h, k){\n if(l == h){\n return arr[k];\n }\n if(l < h){\n let p = partition(arr, l, h);\n if(p === k){\n return arr[k];\n }\n else if(p < k){\n return quickselect(arr, p+1, h, k);\n }\n else {\n return quickselect(arr, l, p-1, k);\n }\n }\n }\n\n function partition(arr, l, h){\n let pivot = arr[h]\n let p = l;\n for(let i = l; i < h; i++){\n if(arr[i] < pivot){\n swap(arr, i, p);\n p++;\n }\n }\n swap(arr, h, p);\n return p;\n }\n \n return quickselect(nums, 0, nums.length - 1, nums.length - k);\n\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8143,"value":"SkipList = (await import('https://esm.sh/finalskiplist@1.0.2')).default","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9061,"value":"v4_idx = 10//5338 - v4_firstN","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9063,"value":"v4_inspect = [corpus[0][0],corpus[1][0]]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8719,"value":"v4_firstN = 1000","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9352,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9578,"value":"function process(string, { level = 0, sort = false} = {}) {\n\n //const pipe = (str,...rules) => rules.reduce((line,pipe,i) => rules[i-1] !== false && \n //typeof pipe === 'function' ? pipe(line) : (pipe => pipe)(line), str) \n\n let dropConsec = str => str.replace(/([^])\\1+/g,'$1')\n //let dropVowels = str => str.replace(/[aeoiu0-9]/g,'')\n //let dropSingle = str => str.replace(/\\b\\S\\b/g,'')\n let padString = str => ' ' + str + ' '\n //let sortChars = str => sort ? [...str].sort().join('') : str\n \n return dropConsec(padString(string)).replace(/[0-9\\[\\]]+/g,'')\n /*pipe(string, padString, \n level > 1 , dropVowels,\n level > 0 , dropConsec,\n level > 2, dropSingle)*/\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9975,"value":"v4_union.heap.slice(0,v4_firstN).reduce((a,b)=>a+!!b,0)/v4_firstN","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7496,"value":"$36","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7488,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":7451,"value":"v3_idx = parseInt(Math.random()*1000)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7453,"value":"[...v3.heap[v3_idx].dict.keys()].map(k=>corpus[0]?.[k]??corpus[1][k])//.sort()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5412,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7410,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6681,"value":"v2_idx = 80//parseInt(Math.random()*1000)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8421,"value":"v2_firstN = 100","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7158,"value":"v2_inspect = [corpus[0][v2_idx],corpus[1][v2_idx]]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7168,"value":"v2_cluster = v2.heap[v2_idx].map(idx=>corpus[1][parseInt(idx)-v2_firstN])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7114,"value":"v2_nomatch = v2.heap.slice(0,v2_firstN).map((d,i)=>[i,d.slice(0,1).map(d=>parseInt(d)-v2_firstN).includes(i)]).filter(d=>!d[1])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4986,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8295,"value":"d3.quickselect([[1,1],,[2,2],[3,1]],2,0,4,(a,b)=>b?.[1]-a?.[1])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3174,"value":"$39","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4661,"value":" \n /*for (let n = 0; n < loc.length; ++n) {\n // heap[i][loc[n]] ? heap[i][loc[n]] += 0 : heap[i][loc[n]] =1\n heap[i]\n ? heap[i][loc[n]]\n ? heap[i][loc[n]] += 1\n : heap[i][loc[n]] = 1\n : heap[i] = [];\n }*/\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5874,"value":"// from https://gist.github.com/matsadler/6087275\n\nkdtree = {\n function kdtree(dimensions, points, depth) {\n depth = depth || 0;\n var axis = depth % dimensions,\n node = { axis: axis };\n\n points.sort(function (a, b) {\n return a[axis] - b[axis];\n });\n var lefts = points.splice(0, Math.floor(points.length / 2));\n\n node.value = points.shift();\n\n depth += 1;\n if (lefts.length) {\n node.left = kdtree(dimensions, lefts, depth);\n }\n if (points.length) {\n node.right = kdtree(dimensions, points, depth);\n }\n\n return node;\n }\n\n return kdtree;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5887,"value":"$3a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5042,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4855,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3076,"value":"$3d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10502,"value":"2**32-1\n//4294967311","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3079,"value":"$3e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3130,"value":"function hashWords(words, hash) {\n for (var i=0; id[1].length>1).map(d=>d[1].join('')).reduce((pool,key)=> (pool[key]?pool[key]++:pool[key]=1,pool),{})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10426,"value":"lsh[0].query(lsh[3])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10500,"value":" new Minhash({numPerm:32});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3082,"value":"lsh = {\n \n var a = ['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for','estimating', 'the', 'similarity', 'between', 'datasets',\n 'minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for','estimating', 'the', 'similarity', 'between'].sort();\n \n var b = ['xxx', 'i', 'a', 'the', 'probabilistic', 'data', 'structure', 'for','estimating', 'no', 'similarity', 'between', 'dataset'].reverse();\n\n var c = ['xxx', 'i', 'a','probabilistic','structure','for','no','dataset'];\n \n var aHash = new Minhash({numPerm:32});\n var bHash = new Minhash({numPerm:32});\n var cHash = new Minhash({numPerm:32});\n\n var index = new LshIndex({bandSize:2});\n\n hashWords(a, aHash);\n hashWords(b, bHash);\n hashWords(c, cHash);\n \n index.insert('a',aHash); index.insert('b',bHash); \n \n for (let i = 0; i < 1; ++i) {\n index.insert(String.fromCharCode(i+99),cHash);\n }\n \n return [index,aHash,bHash,cHash]\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9771,"value":"fastCount = {\n\n let init = corpus[0].slice(0,5000)\n let span = init.length\n let dict = {}\n \n let t1= performance.now()\n let r;\n for (let i = 0; i < span; ++i) {\n let o = {}\n let w = init[i].split(' ')\n \n\n //dict[i] = o;\n for (let j = 0;j < w.length;++j){ \no[w[j]] = 1\n\n //let s = w[j]\n // dict[s]?\n // dict[s]++:dict[s] = 1\n }\n //dict[i] = o\n }\n\n return {\n dict,\n time: performance.now()-t1\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W3f","stdlib":"1","titling":"auto"}} 30:"$2f:body"