A Cheap Trick for quadratic loops

The other day I blogged about the perils of a hash value-related filter that exhibits quadratic time. Sometimes there's a hack you can use to make the simplicity of a quadratic nested loop a bit more palatable, performance-wise. Here's a script I wrote a couple of weeks ago to give me the unique list of folders containing selected files:

class MainClass {
  void Main(CaseClass c) {
    if (c) {
      EntryClass root = c.EntryRoot();
      NameListClass list();
      String folder,
             last;
      forall (EntryClass e in root) {
        if (!e.IsFolder() && e.IsSelected()) {
          folder = e.FullPath().GetFilePath();
          if (last != folder && !list.Find(folder)) {
            new NameListClass(list, folder);
          }
          last = folder;
        }
      }
      foreach (NameListClass f in list) {
        Console.WriteLine(f.Name());
      }
    }
  }
}

This code uses a flat NameListClass for keeping a unique list of the folders and NameListClass::Find() does a sequential scan of the list. But, it still runs in a reasonable time.

The trick is that the script remembers the folder of the last previous entry. Chances are the current entry is in the same folder, so the script doesn't need to scan the list. In general, when you're looping over a tree with forall(), there's probably an ordering principle to the data in the tree. It's easy to cache a variable or two from the last item processed, and it can save yourself a lot of work. If the cache misses, then, yes, your code is slow... but it's also simple and fast to write. Obviously it's not appropriate for every situation, but it's a good trick to keep in mind.