671–680 of 772 posts
Think of them as double ended priority queues. O(n) construction with O(lgN) mutations. Both the min and max elements are quick to get O(1).
The paper is short and the data structure is elegant. I read it a few years ago in uni and made me appreciate how greatly useful can be implemented very simply.
Earlier quoted context omitted.
I have always wanted to really understand this data structure. Sure, I can follow the analysis with the potential functions and all, but I never really understood how Tarjan came up with the functions in the first place. Does anybody have a resource which intuitively explains the analysis?
Robert Sedgewick has a great explanation in his Algorithms book. He has gorgeous diagrams alongside his explanations.
Earlier quoted context omitted.
I spent a long time looking at an algorithm for long range force calculations called the Fast Multipole Method which is O(N) and found that practically it couldn't compete against an O(N log N) method we used that involved FFTs because the coefficient was so large that you'd need to simulate systems way bigger than is feasible in order for it to pay off because of cache locality, etc.
Honestly, that is not too uncommon. For top level algorithm choice analysis, "rounding" O(log(n)) to O(1), and O(n*log(n)) to O(n), is often pretty reasonable for algorithm comparison, even though it is strictly incorrect. It is not uncommon for a simple O(n*log(n)) algorithm to beat out a more complex O(n) algorithm for realistic data sizes. If you "round" them to both O(n), then picking the simpler algorithm becaus…
Earlier quoted context omitted.
My writeup of union find is in https://dercuano.github.io/notes/incremental-union-find.html . I did not in fact find a way to make it efficiently support incremental edge deletion, which is what I was looking for.
> I did not in fact find a way to make it efficiently support incremental edge deletion, which is what I was looking for. I don't understand this goal. The interior connections aren't relevant to a union-find structure; ideally you have a bunch of trees of depth 2 (assuming the root is at depth 1), but the internal structure could be anything. That fact immediately means that the consequence of removing an edge is no…
My quest was to find a way to incrementally delete edges from E, not E'. You're talking about deleting edges from E', which I agree is not generally a useful thing to do.
For example, your N might be the cells of a maze map, and your E might be the connections between adjacent cells that are not separated by a wall. In that case you can tear down a wall and add a corresponding edge to E. But it would be nice in some cases to rebuild a wall, which might separate two previously connected parts of the maze. I was looking for an efficient way to handle that, but I didn't find one.
Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is…
Ted Nelson named them Enfilades. Guy Steele called them Monoid Cached Trees.
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…
FYI this also extends to higher dimensions. I once used it to split a single loop variable into 3 for a "normal" matrix multiplication to get a huge speedup. Unrolling the inner 3 bits is possible too but a bit painful.
Also used it in ray tracing to scan pixels in Z-order, which gave about 10 percent performance improvement at the time.
But yes, I must look at this grey code step to see if it makes sense to me and understand why its not helping you even with reduced cache misses.
Earlier quoted context omitted.
I decided to try implement get_gray_xy. I am wondering how you can generalise it to any number of loops and apply it to nested loops of varying sizes, that is if you have three sets and the sizes are 8, 12, 81. 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…
Here is the implementation of get_gray_xy that I used: static uint64_t deinterleave(uint64_t x) { x = x & 0x5555555555555555; x = (x | (x >> 1)) & 0x3333333333333333; x = (x | (x >> 2)) & 0x0f0f0f0f0f0f0f0f; x = (x | (x >> 4)) & 0x00ff00ff00ff00ff; x = (x | (x >> 8)) & 0x0000ffff0000ffff; x = (x | (x >> 16)) & 0x00000000ffffffff; return x; } static void get_gray_xy(uint64_t n, uint64_t *x, uint64_t *y) { uint64_t gra…
Then isInSet(x) = index[x] >= 0 && index[x] and rmFromSet() is left as an exercise.)
The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.) The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged wi…
Wouldn't that be extremely useful and a polynomial solution for 3-SAT, which is NP complete?
Spatial hashing. Say that you have data that is identified with points in 2D or 3D space. The standard way that CS students learn in school to represent this is via a quadtree or octree. However, these tree data structures tend to have a lot of "fluff" (needless allocations and pointer chasing) and need a lot of work to be made efficient. Spatial hashing is the stupidly simple solution of just rounding coordinates to…
I'm still looking for a good spatial index for points. I'll think about yours.