Remix clone Hacker News

new | show | ask | jobs Github

▲

rak1507 3 months ago

The problem is that this isn't a "hashmap" in any meaningful sense, because all the operations are O(n).

▲ xelxebar 3 months ago | parent [-]

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).

       ]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        │
 └──────────┴────────────┘