Comment Comment by xelxebar Hey, I know you.> all the operations are O(n)Not true, fortunately!The cat-gets pattern for insertion is clearly just an O(1) append. Similar for the replicate-gets in the deletion.Finding the deletion mask might be O(n) or O(log n), depending[0] on the size of your search space.Key is effectively just a radix sort, which is indeed O(n) on the keys, but a trad hashmap doesn't get any better in this case.[0]:https://help.dyalog.com/19.0/#Language/Defined%20Functions%2... parent xelxebar 1 year ago
> all the operations are O(n)
Not true, fortunately!
The cat-gets pattern for insertion is clearly just an O(1) append. Similar for the replicate-gets in the deletion.
Finding the deletion mask might be O(n) or O(log n), depending[0] on the size of your search space.
Key is effectively just a radix sort, which is indeed O(n) on the keys, but a trad hashmap doesn't get any better in this case.
[0]:https://help.dyalog.com/19.0/#Language/Defined%20Functions%2...