Having been told today for the eightieth time that I am “a fast programmer”, it makes me wonder. I’ll be given a project and get to work on it, finish it off, do two more projects, and look up to see my fellows ducking their heads trying to avoid attention as they still try to figure out just how they are to complete their one first task.
Now, at my first company, I and my fellow programmers were hired on a startup budget with no greater expectation than to be able to fix some function calls in Java to switch from the DoJa API to J2ME, so it wasn’t necessarily cream of the crop we were talking.
However, at this moment I am contracting out to one of the five largest electronics companies in Japan. And still there is only one other guy who even seems like he can put code to screen of seven.
It just seems odd that there are that many professional programmers in the world for whom writing some app that does, say, read in a file and swap the words in the sentence to reverse order and takes days to do it rather than an hour and change. Is the profession really this flooded with people who struggle with every line they write? It’s scary almost to think of when you think of the amount of things in life that are now run by computers. I’m hoping that it is just a matter that I have been working with contract workers mostly.
But anyways. As said, I do appear to be “fast” in my coding. My boss when trying to get companies to take me part time says, “Twice the amount of code as any other programmer in the same time, guaranteed.” Though I suspect that this may have come from coding hardware stuff where a lot of the coding seems to be trying lots of register settings and whatnot. For just straight application work, I’m guessing at three times speed.
So, it doesn’t really matter I guess, but I thought it might be fun to see how fast various dopers can create an app to the same specifications.
Specification:
You are to create a storage structure that is a sort of trie. The language is C (unless you know how to translate the spec over) and it is assumed that sizeof(void*) == sizeof(uint32_t)
It will have this interface:
int trie_init(struct trie *t);
Initialises the structure. Returns 0 on success, -1 on error.
void trie_delete(struct trie *t);
Frees all memory that was allocated by the structure. It will not assume that the items the user has added are allocated memory. It is up to the user to free his own items before deleting the structure.
uint32_t trie_add(struct trie *t, void *item);
Stores ‘item’ in the structure. Returns a unique key, or an invalid value–which will be the max value of a uint32_t type–on error.
void* trie_get(uint32_t key);
Get the item by key.
int trie_remove(uint32_t key);
Delete the item referenced by the key. Returns 0 on success, -1 on error.
void trie_enumerate(void (handler)(void));
‘handler’ will be called for each item present in the structure, and the item passed to it.
The structure itself will be based on nodes like so:
struct trie_node {
uint32_t used; /* bitmask flags - something in the slot /
uint32_t pointer; / bitmask flags - the something is a node pointer */
void *items[32];
}
To insert items into an empty structure, you will assign keys based on a counter. That is, the first item will be 0, then 1, 2, and so on. Each five bits of the key (from low to high) will indicate a slot for the item to be placed in a node. So if the key is 0, then it will go in slot 0 of the node. This will get you to 31.
The low five bits of 32 (which equate to 0) will vie with 0 for slot 0 in the node, so you will make a second node.
You will make slot 0 be a node pointer instead of an item holder, and put the new node in it. item 0 and item 32 will be delegated to the proper slots in the new node based on their second quintuple of bits.
You will maintain a variable that contains the last key that was deleted. I.e. if I delete item 6, then we will store 6 in this variable. When you delete an item, you will place the value in the last deleted key variable in the deleted slot, and then put the item just deleted into the variable. (I.e. if I had 6 in it, and I just deleted 2, I will place the number “6” in slot 2, and set the variable to 2.)
When you add an item and there have been items deleted from the structure, you will use the last deleted key for the new item. Before you insert the item into that slot, you will take the value that is stored there (which will be the next previously deleted slot) and place it in the “last deleted key” variable. (I.e. Use slot 2, but take the 6 that is there and put it back in the variable first.) No new slots will be used or nodes created until there are no further deleted slots left.
Please time yourself from the time you start your preparations (i.e. working stuff out on paper or whatever) to when you have a fully debugged and working implementation. Or, if you don’t feel like making it, feel free to just throw out how much time you would guess based on an eyeballing.
The type uint32_t is defined in stdint.h if you aren’t aware of it. The structure itself is of my own design and I’ve never used it for any company I have worked for so no I am not giving away some trade secret. I have implemented it once, and I believe it took me about 3 or 4 hours. The goal was to create a structure type to hold a database table, though I’ve done no testing in terms of relative speed versus other structures.
For anyone who doesn’t have a C compiler at home (and is on a Windows machine), I recommend Dev-C++ which is free, works quite well, and can compile Windows applications, or even OpenGL right from the box.