3 ms·
The problem is that this isn't a "hashmap" in any meaningful sense, because all the operations are O(n).
by rak1507 1y ago
The problem is that this isn't a "hashmap" in any meaningful sense, because all the operations are O(n).
- xelxebar 1y agoHey, 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%20and%20Operators/Search%20Functions%20and%20Hash.htm?Highlight=Hash https://help.dyalog.com/19.0/#Language/Defined%20Functions%2...
- rak1507 1y agoThe 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). ]runtime -repeat=1s 'v←k1 ⋄ v⌿⍨←v≠2' \* Benchmarking "v←k1 ⋄ v⌿⍨←v≠2", repeat=1s ┌──────────┬──────────────┐ │ │(ms) │ ├──────────┼──────────────┤ │CPU (avg):│0.008491847826│ ├──────────┼──────────────┤ │Elapsed: │0.008466372283│ └──────────┴──────────────┘ ]runtime -repeat=1s 'v←k2 ⋄ v⌿⍨←v≠2' \* Benchmarking "v←k2 ⋄ v⌿⍨←v≠2", repeat=1s ┌──────────┬────────────┐ │ │(ms) │ ├──────────┼────────────┤ │CPU (avg):│0.8333333333│ ├──────────┼────────────┤ │Elapsed: │0.83 │ └──────────┴────────────┘