I request an extension primitive called dta_o1 or dta_hashtable, and dta_hashtablemethod(table, methodname, args). This will allow large datastructures to move at quick, O(1) speed. Another alternative is making it return a special list proxy where you use built in INSERT/DELETE/ITEM to change the contents. Thoughts?
Why would you want a single method with a methodname input instead of one procedure per method?
Of course you can write this in Snap! and still get the same O(1) behavior. How much faster do you think doing it in JS would be?
I’m reluctant to start down the path of JS extensions for data structures. If we did this, next you’d ask for heaps (in the dense tree sense, not the big pile of anything sense) or red-black trees or B-trees or … etc.
PS Of course the advertised O(1) behavior of hash tables is kind of a cheat, since the hashing function will probably take time proportional to the length of the hash string, which is probably ≈ the log of the size of the hash table! :~)
Yes, it is possible in Snap!. However, it is evidently way slower (after doing many tests, JS maps are \approx 12,075 \text{ to } 13000 times faster). (And correct me if I’m wrong, I’m still learning about memory,) but Snap! does not support sparse arrays, which also increases speed.
I don’t want to bog down the extensions library with my suggestion.
Maybe a separate library, “Data Structure” with this and other data structures as you please without polluting the default extensions?
YES, the API could be Split into different blocks without bogging down extensions
(And correct me if I’m wrong, I’m still learning about memory,) but Snap! does not support sparse arrays, which also increases speed.
If you use mutators (ADD, REPLACE, etc.) on a list, Snap! uses a native JS array. If you construct the list with IN FRONT OF or other purely functional means, we use linked lists. (Umm, except that NUMBERS FROM makes a JS array.)
A data structures library that has all the standard CS 2 ADTs would be a good thing, I think.
Yes, but it does not directly empty the memory slot. If you were to make a “sparse” array in Snap, it still allocates a massive amount of pointers to a nil value instead of allocating literally 0 space.
Oh. Are JS hashtables sparser than JS arrays?
What I meant is you can’t get a real sparse array in Snap! because there is no way to actually make the memory slot take up no space. The closest thing is using blank (stored as empty string) to put into the array, which still allocates memory.
actually you can if you use extension [err_ignore V] @:> ::reporter
Just because it reports JS null (Which you can also do with CALL FALSE) doesnt mean it takes up 0 memory
yea, but thats the closest you can get
even an empty slot’s metadata takes up space even if its small
I didn’t know you can do JS null in Snap!. Interesting. :~)
That’s not because Snap’s slow, that’s because you made a naive "hash"map.
It has nothing in common with a hashmap. It’s a standard map/dictionary API built into Snap, implemented as a list of lists. It can be made O(log N) using a sorted list and binary search.
Feel free to benchmark a more sophisticated map implementation.
BTW: Performance depends on the key length. To get consistent results, I’m using a trivial map populated with (key: "#"i, value: i) pairs.
I don’t think it’s relevant to this discussion to benchmark something that isn’t a hash table. Of course that’ll be a slower order of growth.
I found this project by user @zaydiscool777. (The other search results were implementations using JS Function to call JS’s hashtable implementation. This one is actually done in Snap!.) I instrumented it a little (and debugged it a little) with this result:
So as you can see the results are sublinear but far from constant. I’m not sure what to make of that.
Oh wait it turns out I have my own hashtable implementation that wasn’t showing up in my search because I hadn’t published it! Debugged and instrumented similarly to the other one:
Still way slower than JS of course (those times are in seconds, not milliseconds), but it does seem to be O(1). (I think the time for the smallest table is longer because I’m doing more enters and lookups than the length of the table, so getting more collisions.)
It’s a future request to implement native, dedicated map functionality.
So a comparison to the built-ins seems to be relevant.
Testing an insertion performance is more meaningful if performed on a pre-populated map.
Your tests are different so result are not comparable.
You allocated empty map of given size and insert 10k pairs (key: i, value:i)
(key:"#"i, value:i) created with string_hash_function does not work.
I used much more data to create this graph. It’s clearly O(n).
The Snap! code is O(1), which is strange. My best guess is some quirk with low-level reallocations and general jank. I don’t know why your implementation is O(1), however.
I couldn’t find an extension, or even a library, that uses this method and claims to be a dictionary/hashmap. This is the standard, but that’s because Snap! isn’t known or made to be fast.
Why are you comparing a hashmap to a naive linear search map?
I highly suggest you use @bh’s hash map implementation unless for some reason you want to perform 10,000 lookups in millisecond time (why?).
