During a wholly uncharacteristic bout of clothes tidying, I realised that sock matching was essentially the same problem as limit matching.

Incoming socks are matched against a queue of existing socks; if there are no matches they are added to the queue. When a pair is matched, they are both removed. Additionally, occasionally someone may say, “Hey Edmund… have you seen any of my expensive black dress socks around?”, at which point efficient removal of a sock from the queue is required.

The major difference is that socks aren’t matched using a simple relational operator <. Strictly speaking they are matched by the equality operator =. In the case of chiral socks (where the left and right socks in a pair are different), they would be matched on a pair-wise operator (=,!=) where each sock is represented by a tuple of (type, chirality). In practice, it’s often hard to tell whether two socks are similar enough to form a pair. We could use an approximate matching operator ~. But you can imagine a trio of socks x ~ y ~ z with x !~ z. The present greedy algorithm from the price-time matching engine could lead to suboptimal matches for socks, with a pair of unmatched socks remaining because their partners have eloped earlier in the process.

Looking for optimal matches rather than simple matches almost certainly means using a backtracking or dynamic programming algorithm, not a greedy one. I’ll restrict myself to describing equality matching. The consequence of this is that the bidirectional queue structure (implemented with skip lists) from the price-time engine isn’t necessary. A hash table does the trick: if two socks hash to the same bucket, then check if they match and remove them both.

The other major difference between efficient sock matching and limit matching is the difference in scale. The price-time matching problem has a specified maximum of 65536 outstanding limits in play at any time. But there seems to be no limit to the number of singular socks generated by my laundry…

### Like this:

Like Loading...

*Related*

lol, very nice. ill hook up a web cam and conveyor belt and you can sort my socks.