penitent, turbulent, multiplex!

“What would you recommend to the programmer if … each integer could appear at most ten times? How would your solution change as a function of the available storage?”

I ignored the last part of this question because it’s a lot like the previous.

My solution to the first part basically involves maintaining a count for each integer instead of a single bit. You can count up to 10 in a nibble — up to 15, actually — so you can get away with using 4 bits for every int.

My solution, which I called NibbleCounter for lack of a better name, can be found here:

NibbleCounter: NibbleCounter.h, NibbleCounter.cc
With syntax highlighting: NibbleCounter.h, NibbleCounter.cc

“Solve Problem 1-3 using strictly no more than 1 megabyte of space.”

I didn’t actually write code for this one since it’s not much different from 1-3. We’re only allowed 1 megabyte, or 8 388 608 bits. So we can only maintain flags for up to roughly 8 million ints at a time, but we’ve got 10 million to deal with.

My idea was to do two passes of the list. First time around you accept only integers < 5 000 000, and slot them in the bit vector as usual. You then emit all the integers that have bits set in the vector.

Clear the vector, and now in the second time around you accept only integers 5 000 000 to 10 000 000. You’ll have to subtract 5 000 000 each time from the number you’re handling in the unsorted list to actually find the index in the bit vector, and then add it again when you spew the numbers from the last half of the list on the screen.

Turns out that’s the solution that Bentley came up with too. Woo. I can’t really think of any other way to do it…

“Compare the runtime of the system sort and bitmap sort.”

The program I used to do the comparison is here, in hybrid C/C++: sort_compare.cc, with syntax highlighting if you prefer.

Tests we run on my MacBook. I used the program listed in the previous post (the solution to exercise 1-4) to generate the test data. I omitted the time required to print the sorted list to the terminal, but included the time required to read the numbers from disk. Numbers were restricted to the range [0, 10 000 000]. Times are stated as user time in seconds, as measure by the “time” command.

The bit vector sort is faster and the difference becomes more noticeable as the file size grows. It could potentially be made faster still by not copying the results back to the input vector and by inlining the Set() and Get() member functions, but the first is sort of an artificial use case and the second is just an unholy pain. You have to love compilers that are smart enough to rearrange your code in arcane ways but that won’t permit you to inline member functions unless you ram the whole implementation into the header. Blargh.