4 ms·
Disclaimer: I've never used Janet, but I am pretty familiar with Clojure. In Clojure, there are lists, but the most common structure for sequential data is act
by tombert 5y ago
Disclaimer: I've never used Janet, but I am pretty familiar with Clojure.
In Clojure, there are lists, but the most common structure for sequential data is actually a vector [1], which works more-or-less as a slightly modified version of the Clojure version of a hashmap. Advantages of doing it this way is that you get log32 indexed lookup times (vs linear for lists), and you also get log32 [2] append-to-the-end semantics instead of "push to the beginning" that you have with lists.
In practice it generally doesn't affect a lot, but occasionally when I do need to put an item in the front of a collection, I will wish I had used a list instead of a vector, but I feel like the far more-common usecase is to append to the end, since in Erlang there's been a few times where I end up having to reverse the list after I'm done building it.
[1] At least how I use it, I haven't done any statistics to prove this.
[2] Don't let the log scare you! Log32 is very good and also effectively constant time for most in-practice use cases. Log32 of a billion is basically six, meaning you're dealing with a constant factor times six hops for inserts and lookups on a billion elements.
- mst 5y agoPhil Bagwell's VList data structure seems really interesting as a way to avoid a bunch of the pitfalls of naive lists performance-wise - the paper's good fun and there seems to be an implementation in racket for anybody who wants to play with it.
- spicybright 5y agoDoes any one have a copy of anything related to this? Wikipedia had an article on it deleted, and I'm not getting much from the first few pages of google...
- mst 5y agoRacket implementation: https://docs.racket-lang.org/functional-data-structures/VList.html https://docs.racket-lang.org/functional-data-structures/VLis... There's a copy I made of the original paper here: http://trout.me.uk/lisp/ http://trout.me.uk/lisp/
- celeritascelery 5y agoThe problem with a vlist is that it doesn’t maintain lisp list semantics. You can’t implement setcdr on a vlist. But you can with something like cdr-coding.
- mst 5y agoThe paper discusses how to handle appends and similar. Assuming the majority of your lists are read-only apart from appends, you can end up with something pretty performant overall. Trade-offs all the way down as ever though.