empirical algorithms

July 29th, 2006

If you're one of those people thinking "there isn't enough computer science in this blog", today's entry is for you. We deal in applied computer science.

As I was on my way to the supermarket, I was thinking about an algorithm for a coding project I'm working on. Just as I arrived, it struck me: shopping is an M:N problem. It is isn't it? When you're at home thinking "I need to get some food in here", you make a list of things to buy in your mind. Then you arrive at the store and you have your list, but you're confronted with a longer list - the list of things in the store. So as you go from to display to display, you have an option of two fundamental algorithms:

  • for each item in the display, compare to everything on shopping list
  • for each item on shopping list, compare to all items in the store

And whichever you choose, you have to loop that around the other list, so it's a heavy computation. In reality, our methods are somewhat more refined, we associate milk in the diary section with milk on the shopping list without having to compare it with all the other items. But memory remains a problem. How many items can you remember when you go shopping? For me it's about 5-6, anymore and I get very error prone.

Another way to shop is just not make a list at all, just go in the store and for every item, run a heuristic to estimate the need for this particular item at home. The heuristic will accept as arguments many different things, like:

  • current price vs average price for this item
  • the existing supply of this at home
  • the need for this in the first place
  • the craving for this item, if any

So you see, fundamentally, it's a complex system. No wonder amateurs can find it daunting.

:: random entries in this category ::