5 ms·

For a radix sort on the 8 digit USD serial numbers, it takes 8x more time (the 2 letters can be ignored). That could be halved by radix sorting on pairs of digi

by tromp 2y ago

For a radix sort on the 8 digit USD serial numbers, it takes 8x more time (the 2 letters can be ignored). That could be halved by radix sorting on pairs of digits, but then keeping track of 100 piles instead of 10 probably negates most of the gain. In practice, partial sorting suffices to reduce the serial number search time to a reasonably short amount, e.g. by 4 rounds of radix sorting.

mattmaroon 2y ago
Right, so basically by your ninth time doing this you’d have broken even (ish) on time. He was doing it every day so that’d be a great investment. It also would reduce the possibility of errors greatly I’d think.
- Retric 2y ago
  100k bills doesn’t need an exact sort to be vastly faster. Day one you sort by first digit, then keep sorting matching digits stopping when you have say 20 numbers in a pile. My guess is you break even on day 2 and the first day is only slightly worse.
  - mattmaroon 2y ago
    That’s a good point, each individual sort probably takes only slightly longer than just looking through them for the number. So the actual sorting might not really add much time at all
kragen 2y ago
in a single round of digit-pair radix sorting, you can put 100 piles of ≈1000 bills each into 10×10 cubbyholes, a piece of furniture which is small enough to fit on a desk. then you need about 20 minutes to linearly search through one such pile when the dj announces a number, which is probably fast enough to win if you have a second cubbyhole array, when you linearly search through a pile chosen from the first cubbyhole array, you can radix-sort that pile by another two digits, dividing it into piles of ≈10 bills. those piles are small enough that you can keep them sorted as you build them without much loss of efficiency, even on a computer if you can fill the first array with 100 wallets with 10 numbered tabs each, like the tabbed dividers in a looseleaf notebook, you can divide the bills into 1000 piles on the first radix-sorting pass. in practice it might be too much work to find or make the wallets but i think the sad thing about michael larson's story is not that he didn't know enough about computer 'science' (or, i guess, library 'science'), but that he spent more effort searching for a hack that would make hard things easy than it would have taken to do them the hard way, destroying his personal relationships in the process

by tromp 2y ago

mattmaroon 2y ago

Right, so basically by your ninth time doing this you’d have broken even (ish) on time. He was doing it every day so that’d be a great investment. It also would reduce the possibility of errors greatly I’d think.

Retric 2y ago
100k bills doesn’t need an exact sort to be vastly faster. Day one you sort by first digit, then keep sorting matching digits stopping when you have say 20 numbers in a pile. My guess is you break even on day 2 and the first day is only slightly worse.
- mattmaroon 2y ago
  That’s a good point, each individual sort probably takes only slightly longer than just looking through them for the number. So the actual sorting might not really add much time at all

kragen 2y ago

in a single round of digit-pair radix sorting, you can put 100 piles of ≈1000 bills each into 10×10 cubbyholes, a piece of furniture which is small enough to fit on a desk. then you need about 20 minutes to linearly search through one such pile when the dj announces a number, which is probably fast enough to win if you have a second cubbyhole array, when you linearly search through a pile chosen from the first cubbyhole array, you can radix-sort that pile by another two digits, dividing it into piles of ≈10 bills. those piles are small enough that you can keep them sorted as you build them without much loss of efficiency, even on a computer if you can fill the first array with 100 wallets with 10 numbered tabs each, like the tabbed dividers in a looseleaf notebook, you can divide the bills into 1000 piles on the first radix-sorting pass. in practice it might be too much work to find or make the wallets but i think the sad thing about michael larson's story is not that he didn't know enough about computer 'science' (or, i guess, library 'science'), but that he spent more effort searching for a hack that would make hard things easy than it would have taken to do them the hard way, destroying his personal relationships in the process