Created
December 23, 2023 17:18
-
-
Save programaths/d54b2b3f9ec2b298a9e1914786768483 to your computer and use it in GitHub Desktop.
Dumb lookups
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
<!doctype html> | |
<html lang="en"> | |
<head> | |
<meta charset="UTF-8"> | |
<meta name="viewport" | |
content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0"> | |
<meta http-equiv="X-UA-Compatible" content="ie=edge"> | |
<title>Power Search</title> | |
<link rel="stylesheet" href="style.css"> | |
<script type="module" src="main.js"></script> | |
</head> | |
<body> | |
<div><label for="lookup">Word search (466550 entries) </label><input type="search" id="lookup"></div> | |
<div id="names"></div> | |
</body> | |
</html> |
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
let txt=await fetch('words.txt').then((r)=>r.text()); | |
let names=txt.split("\n"); | |
let field=document.body.querySelector('#lookup'); | |
let namesDisplay=document.body.querySelector('#names'); | |
field.addEventListener('input',()=>{ | |
namesDisplay.innerHTML=''; | |
if(field.value.length>0) { | |
const startTime = performance.now(); | |
let filtered = names.filter((it) => it.includes(field.value)); | |
const timeTaken = performance.now() - startTime; | |
namesDisplay.innerHTML += `<div>Took: ${timeTaken} ms</div>` | |
let i = 0; | |
while (i < 10 && i < filtered.length) { | |
const index = filtered[i].indexOf(field.value); | |
let prefix = filtered[i].substring(0, index); | |
let suffix = filtered[i].substring(index + field.value.length); | |
let match = filtered[i].substring(index, index + field.value.length); | |
namesDisplay.innerHTML += `<div>${encodeURI(prefix)}<strong>${encodeURI(match)}</strong>${encodeURI(suffix)}</div>`; | |
i++; | |
} | |
} | |
}) |
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
let txt=await fetch('words.txt').then((r)=>r.text()); | |
let names=txt.split("\n"); | |
class Trie { | |
constructor() { | |
this.root={children:{}}; | |
} | |
/** | |
* | |
* @param string {string} | |
* @param index {number} | |
*/ | |
addNodes(string,index){ | |
let cn=this.root; | |
string=string+'$'; | |
for(let c of string) { | |
if (cn.children.hasOwnProperty(c)){ | |
cn=cn.children[c] | |
}else{ | |
cn.children[c]={children: []} | |
} | |
} | |
if(Array.isArray(cn.indexes)){ | |
cn.indexes.push(index) | |
}else { | |
cn.indexes = [index]; | |
} | |
} | |
getIndexes(string,count){ | |
let result=[]; | |
let cn=this.root; | |
for(let c of string) { | |
if (cn.children.hasOwnProperty(c)){ | |
cn=cn.children[c]; | |
}else{ | |
return result; | |
} | |
} | |
let q=[cn]; | |
while (q.length>0 && count>0){ | |
cn=q.pop(); | |
if(Array.isArray(cn.indexes)){ | |
result.push.apply(result,cn.indexes); | |
count=count-cn.indexes.length; | |
} | |
for(let child of Object.values(cn.children)){ | |
q.push(child); | |
} | |
} | |
return result; | |
} | |
} | |
let trie=new Trie(); | |
for(let [index,name] of names.entries()){ | |
for(let i=0;i<name.length;i++) { | |
trie.addNodes(name.slice(i), index); | |
} | |
} | |
let field=document.body.querySelector('#lookup'); | |
let namesDisplay=document.body.querySelector('#names'); | |
field.addEventListener('input',()=>{ | |
namesDisplay.innerHTML=''; | |
if(field.value.length>0) { | |
const startTime=performance.now(); | |
let indexes = trie.getIndexes(field.value,50); | |
let filtered = indexes.map((it) => names[it]); | |
let i = 0; | |
const timeTaken=performance.now()-startTime; | |
namesDisplay.innerHTML += `<div>Took: ${timeTaken} ms</div>` | |
while (i < 50 && i < filtered.length) { | |
const index = filtered[i].indexOf(field.value); | |
let prefix = filtered[i].substring(0, index); | |
let suffix = filtered[i].substring(index + field.value.length); | |
let match = filtered[i].substring(index, index + field.value.length); | |
namesDisplay.innerHTML += `<div>${encodeURI(prefix)}<strong>${encodeURI(match)}</strong>${encodeURI(suffix)}</div>`; | |
i++; | |
} | |
} | |
}) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment