Fast, Heuristic Disk Search

Warning! Some information on this page is older than 3 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

23:00
Wed
04
Jan 2012

Fast, Heuristic Disk Search

In March 2007 I've written an algorithm which I called "Fast, heuristic disk search" and published it in my article Szybkie, heurystyczne przeszukiwanie dysku (in Polish) on codeguru.pl. Today I went back to it, improved it a bit and I think it is a good opportunity to present it once again, this time in English :)

The problem is about searching hard disk, looking for a file or directory with particular name. Naive approach, which is used by file searching functions in programs like Total Commander, uses depth-first search, so it enters C:\, then C:\Program Files, then C:\Program Files\Adobe etc., spending lots of time in places where it probably won't find the file we are looking for.

Game developers know that searching algorithm can be significantly improved by using some heuristics that will drive algorithm towards (probably) right direction. We do it in A* pathfinding. Does a similar principle could be used also when searching for a file?

My particular problem was configuring a program with path to a console tool, let's say fxc.exe shader compiler from DirectX SDK. We could present a textbox where user has to enter path to this tool. We could also make "Browse" button with an open file dialog to simplify locating it. But wouldn't be great if program tried to locate it automatically on first run? Some installed programs store path in a registry key, but if it doesn't, we have no idea where could it be if we don't look for it among files and directories on hard disk.

My algorithm tries to locate given file or directory in given time limit by searching all given directories and their subdirectories. The improvement I propose here is inteligent management of the order in which we process these directories.

The algorithm uses two collections: a queue of directories to process and a set of already visisted directories. Here is the code in C#:

/* Intelligent search for a file or directory by name, on the hard disk.
 * Can throw exceptions on some errors, while silently ignore other.
 * 
 * targetName - name of the target like "fxc.exe" or path suffix like @"bin\x86\fxc.exe".
 * interestingDirNames - case-insensitive strings with parts of
 *     directory names that make these directories particularly
 *     interesting, while not very common.
 *     Example: { "microsoft", "dx", "directx", "sdk" }
 * startDirs - paths to directories to start search from. For example,
 *     path to Program Files or hard disk root directories.
 *     
 * Returns path to found target or null if not found in given time.
 */
public static string IntelligentSearch(
  string targetName, bool targetIsDirectory,
  string[] interestingDirNames, string[] startDirs, TimeSpan timeout)
{
  DateTime endTime = DateTime.Now + timeout;

  // Paths to process
  LinkedList<string> PathQueue = new LinkedList<string>();
  // Path already processed in form Key=Path, Value="1"
  System.Collections.Specialized.StringDictionary Processed =
    new System.Collections.Specialized.StringDictionary();

  foreach (string startDir in startDirs)
    PathQueue.AddLast(startDir);

  // Processing loop - berform breadth first search (BFS) algorithm
  while (PathQueue.Count > 0)
  {
    // Get directory to process
    string Dir = PathQueue.First.Value;
    PathQueue.RemoveFirst();
    // Already processed
    if (Processed.ContainsKey(Dir))
      continue;
    // Add to processed
    Processed.Add(Dir, "1");

    try
    {
      string targetPath = Path.Combine(Dir, targetName);
      if (targetIsDirectory)
      {
        if (Directory.Exists(targetPath))
          return targetPath;
      }
      else
      {
        if (File.Exists(targetPath))
          return targetPath;
      }

      foreach (string SubDir in Directory.GetDirectories(Dir))
      {
        bool dirIsInteresting = false;
        if (interestingDirNames != null && interestingDirNames.Length > 0)
        {
          string subDirName = Path.GetFileName(SubDir);
          foreach (string interestingName in interestingDirNames)
          {
            if (subDirName.IndexOf(interestingName, StringComparison.InvariantCultureIgnoreCase) != -1)
            {
              dirIsInteresting = true;
              break;
            }
          }
        }

        if (dirIsInteresting)
          PathQueue.AddFirst(SubDir);
        else
          PathQueue.AddLast(SubDir);
      }
    }
    catch (Exception) { }

    if (DateTime.Now > endTime)
      return null;
  }

  return null;
}

Example usage, which finds my fxc.exe in a fraction of a second:

string[] interestingDirNames = {
  "microsoft",
  "dx",
  "directx",
  "sdk",
  "utilities",
  "bin",
  "x86" };

List<string> startDirs = new List<string>();

startDirs.Add(Environment.GetFolderPath(Environment.SpecialFolder.ProgramFiles));

foreach (System.IO.DriveInfo Drive in System.IO.DriveInfo.GetDrives())
  if (Drive.DriveType == System.IO.DriveType.Fixed)
    startDirs.Add(Drive.RootDirectory.Name);

string result = Globals.IntelligentSearch(
  "fxc.exe",
  false,
  interestingDirNames,
  startDirs.ToArray(),
  TimeSpan.FromMilliseconds(5000.0));

Comments (1) | Tags: algorithms .net | Author: Adam Sawicki | Share

Comments

aaa
2015-04-10 09:23:43
chanel bags, http://www.chanelhandbags.net.co/
flat iron, http://www.chiflatiron.net.co/
converse shoes, http://www.converse.net.co/
ferragamo outlet, http://www.ferragamo.com.co/
gucci belt, http://www.guccihandbags.com.co/
hollister kids, http://www.hollister.us.org/
insanity workout calendar, http://www.insanityworkout.net.co/
jimmy choo shoes, http://www.jimmychoo.net.co/
air jordan shoes, http://www.jordan-shoes.com.co/
juicy couture, http://www.juicycouture.com.co/
juicy couture outlet, http://www.juicycoutureoutlet.net.co/
kate spade, http://www.kate-spade.com.co/
katespade, http://www.katespade-outlet.com.co/
louis vuitton outlet, http://www.louisvuitton-outlet.com.co/
michael kors outlet online, http://www.michael-kors.us.org/
michael kors, http://www.michael-kors-handbags.us.com/
michael kors purses, http://www.michael-kors-outlet.us.org/
michael kors, http://www.michael-kors-outlet-online.us.org/
michael kors outlet online sale, http://www.michaelkorsoutletonline-sale.us.com/
north face jackets, http://www.northface.us.org/
oakley outlet, http://www.oakley-sunglasses.us.org/
pandora charms, http://www.pandorajewelry.com.co/
prada outlet, http://www.pradahandbags.com.co/
prada shoes for men, http://www.pradashoes.com.co/
ray-ban, http://www.ray-ban-outlet.us.com/
ray ban sunglasses outlet, http://www.rayban-sunglasses.us.org/
rolex watches, http://www.replicawatches.us.com/
swarovski outlet, http://www.swarovskicrystal.com.co/
the north face outlet, http://www.thenorthface.us.org/
tiffany jewelry, http://www.tiffanyandco.net.co/
tiffany co, http://www.tiffanyjewelry.us.org/
true religion jeans outlet, http://www.true-religion.com.co/
true religion outlet, http://www.truereligionjeans.net.co/
ugg boots, http://www.uggaustralia.net.co/
uggs outlet, http://www.uggboots.net.co/
ugg australia, http://www.uggbootsclearance.com.co/
ugg, http://www.uggsonsale.com.co/
ugg boots clearance, http://www.uggsoutlet.com.co/
cheap oakley, http://www.cheap-oakleysunglasses.in.net/
oakley vault, http://www.oakleysunglassescheap.in.net/
ralph lauren outlet online, http://www.ralphlaurenoutletonline.in.net/
ralph lauren outlet, http://www.ralphlauren--outlet.in.net/
burberry.com, http://www.burberryoutlet--online.in.net/
toms shoes, http://www.tomshoes.in.net/
toms outlet, http://www.toms-outlet.in.net/
christian louboutin shoes, http://www.christianlouboutin.in.net/
tory burch handbags, http://www.tory-burch-outlet.in.net/
gucci belt, http://www.gucci-outlet.in.net/
longchamp bags, http://www.longchamphandbagsoutlet.in.net/
abercrombie.com, http://www.abercrombie-kids.in.net/
hollister, http://www.hollisterclothing-store.in.net/
hermes birkin bag, http://www.hermes.in.net/
cheap nfl jerseys, http://www.cheapjerseys.in.net/
beats headphones, http://www.beats-by-dre.in.net/
beats by dr dre, http://www.beatsheadphones.in.net/
hair straightener, http://www.ghdhairstraightener.in.net/
ray ban sunglasses, http://www.rayban-sunglasses.org.uk/
michael kors bags, http://www.michaelkors-uk.org.uk/
michael kors uk, http://www.michaelkorshandbags.org.uk/
louis vuitton outlet, http://www.louis--vuitton.org.uk/
ralph lauren outlet, http://www.ralphlauren-outlet.org.uk/
nike running, http://www.nikefree-run.org.uk/
omega watches, http://www.rolex-watches.me.uk/
dresses for weddings, http://www.weddingdressesuk.org.uk/
pandora sale, http://www.pandora-charms.org.uk/
thomas sabo, http://www.thomassabo-uk.org.uk/
swarovski, http://www.swarovski-uk.org.uk/
christian louboutin, http://www.christianlouboutin.org.uk/
air huarache, http://www.air-huarache.co.uk/
roshe run, http://www.rosherun.org.uk/
north face uk, http://www.thenorth-face.org.uk/
louis vuitton canada, http://www.louis--vuitton.ca/
jordan shoes, http://www.airjordans.us/
air jordan, http://www.jordanretro.org/
air jordan retro, http://www.cheap-jordans.net/
nike outlet, http://www.nikefactory.org/
cheap nike shoes, http://www.nikestore.us/
nike sneakers, http://www.cheap-nikeshoes.com/
air max 2015, http://www.nike-air-max.us/
nike air max 2014, http://www.airmax-2015.org/
nike air max 2015, http://www.airmax-90.org/
nike free, http://www.nikefree-run.net/
nike running shoes, http://www.nikefree5.net/
supra shoes, http://www.suprashoe.net/
new balance, http://www.newbalance-outlet.org/
mont blanc, http://www.montblanc--pens.net/
salvatore ferragamo outlet, http://www.ferragamoshoes.net/
mcm bags, http://www.mcm-bags.net/
bottega, http://www.bottega.us/
nike mercurial, http://www.nikemercurial.net/
celine bags, http://www.celinebags.org/
roshe runs, http://www.rosheruns.us/
roshe run, http://www.nikerosherun.us/
vans shoes, http://www.vansshoes.us/
timberland outlet, http://www.timberland-shoes.com/
iphone 4s cases, http://www.iphone-cases.us/
softball bats, http://www.softball-bats.us/
babyliss pro, http://www.babyliss-pro.net/
louis vuitton handbags, http://www.louisvuitton-outlets.us/
burberry outlet, http://www.burberry-outlet.jp.net/
louboutin, http://www.louboutin.jp.net/
christian louboutin shoes, http://www.christianlouboutinshoes.jp.net/
louis vuitton outlet stores, http://www.louisvuitton.jp.net/
prada outlet, http://www.official-pradaoutlet.com/
michael kors outlet online sale, http://www.michaelkorsclance.com/
michael kors handbags, http://www.official-michaelkorsonline.com/
tommy hilfiger polos, http://www.tommyhilfiger.in.net/
mcm handbags, http://www.mcmworldwide.ca/
moncler outlet, http://www.mmoncler-outlet.com/
kate spade sale, http://www.kate-spades.com/
barbour quilted jacket, http://www.barbour-factory.com/
salvatore ferragamo shoes, http://www.ferragamos.in.net/
canada goose outlet, http://www.canada-gooser.com/
louis vuitton outlet online, http://www.louisvuittonas.com/
burberry outlet, http://www.burberry-outlet2015.com/
hollister clothes, http://www.fashion-clothing.us.com/
north face outlet online, http://www.thenorthface.so/
barbour jackets, http://www.barbour-jacketsoutlet.com/
north face jackets outlet, http://www.northfaceoutlet.in.net/
north face jackets women, http://www.northclearance.com/
burberry, http://www.burberrysfactory.com/
polo ralph lauren outlet online, http://www.ralph-laurenuk.com/
ralph lauren outlet, http://www.polo-outlets.com/
ralph lauren outlet online, http://www.ralphlaurenr.com/
beats by dre outlet, http://www.monsterbeatsbydres.net/
louis vuitton outlet online, http://www.louis-vuittonblackfriday.com/
gucci outlet, http://www.lv-guccishoesfactory.com/
longchamp outlet, http://www.longchampsoutlet.com/
moncler clearance, http://www.moncler-clearance.com/
ralph lauren shirts, http://www.ralphlaurentshirts.com/
hermes handbags, http://www.usahanbags.com/
beats by dre outlet, http://www.beatsbydreoutlet.net/
coach factory outlet online, http://www.coach-blackfriday2014.com/
coachfactory.com/shop, http://www.coachccoachoutlet.com/
coachoutlet.com, http://www.coach-clearance.com/
michael kors outlet, http://www.michaelkors.in.net/
coachfactory.com, http://www.coach-factories.net/
oakley vault, http://www.oakley.so/
hermes bags, http://www.hermes-outletonline.com/
marc jacobs bags sale, http://www.marcjacobsonsale.com/
nike air max, http://www.nike-jordanshoes.com/
woolrich clearance, http://www.woolrich-clearance.com/
coach outlet store, http://www.coachoutletew.com/
coach bags outlet, http://www.coachoutlet.so/
coach handbags outlet, http://www.coachoutletstates.com/
gucci sale, http://www.guccishoes-uk.com/
coach outlet online, http://www.official-coachoutlets.com/
michael kors outlet store, http://www.michaelkors.so/
gucci handbags, http://www.guccifactorys.com/
the north face outlet, http://www.thenorthface.in.net/
ugg boots clearance, http://www.cheapuggboots.eu.com/
tommy hilfiger coupons, http://www.tommy-hilfigeroutlet.com/
uggs outlet, http://www.uggboots.so/
louis vuitton outlet, http://www.louisvuitton.so/
calvin kleins outlet, http://www.calvin-kleins.com/
christian louboutin, http://www.cheap-christianlouboutinshoes.com/
jordan retro, http://www.airjordanshoes2015.com/
burberry outlet, http://www.burberry.eu.com/
abercrombie fitch, http://www.abercrombiee.com/

Post comment

Nick *
Your name or nickname
E-mail
Your contact information (optional, will not be shown)
Text *
Content of your comment
Calculate *
(* - required field)
STAT NO AD [Stat] [Admin] [STAT NO AD] [pub] [Mirror] Copyright © 2004-2016 Adam Sawicki
Copyright © 2004-2016 Adam Sawicki