A forward to maintain relevance to this site: Photos featured in this post were annotated using The GIMP (GNU Image Manipulation Program)
Most everyone has a clothing storage facility, such as a closet, wardrobe furniture or plain rack. The clothing storage, much like any other computer data structure, has an “add” and a “remove” function, with “search” operations. Normally, “add” is when items from finished laundry are put away, and “remove” is when clothing item is summoned for use. “Search” happens when you locate where to “add” or “remove” item.
A more traditional arrangement is what I’ll call the “always categorically” sorted. I used to follow this arrangement, as I believe most people do. Usually this entails dividing the space into a few main “banks”, and then sorting by “type” in each bank. See this representation:
A place for everything and everything in its place.
Now, in most closets I’ve seen, there’s some “specials” such as jackets, vests, suits, that are there but hardly used, a “bottoms” for pants and shorts, and a large “tops” section. For our discussion, we’ll focus on this since this seems to be a consistent majority that tends to be subdivided by sleeve length or material thickness.
Say the Laundry is done and its time to reload the closet. The “Add” algorithm is as such where you have to locate the “bank”, then the “sub type” to insert the item:
PutAwayLaundry( stack* cleanItems, NumberOfItems)
{
cleanIdx=0;
while( cleanIdx < NumberOfItems)
{
//find bank to load
for(bankIdx=0; bankIdx < MAX_BANK; ++bankIdx)
{
if(cleanItems[cleanIdx].bank_type == bank[bankIdx].bank_type)
{ //found the bank to insert
for( subIdx=0; subIdx < bank[bankIdx].MAX_SUBS; ++subIdx)
{ //search each type within bank
if(cleanItems[cleanIdx].type == bank[bankIdx].type[subIdx])
{ //found the type sub-section to load
bank[bankIdx].type[subIdx].
Insert_and_shift_down( cleanItems[cleanIdx] );
break;
}
break;
}
break;
}
}
cleanIdx = cleanIdx + 1;
}
}
The “remove” algorithm is pretty similar: step thru each bank, then each sub_section, then walk through that sub_section to find a particular item.
Analysis: Insertions and removals happen at x banks, and y sub_sections within each bank. Accesses are all over the place.
An alternative that I’ve grown to like is the “cache” model to simplify “add” and “removal” operations. Here’s a representation.
Spoiler alert: always insert at head of bank
The “cache” model shares the same bank[x] top-level arrangement, because it really doesn’t make sense to mix vests, slacks, and shirts in one big mash-up. However notice that the top level is the ONLY dividing criteria. Here’s the “add” algorithm: Locate the matching bank and stuff it in at the front of that bank.
PutAwayLaundry( stack* cleanItems, NumberOfItems)
{
cleanIdx=0;
while( cleanIdx < NumberOfItems)
{
//find bank to load
for(bankIdx=0; bankIdx < MAX_BANK; ++bankIdx)
{
if(cleanItems[cleanIdx].bank_type == bank[bankIdx].bank_type)
{ //found the bank to insert
//insert at head of bank and be done with it.
bank[bankIdx].Insert_and_shift_down( cleanItems[cleanIdx] );
}
}
cleanIdx = cleanIdx + 1;
}
}
The optimization here is that we’ve taken away all the type[y] comparisons (which could be numerous…) and reduced the “add” to insert at the front of one of the 3 banks, and shift the rest down.
What about when you look for a shirt to wear? Start at head of the shirt bank, incrementally search until you find the one you’re looking for. The kickass-ness of the “cache” model is that the one you’re looking for will be typically located within the first 5% of the bank. Think about it: it is summer today and it was summer when you last did laundry within the past week, so a summer appropriate shirt will be where you just loaded it…right in the front. ::Genius::
When the season gradually changes, well the search algorithm takes a slight penalty as you’re walking deeper towards the colder clothing…but only temporally. The winter clothes get washed and get put back..you guessed it, at the front. Which get pulled again…from the front! ::Automatic Sorting::
The cache closet works well. So well that in passing conversation with a co-worker turns out he does the same thing. (it was kinda telling since that on a handful of occasions we’d end up wearing the same color shirt to the office on the same day without any prior coordination).