The basic idea is open addressing, but without any redirections (thus making Swiss tables very memory efficient). Also, Swiss tables store a densely packed array of metadata with each entry consisting of 1 byte (which makes the metadata table easier to fit into CPU cache, as opposed to, say, a metadata of pointers of 8 …
Author Archives: Mark Taylor
Founding Our Awesome Kick-ass Company
Today is a special occasion (& might be a historic moment) that we might appreciate a few years later: I, Yichuan Wang, & Robin Qiu just founded our own company. We were roomies in college, and they’re brilliant & awesome guys, and I firmly believe in a few years we will create a very bright …
Monty Hall Problem
This is actually a tricky problem, but really fun (a brain teaser). Here is the problem (I’ll just copy it from Wikipedia, lazy evil being :) Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say …
A Wet Dream You’ll Never Wanna Wake Up From
I just couldn’t believe it, … seemed after I told Ania how desperately, madly I’ve fallen love with her, we gazed into each other’s eyes, and…, and the most amazing, exciting thing that I’ve always dreamed of happened… WOW, she kissed me passionately, it was a big sloppy kiss, a minutes-long tongue kiss, a hell …
Continue reading “A Wet Dream You’ll Never Wanna Wake Up From”
Efficient Ways to Sort Strings
see the details at https://stackoverflow.com/questions/6972635/efficient-string-sorting-algorithm/71349193#71349193
The Bizarreness of Optimization
Background: consider the hashtable with closed addressing/separate chaining: Typically, we can have two different schemes to link through all the nodes. One is to link the last node of the current bucket to the first node of the next non-empty bucket. See the above picture and imagine taht there are links among these buckets. Another …
How To Implement A Real Emplace Routine
Above is a piece of code that attempts to implement the emplace family routines. One can insert something like const value_type& (value_type&&) val or variadic arguments Args&&… args, both of which then can be handled by the insert_leaf_at subroutine Of course, this simple implementation is flawed as it requires an extra move operation. In order …
Innovation
Happy Happy Birthday
So, happy happy birthday to a marvelous friend, Ania;)
A Running Example
I made a test in Dev-C++ (version 5.7.1, with MinGW GCC 4.8.1 32-bit), and in debug mode, via the CPU Window it produced the following instructions: procedure main: subroutine add: Following these instructions, I drew a simple diagram (partial, incomplete): The arguments for printf were left out in this diagram for simplicity, but it is …