Last active
March 2, 2024 06:10
-
-
Save Phryxia/417687b9b3365901cdf2f0d0a26263e0 to your computer and use it in GitHub Desktop.
Random data structure using bless of dimensionality
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
interface BinaryTrieNode<T> { | |
value?: T | |
lc?: BinaryTrieNode<T> | |
rc?: BinaryTrieNode<T> | |
} | |
class BinaryTrie<T> { | |
root: BinaryTrieNode<T> = {} | |
constructor(public readonly depth: number) {} | |
public get(key: boolean[]) { | |
let node: BinaryTrieNode<T> | undefined = this.root | |
let i = 0 | |
while (node && i < this.depth) { | |
if (key[i]) { | |
node = node.lc | |
} else { | |
node = node.rc | |
} | |
++i | |
} | |
return node?.value | |
} | |
public add(value: T) { | |
const key = this.createKey() | |
let node: BinaryTrieNode<T> | undefined = this.root | |
for (const b of key) { | |
if (b) { | |
node = (node!.lc ??= {}) | |
} else { | |
node = (node!.rc ??= {}) | |
} | |
} | |
node.value = value | |
return key | |
} | |
public remove(key: boolean[]) { | |
let node: BinaryTrieNode<T> | undefined = this.root | |
let i = 0 | |
const stack = [] as BinaryTrieNode<T>[] | |
while (node && i < key.length) { | |
stack.push(node) | |
if (key[i]) { | |
node = node.lc | |
} else { | |
node = node.rc | |
} | |
++i | |
} | |
if (!node) return | |
while (stack.length) { | |
const top = stack.pop() | |
const nextTop = stack[stack.length - 1] | |
if (!nextTop) break | |
if (top === nextTop.lc) { | |
delete nextTop.lc | |
if (nextTop.rc) { | |
break | |
} | |
} else { | |
delete nextTop.rc | |
if (nextTop.lc) { | |
break | |
} | |
} | |
} | |
} | |
public has(key: boolean[]) { | |
let node: BinaryTrieNode<T> | undefined = this.root | |
let i = 0 | |
while (node && i < this.depth) { | |
if (key[i]) { | |
node = node.lc | |
} else { | |
node = node.rc | |
} | |
++i | |
} | |
return !!node | |
} | |
private createKey() { | |
let key: boolean[] | |
do { | |
key = Array.from(new Array(this.depth), () => (Math.random() > 0.5 ? true : false)) | |
} while (this.has(key)) | |
return key | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
It's just stupidly simple binary trie with random key generation. But if
depth
is significantly big (imo more than 64), there is almost no chance of collision between created key(s) and existing key(s). Note that the time complexity never affected by number of entries, so it can achieve O(1) time complexity of reading, writing and deletion. If there is a case of having insanely many entries, just increasedepth
a little bit(>80) would resolve collision issues.This stupid data structure is inspired by Vector Symbolic Architecture (or Hyper Dimensional Coputing). This uses blessing of dimensionality. This implementation is just proof of concept, and I hope more better performance-friendly improvement would be found. Here are some suggestions.
But actually this doesn't seem to be helpful in most real cases, since the constant is fairly big and tree has bad local cache efficiency. They can't be sorted neither. There are better ways to handle hash collision in reasonable cost with more tiny, compact hash data sturctures.