531–540 of 772 posts
Earlier quoted context omitted.
It does, but the map has a reference to it, so it will "leak" (in gc languages an unwanted reference is considered a leak). If this map got rather large, you could end up with a rather large heap and it would be un-obvious why at first.
Do Promises hold a reference to the chain of functions that end in the result? If so, that seems like a bug.
Earlier quoted context omitted.
You can put the promise into the cache immediately but you can only put the result from the promise into the cache once the promise resolves. So if an identical request comes in a second time before the promise has been resolved, then if you are caching the promise you have a cache hit but if you are caching the result then you have a cache miss and you end up doing the work twice.
I am still not understanding the purpose of this as I believe it is grounded on the wrong assumption. Pretty much every single asynchronous operation other than some `Promise.resolve(foo)` where foo is a static value can fail. Reading from the file system, calling an api, connecting to some database, etc. If the original promise fails you're gonna return a cached failure. Mind you, I'm not stating this might be compl…
This is usually a good thing, and even in cases where it isn't, it's often a worthwhile trade-off.
In the common case a failure will either be persistent, or - if load/traffic related - will benefit from a reduction in requests (waiting a while to try again). In both of these cases, where your first key request fails, you want the immediately-following cases to fail fast: "caching" the promise caches the failure for the duration of one request (presumably the cache is emptied once the promise resolves, allowing subsequent key accesses to retry).
The less common case where the above isn't true is where you have very unstable key access (frequent one-off failures). In those cases you might want a cache miss on the second key request, but successful key retrieval usually isn't as critical in such systems which makes the trade off very worthwhile.
Earlier quoted context omitted.
Wouldn't you at least be looking at nlog(n) for the sort in the merge join?
Yes, if the data is not already sorted. Thus it's O(n) for already sorted data and O(n log(n) + n) -- which simplifies to O(n log(n)) -- for arbitrary data.
Here's a few fun ones: the Burrows–Wheeler transform, suffix arrays in general, Kanerva's fully distributed representation, reduced-affine-arithmetic numbers, LSM trees, binary array sets, sparse array sets, and gap buffers. (I'm not sure how nobody had mentioned gap buffers yet on the thread, but if they did I didn't see it.) — ⁂ — The Burrows-Wheeler transform is the second character of each suffix in a (cyclic) su…
> Much better advice is found in The Practice of Programming: almost all programs can be written without any data structures but arrays, hash tables, linked lists, and, for things like parsing, symbolic algebra, or filesystems, trees. So just use those if you can. In general, as much as possible use stuff you already have good libraries for. Often, you can get away with much simpler data structures with a bit of clev…
I'm not that enthusiastic about libraries. Yes, using a good LSM-tree library will keep you and your successors from spending holiday weekends debugging your LSM-tree implementation — probably, because "good" doesn't mean "perfect". But it won't be a tenth as fast as an in-RAM hash table, if an in-RAM hash table can do the job. And CPython's standard hash table usually won't be a tenth as fast as a domain-specific hash table optimized for your needs.
That doesn't always matter very much, but it does always matter. Especially now with the advent of good property-based testing libraries like Hypothesis, if you can run a function call in 0.1 ms instead of 1.0 ms, you can do ten times as much testing with a given amount of resources.
Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…
I have written many tools that do something like this, very useful. Just gotta be careful with memory leaks, so (for a TS example) you might want to do something like this: const promiseMap > = new Map(); async function keyedDebounce (key: string, fn: () => R) { const existingPromise = promiseMap.get(key); if (existingPromise) return existingPromise; const promise = new Promise(async (resolve) => { const result = awa…
> Good use-case: routing. Say you have a list of 1 million IPs that are [deny listed]. Apparently, bloom filters make for lousy IP membership checks, read: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ CritBit Trie [0] and possibly Allotment Routing Table (ART) are better suited for IPs [1]. [0] https://github.com/agl/critbit [1] https://web.archive.org/web/20210720162224/https://www.harig...
If it should take into account ip blocks then just put the ranges in an sorted index and you have logarhytmic complexity for search (if speed is important and the blacklist is not huge, you can also expand the blacklisted ranges by individual ip and put them in a Map so that you get complexity of 1 for ip range search)
https://en.wikipedia.org/wiki/Macaroons_(computer_science) are very interesting to me. Think of it as a JWT that you can narrow down the authorizations for without needing to communicate with a server, so if you have read permissions to all your photos you can add a caveat saying `photoid=123456` and share it, and the recipient can only read the photo 123456. The caveats can be anything, including requiring third par…
I’ve heard of these! The fly.io blog has a really cool write-up about them. Definitely an under appreciated concept. IIUC, you can even validate the “sub issued” macaroons offline, provided you know the validity of one of its ancestors up the chain. Is this correct, or am I misunderstanding?
Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…
Earlier quoted context omitted.
Firstly, accessing an arbitrary list index is O(N), whilst a Zipper can access its focus in O(1) (shifting the focus is O(1) for both Zippers and list+index) Secondly, using an index forces us to do bounds checks, keep track of the length (or re-calculate it at O(N) cost), etc. whereas a Zipper is "correct by construction"; i.e. every value of type (List[A], A, List[A]) makes sense as a zipper; whereas many values of…
> accessing an arbitrary list index is O(N) I think you mean linked-list here. Parent is talking about "arrays".
Yes, I specified this explicitly, e.g. "The Zipper acts like a linked-list with a cursor" and "Where [a, b, c] denotes a singly-linked list".
> Parent is talking about "arrays"
You're using quotation marks, but I don't see what you're quoting? The parent explicitly says: "a list and an index"
In any case, arrays come with most of the same problems I mentioned for lists:
- They have invalid states, e.g. ([], 42)
- They require bounds-checking, a consistent notion of subtraction on the index type, etc.
- They can't be infinite
- They require O(N) time, O(N) memory (and O(N) garbage if we're discarding the old value) to replace the focused element
- etc.
Plus, arrays come with all sorts of extra gotchas, like buffer-overflows, pre-allocation/re-allocation decisions, over/under-provisioning, etc.