561–570 of 772 posts
Earlier quoted context omitted.
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.
Yeah. I know. Why would the data already be sorted?
The piece table. https://news.ycombinator.com/item?id=15387672
Mirror of original: https://web.archive.org/web/20160308183811/http://1017.songt...
From a prior post: The piece table. https://news.ycombinator.com/item?id=15387672 Mirror of original: https://web.archive.org/web/20160308183811/http://1017.songt...
HyperLogLogs! They're extremely useful for cardinality count estimation, and support set operations. https://en.m.wikipedia.org/wiki/HyperLogLog
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…
Append-Log. A grow-only linked list where you can only append elements to it. Good use-case: Lock-free concurrent reads are allowed, because there is no way committed content could change. Writes need to be Linearizable (so locking is required). Given this property, this data structure provides faster reads than a Mutex > and similar write perfs. Bonus section: Provides broadcast broadcast capabilities if used as cha…
For reads, start with an acquire read of the tail pointer, which will make all preceding writes to the list visible to you. Then you can read the list all you want up until you hit the node you read from the tail pointer without synchronization.
Edit: forgot to add mine. Not obscure by any means but Fenwick Trees are very cool IMO
Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…
I was experimenting a while ago with something that I think is related to this. If you have a quadratic algorithm where you need to compare each pair of objects in a large array of objects, you might use a loop in a loop like this: for (int i = 0; i When this algorithm runs, it will access every cache line or memory page in the array for each item, because j goes through the whole array for each i. I thought that a b…
Wikipedia says graycodes can be found by num ^ (num >> 1)
a = [1, 2, 3, 4]
b = [2, 4, 8, 16]
indexes = set()
correct = set()
print("graycode loop indexes")
for index in range(0, len(a) * len(b)):
code = index ^ (index >> 1)
left = code & 0x0003
right = code >> 0x0002 & 0x0003
print(left, right)
indexes.add((left, right))
assert len(indexes) == 16
print("regular nested loop indexes")
for x in range(0, len(a)):
for y in range(0, len(b)):
correct.add((x,y))
print(x, y)
assert correct == indexes
graycode loop indexes
0 0
1 0
3 0
2 0
2 1
3 1
1 1
0 1
0 3
1 3
3 3
2 3
2 2
3 2
1 2
0 2
regular nested loop indexes
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3Earlier 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…
When the VERY FIRST ASYNC operation is inflight the cache is immediately loaded with a Promise, which blocks all other calls while the FIRST async operation is in flight. This is only relevant to the very FIRST call. That's it. After that the promise is pointless.
As for the Promise failure you can just think of that as equivalent of the value not existing in the cache. The logic should interpret the promise this way.