Post
To process data efficiently we need to organize it. So what are some common datastructures?
We may need to track a List of items, for which hardware prefers us to use Arrays. Which stores each item in contiguous memory.
Though I see that C devs frequently find it easier to use Linked Lists, with a pointer to the next (and maybe previous) item stored alongside each item. This less efficient (with exceptions) both in terms of RAM & CPU.
1/?
Often we want a key-value Map a.k.a. Dictionary to let us lookup a value by its key.
For this we usually use a Hash Map where we compute an offset into an array from a given key, with some strategy to handle collisions. Extremely fast!
If its on a harddrive we usually use BTrees where each "page" lists keys & pointers to which page tracks the entries between them. Its still very fast!
Or in a hypothetical I favored tries, where we repeatedly lookup the next subtree by the key's next byte.
2/
Finally for today, I think I'll mention Priority Queues for which we usually implementing using Binary Heaps.
A binary heap maintains the "invariant" that a parent entry is always greater (or alternatively, smaller) than its 2 children. Typically we store the children of entry x at 2x & 2x+1.
We can remove the smallest entry by swapping with the last entry & reestablishing the invariant. And we add entries by appending it before moving up the tree to reestablish the invariant.
3/3Call it fin!
P.S. Your language's standard library should provide an implementation of these datastructures. I recommend using it.
Except C. LibC's implementation of these datastructures is quite primitive, if it exists at all.
Install bonfire.cafe
Get the full app experience
