When I fold laundry, I pair up matching socks.  Usually I put matching pairs of socks 
into the washing machine, then take a lot of individual socks out of the dryer; then, 
during folding, I recreate the pairs from a stream of individual socks by the 
following method.  I maintain an "unpaired sock buffer", usually on my leg, which is 
initially empty.  Then, for each sock in the sequence, I do a sequential search 
through this buffer for its mate.  If I find the mate, I remove it from the buffer and 
form a pair; if I do not, I add the new sock to the buffer.

When the number of socks remains small, this works well; but it's slow for a large 
load of laundry; the average size of the buffer gets larger (I suspect it's 
proportional to the total number of socks) and so processing each sock takes longer.  
Other possible methods exist; for example, you could limit the sock buffer size and 
put overflow socks (either from the sequence or, to guard against stray single socks, 
from the sock buffer) into an overflow pile, which you'd process after the initial 
sock sequence; or you could sort the sequence into subsequences by some attribute such 
as color.

The worst case for this problem is to compare every sock against every other sock.  
The worst case for the naive sock-buffer method isn't that bad; it happens when the 
sock sequence is palindromic.  Here, you need only compare to half the other socks at 
most, and a quarter of them on average, which is four times better than the worst 
case.  I wonder if other methods that take into account only equality of socks can do 
better.  (Clearly, once you categorize socks by color, size, cut, and other 
attributes, you can use any of a variety of O(N lg N) sorting algorithms.  Radix 
sorting with a radix around 5-10 seems to work best for me, beating out 
comparison-based schemes by a factor of five or so.)

Reply via email to