▲ | xelxebar 3 months ago | |
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... | ||
▲ | rak1507 3 months ago | parent [-] | |
The append is the only thing that is O(1), finding the deletion mask is linear (≠ is linear, isn't it?) and the actual deletion is also linear (⌿ is also linear).
|