[Pdx-pm] [SOLUTION] Telephone number sorting
jkeroes at eli.net
Fri Sep 27 18:53:02 CDT 2002
> Q: What's the fastest, most space-efficient way to sort all
> of Portland's 503 phone numbers?
A: Use a bit vector. To allocate enough space for all
10,000,000 numbers, allocate 10,000,000 bits. 
To signify that a telephone number is in use, turn the bit on.
e.g. to indicate that the number 411 is in use, turn the 411th bit on.
e.g. To indicate that telephone number 555-1234 is in use, turn the
5,551,234th bit on.
This makes sorting very easy: we don't *have* to sort anything, we just
iterate through all of the bits, printing the index if the bit is turned
I implemented this with Bit::Vector, a C-Perl hybrid module. You can
play with the code, I'll put it up for grabs at http://ua.sez.hellyeah.org/perl/
 Actually, the computer will take a little bit more, to make it
align with the computer's word-byte boundary.
More information about the Pdx-pm-list