221–230 of 772 posts
Just because of the Type being introduced very late to the language, and another very successful method named identically makes it almost impossible to google your way out of any situation.
You have to rely on core documentation and link lists. Just by using “new Map()” in JS, you’re suddenly ehem mapped 30 years back in time!
These are binary search trees, but when you 'splay' the tree (such as by search) it rebalances the tree so that the search result is on top. This means while it is O(log n) for operations like other self-balancing trees, it optimizes tree depth in the face of non-random access so that recently accessed items are fewer steps into the tree.
Piece tables:
A bit more common for text editors, where you need to represent a sequence of characters in a form that allows efficient memory use and fast insertions/removals (so editing the first line isn't moving the 10MB of data that follows it). You create a series of references to spans (or pieces) of the document, possibly starting with a single span pointing to a mmap() version. Edits are done by appending/prepending pieces, which are potentially just references to subsequences of items created in fresh memory, appended into a buffer. Saving can create a single sequence (and a single span).
This has interesting variations:
- Put attributes on the pieces for formatting, such as indicating text should be rendered a different color or bolded.
- Create a hierarchy of pieces-of-pieces. With formatting attributes you are then dangerously close to a DOM.
- Retain old copies of a piece table - since your original mmap() file hasn't changed and your changes are in an append-only buffer, those piece table copies provide undo/redo state.
The fact that you could perform linear algebra on documents and words, to get out a number that somehow quantified how close a document was to another really surprised me back in the day. Grew a new appreciation for what exactly those vectors in linear algebra could represent.
Not in the field so don't know how obscure it is though.
[1]: https://en.wikipedia.org/wiki/Latent_semantic_analysis#Laten...
Static arrays - when was the last time you used a static array?
What do you mean by “static” exactly? It could be referring to an array that doesn’t change size. Or the contents are read-only. Or do you mean C/C++ static linking? Or something else? In C, C++ and CUDA I use constant fixed-size arrays with lookup tables of specialized data all the time. I also use small arrays to hold temporary results that need to get first collected, and then sorted or processed together. Seems l…
Simple code runs fast.
See Pike on Complexity - Rule 3: https://www.lysator.liu.se/c/pikestyle.html
The Zipper acts like a linked-list with a cursor, or "focused element"; it's implemented as a pair of lists in opposite orders; or, equivalently but more symmetric, as triple of (List[A], A, List[A]) Say we have a zipper containing [0, 1, 2, 3, 4, 5], and we're focusing on the 3. In code this will look like: ([2, 1, 0], 3, [4, 5]) Where [a, b, c] denotes a singly-linked list, with O(1) head (returning a) and tail (re…
I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1]. What is the benefit here?
“ In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Donald Knuth's Algorithm X for the exact cover problem.[1] Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.”
HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d comp…
This is a tree-like structure where the structure of the tree is fully determined by the number of leaves N. Specifically, each 1-bit in the binary representation of N corresponds to one of the tree's perfect binary subtrees. For that reason, I think of it more as "structure imposed upon a list" rather than a typical mutable tree with pointers and such.
What are the applications of this data structure? I am only aware of one: computing the Merkle root of a large amount of data in streaming fashion. The funny thing is that it's been discovered independently multiple times: in BLAKE3, Sia, Utreexo, and more. Maybe someday, someone will find another use for it. :)
The easy and efficient way to test if a value is in a list is to use a hash set or dictionary. Complexity is always O(1).