4 ms·
I'm ok with minimalism, but interning strings in a simple array with linear search only scales to ~100 entries. a hash table can be written in 15 lines.
by rurban 8y ago
I'm ok with minimalism, but interning strings in a simple array with linear search only scales to ~100 entries. a hash table can be written in 15 lines.
- UncleEntity 8y agoIt's actually a linked list (with linear search). Good enough for such a simple interpreter methinks...
- sitkack 8y agoSounds like a great pedagogical tool to me!
- shawn 8y agoThis isn’t true. Emacs interns strings in a global obarray, which is a simple array with linear search. I hear emacs scales well.
- pg314 8y agoThat is incorrect. An Emacs obarray is a kind of hash table [1]. [1] https://www.gnu.org/software/emacs/manual/html_node/elisp/Creating-Symbols.html https://www.gnu.org/software/emacs/manual/html_node/elisp/Cr...
- shawn 8y ago(make-vector length 0) Interesting. That threw me off. I overlooked the previous paragraph: In Emacs Lisp, an obarray is actually a vector. Each element of the vector is a bucket; its value is either an interned symbol whose name hashes to that bucket, or 0 if the bucket is empty. Each interned symbol has an internal link (invisible to the user) to the next symbol in the bucket. Because these links are invisible, there is no way to find all the symbols in an obarray except using mapatoms (below). The order of symbols in a bucket is not significant. Thanks!
- deleted 8y ago[deleted]
- krig 8y agoIt works surprisingly well, and appeals to me for its compactness. But i maybe I’ll switch to hashing if I can squeeze that in.