[Pdx-pm] [SOLUTION] Telephone number sorting

[Tyler F. Creelan]

On Fri, 27 Sep 2002, Joshua Keroes wrote:
> > Q: What's the fastest, most space-efficient way to sort all
> >    of Portland's 503 phone numbers?
> e.g. To indicate that telephone number 555-1234 is in use, turn the
>      5,551,234th bit on.

Just a heads up -

The overhead of packing and unpacking sub-word quantities makes this
approach less efficient than it might appear. Modern architectures have a
large datapath and referencing individual bits will introduce additional
work. This is reflected in how, for example, booleans are represented with
32-bit variables in Java and C++ implementations.

More info:

M. Stephenson and J. Babb and S. Amarasinghe.  Bitwidth Analysis with
Application to Silicon Compilation.  In Proceedings of the SIGPLAN
conference on Programming Language Design and Implementation, Vancouver,
British Columbia, June 2000.


Tyler

-----------------------------
Tyler F. Creelan
College of Engineering
Oregon State University
503-640-3101
-----------------------------


On Fri, 27 Sep 2002, Joshua Keroes wrote:

> > 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. [1]
>
> 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
> on.
>
> 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/
>
> -Joshua
>
> [1] Actually, the computer will take a little bit more, to make it
>     align with the computer's word-byte boundary.
> _______________________________________________
> Pdx-pm-list mailing list
> Pdx-pm-list at mail.pm.org
> http://mail.pm.org/mailman/listinfo/pdx-pm-list
>