Wstęp

Artykuł prezentuje algorytm, który przeszukując katalogi dysku twardego użytkownika pozwala odnaleźć potrzebny plik w czasie wielokrotnie krótszym, niż podczas tradycyjnego, rekurencyjnego przeszukiwania dysków dzięki zastosowaniu prostej heurystyki i wiedzy o konkretnym problemie.

Problem

W dobie powszechnego dostępu do Internetu wyszukiwanie stało się bardzo ważne. Jednak zanim jeszcze narodziło się Google, użytkownicy przeszukiwali swoje dyski w poszukiwaniu zagubionych plików i katalogów. Każdy ma czasem taką potrzebę, nawet jeśli utrzymuje w swoim komputerze porządek. Tradycyjnie wymaga to przejrzenia rekurencyjnie wszystkich katalogów na dysku w poszukiwaniu pliku o nazwie pasującej do podanego wzorca. To z kolei zabiera sporo czasu. Wydajność takiego procesu mogą wspomóc mechanizmy indeksowania.

Istnieje jednak także inny problem wyszukiwania, który może zrodzić się podczas pisania aplikacji użytkowej. Aby go zrozumieć, wyobraź sobie następującą sytuację: Istnieje kompilator używany przez wielu programistów. Dla przykładu niech będzie to kryjący się w pliku fxc.exe Microsoft D3DX9 Shader Compiler służący programistom gier do kompilowania kodu tzw. shaderów, a dołączany do pakietu DirectX SDK. Jego mankamentem jest fakt, że stanowi on narzędzie konsolowe - wymaga uruchamiania z poziomu wiersza poleceń i podania odpowiednich parametrów, w tym nazw plików wejściowych i wyjściowych wraz z pełnymi ścieżkami. Oczywiście, jest to niewygodne - tym bardziej, że jak wykazuje praktyka, bardziej zaawansowani programiści gier kompilują wiele shaderów na raz bądź jeden kod źródłowy z różnymi opcjami kompilacji. Dostrzegasz tutaj dla siebie szansę na napisanie ciekawego programu, którego jeszcze nie ma a bardzo by się przydał - nakładki graficznej pozwalającej uruchamiać ten kompilator z poziomu aplikacji okienkowej, a może nawet całego IDE (środowiska programistycznego) do pisania i kompilowania shaderów. Postanawiasz zrealizować swój plan.

Jednym z elementów takiego przykładowego programu - może nie najistotniejszym, ale na pewno niezbędnym - jest uruchamianie z jego poziomu wspomnianego kompilatora oraz przechwytywanie tekstu generowanego na jego konsolowym wyjściu. Aby to zrobić, trzeba znać lokalizację tego kompilatora. Jak ją poznać?

Oczywistym rozwiązaniem byłoby nakazanie użytkownikowi, aby w opcjach twojego programu ustawił prawidłową ścieżkę do lokalizacji, w której ma zainstalowany pakiet DirectX SDK zawierający potrzebny kompilator. Taką funkcję na pewno trzeba zaimplementować, ale dlaczego nie spróbować też zlokalizować go samemu? W końcu programy powinny być jak najbardziej proste, intuicyjne i gotowe do działania bez zbędnej konfiguracji. Jak automatycznie znaleźć ten plik?

Wspaniale byłoby, gdyby ścieżka instalacyjna pakietu, którego poszukujemy była zapisana gdzieś w stałym miejscu w rejestrze systemowym. To proste podejście często okazuje się skuteczne, ale niestety nie każdy program pozostawia po sobie wyraźny ślad w rejestrze. Niektóre zwyczajnie nie zapisują do niego żadnych informacji (a przynajmniej nie przechowują tam swojej ścieżki). Cóż wtedy pozostaje?

Można przeszukać dysk w poszukiwaniu tego pliku. Jednak czy użytkownik zgodzi się na kilkuminutowe oczekiwanie i wpatrywanie się w jakiś pasek postępu pokazujący kolejne skanowane katalogi swojego dysku zamiast ręcznie wpisać potrzebną ścieżkę? Raczej nie. Rozwiązanie, które proponuję w tym artykule pomaga zlokalizować potrzebny plik metodą systematycznego przeszukiwania dysku, ale dzięki zastosowaniu odpowiedniej heurystyki znacznie przyspiesza ten proces dając duże szanse na jego odnalezienie w ciągu ułamka sekundy.

Algorytm

Kiedy poszukujemy na dysku pliku o konkretnej nazwie, nie mamy żadnych wskazówek co do jego lokalizacji. Plik ten może się kryć gdziekolwiek i należy przeszukać wszystkie zakamarki dysku twardego. Jednak czy na pewno nie można w żaden sposób poprawić naszej sytuacji?

Zastanówmy się najpierw nad kolejnością, w jakiej przeszukiwalibyśmy dysk w najprostszym podejściu. Byłaby to zapewne funkcja rekurencyjna, która dla podanego katalogu wylistowałaby wszystkie podkatalogi i dla każdego z nich wywołałaby samą siebie. Takie podejście nazywane jest w algorytmice metodą DFS - Depth-First Search, co oznacza przeszukiwanie wgłąb.

Zastanówmy się teraz, jakie konsekwencje ma takie podejście dla szybkości, z jaką mamy szansę znaleźć poszukiwany plik. Nasz prosty algorytm rozpocznie poszukiwania zapewne od katalogu głównego dysku C:\, po czym pobierze listę leżących w nim katalogów i rozpocznie przeszukiwanie pierwszego z nich. Jeśli będzie to akurat katalog Documents and Settings, zacznie z kolei przeszukiwać jego zawartość, a więc podkatalogi takie jak na przykład Moje dokumenty, Menu Start czy Dane aplikacji. To jest bardzo wiele katalogów, pośród których prawie na pewno nie znajdzie się poszukiwany plik - w końcu kto instaluje programy do katalogu Moje dokumenty?

Do czego zmierzam? Nie chodzi o to, by całkowicie pominąć ten katalog z naszych poszukiwań. Ktoś jednak mógł zdecydować się właśnie tam umieścić zainstalowany DirectX SDK. Dobrym pomysłem może się natomiast okazać zastanowienie się nad kolejnością, w jakiej przeszukiwane są katalogi. Bardziej prawdopodobne jest, że użytkownik zainstalował pakiet wraz z poszukiwanym przez nas plikiem gdzieś w katalogu głównym dysku C:\, D:\ bądź też w katalogu C:\Program Files albo nawet własnym D:\Programiki, niż że zrobił to w jakimś głęboko zagnieżdżonym katalogu, niezależnie czy miałby to być C:\Documents and Settings\Zbigniew\Moje dokumenty, czy też D:\ Stare\Nowe\Śmieci\XXX\Moje programy.

Dlatego pierwszym usprawnieniem, które proponuje, jest zmiana algorytmu na przeszukiwanie wszerz - BFS - Breadth-First Search. Polega ono na tym, by najpierw przejrzeć zawartość wszystkich katalogów pierwszego poziomu (czyli katalogu głównego C:\, D:\ itd.), następnie wszystkich katalogów drugiego poziomu (np. C:\Program files, C:\Documents and Settings itd.), a dopiero potem katalogów trzeciego poziomu (np. C:\Program files\Microsoft Office, C:\Documents and Settings\Zbigniew) itd. To znacznie zwiększy szanse na szybsze znalezienie poszukiwanego pliku.

Drugie usprawnienie, które proponuję to dalsze wykorzystanie wiedzy na temat możliwych lokalizacji obiektu naszych zainteresowań. Chodzi o katalog, w którym prawdopodobnie zainstalowany będzie pakiet. Domyślnie proponowanym katalogiem instalacyjnym jest w przypadku omawianego przykładu C:\Program files\DXSDK. To daje nam wskazówkę, by priorytetowo potraktować katalog C:\Program files i przeszukać go jako pierwszy.

Jeszcze jedną wskazówką jest wykorzystanie nazw katalogów, które z dużym prawdopodobieństwem doprowadzą nas do celu naszych poszukiwań. Są to po pierwsze, podkatalogi w ramach pakietu SDK w których leży interesujący nas plik. W naszym przykładowym problemie z kompilatorem shaderów, jego lokalizacja to zawsze podkatalog Utilities\Bin\x86\fxc.exe. Po drugie natomiast, są to nazwy pod którymi użytkownik mógł zainstalować pakiet DirectX SDK. Zamiast wpisać tu na sztywno domyślnie proponowaną nazwę DXSDK, proponuję ustalić fragmenty łańcuchów - wszelkie prawdopodobne nazwy które może nadać użytkownik - np. directx, dx, sdk, microsoft.

Przygotowania

Do implementacji użyjemy języka C#. W celu zaimplementowania opisanego algorytmu potrzebujemy przede wszystkim wiedzieć, jak przeszukuje się katalogi. Na szczęście w .NET-cie jest to bardzo proste. Metody statyczne klasy Directory pozwalają pobrać tablicę łańcuchów z nazwami plików lub podkatalogów leżących w podanym katalogu - wszystkich lub tylko pasujących do podanej maski, zależnie od przeciążonej wersji metody:

public static string[] GetFiles (string path)
public static string[] GetFiles (string path, string searchPattern)
public static string[] GetDirectories (string path)
public static string[] GetDirectories (string path, string searchPattern)

Na maskę searchPattern składa się nazwa pliku bądź katalogu mogąca zawierać znaki wieloznaczne (ang. wildcards): pytajnik ? oznaczający dowolny jeden znak oraz gwiazdka * oznaczająca dowolną ilość (także 0) dowolnych znaków.

By być w pełni przygotowanym do implementacji, przyda nam się jeszcze wiedza na temat tego, jak pobrać katalog Program Files (on wcale nie musi leżeć zawsze w tym samym miejscu na dysku - da się to zmienić!) oraz jak wylistować wszystkie napędy dyskowe w systemie (ale tylko dyski twarde! - nie chcemy przeszukiwać napędów dyskietek, CD, DVD ani pamięci Flash). Do tego pierwszego służy następujące wywołanie:

DIR = Environment.GetFolderPath(Environment.SpecialFolder.ProgramFiles);

Pobrania listy napędów dyskowych dokona natomiast następujący kod:

foreach (DriveInfo Drive in DriveInfo.GetDrives())
   if (Drive.DriveType == DriveType.Fixed)
      DO_SOMETHING(Drive.RootDirectory.Name);

Drugą rzeczą, jaką potrzebujemy do implementacji jest obmyślenie sposobu, w jaki zrealizujemy zaprojektowany wyżej algorytm. Nie trzeba być laureatem olimpiady informatycznej, żeby wpaść na pomysł wykorzystania do przeszukiwania wszerz kolejki. Kolejne katalogi i podkatalogi przeznaczone do przeszukiwania będą dodawane na koniec kolejki, a kolejny katalog do przetworzenia będzie zawsze pobierany z jej początku. To zapewni odpowiednią kolejność przetwarzania, taką jak opisana wyżej.

Dodatkowo okazuje się, że tą samą kolejkę możemy wykorzystać do zrealizowania naszego planu przeszukiwania w pierwszej kolejności katalogów, które ze względu na swoją nazwę są dla nas szczególnie interesujące, bo rokują duże nadzieje na ukierunkowanie nas we właściwe miejsce. Wystarczy jedynie dodawać takie katalogi na początek zamiast na koniec kolejki, by zostały obsłużone natychmiast po bieżącym, a nie dopiero po obsłużeniu wszystkich oczekujących już w kolejce. To zaburza co prawda algorytm BFS, ale cóż... tak to w życiu bywa - teoria sobie, a praktyka sobie.

Kolejka musi być sekwencją łańcuchów, do której chcemy możliwie szybko dodawać i usuwać elementy zarówno na początku, jak i na końcu. Stąd moja propozycja użycia w tym celu klasy kolekcji listy łączonej - System.Collections.Generic.LinkedList<string>.

Będziemy potrzebowali funkcji, która dla podanej ścieżki stwierdzi, czy katalog umieszczony na jej końcu jest ze względu na swoją nazwę szczególnie interesujący. Możemy ją nazwać funkcją heurystyczną. Heurystyka to takie mądre słowo, które w informatyce oznacza metodę nie dającą zawsze 100% gwarancji na najlepsze czy najszybsze znalezienie rozwiązania, ale dobrze sprawdzającą się w praktyce - która na podstawie pewnych wskazówek może ukierunkować nas na rozwiązanie i tym samym zwiększa prawdopodobieństwo jego znalezienia. Heurystykę stosuje się wszędzie tam, gdzie czysto teoretyczne wyliczenie optymalnego rozwiązania jest niemożliwe bądź zbyt kosztowne obliczeniowo (np. gra w szachy albo znajdowanie najkrótszej drogi). To wszystko brzmi groźnie, ale w naszym przypadku jest bardzo proste. Oto wspomniana funkcja:

private static bool DirectoryIsInteresting(string DirName)
{
    int Pos = DirName.LastIndexOf('\\');
    if (Pos > -1 && Pos < DirName.Length-1)
        DirName = DirName.Substring(Pos + 1);
    DirName = DirName.ToLower();

    if (DirName.Contains("dx")) return true;
    if (DirName.Contains("directx")) return true;
    if (DirName.Contains("sdk")) return true;
    if (DirName.Contains("microsoft")) return true;
    
    if (DirName.Contains("utilities")) return true;
    if (DirName.Contains("bin")) return true;
    if (DirName.Contains("x86")) return true;

    return false;
}

Zanim przystąpimy do przyjrzenia się głównej funkcji naszego algorytmu, musimy rozwiązać jeszcze jeden problem. Czy wiesz już, jaki? Jeśli na podstawie powyższych opisów domyśliłeś się, jaki błąd tkwi w proponowanym podejściu, gratuluję spostrzegawczości. Jeśli nie, to nic nie szkodzi - już spieszę z wyjaśnieniem. Chodzi o uniknięcie sytuacji, kiedy ten sam katalog będzie przeglądany po raz drugi. Taka sytuacja może się zdarzyć i na pewno zdarzy się, jeśli temu nie zapobiegniemy. Dlaczego?

Załóżmy dla przykładu, że do naszej kolejki dodajemy kolejno katalogi: C:\Program Files, C:\, D:\. Przeszukujemy ich zawartość dodając znalezione w nich podkatalogi na koniec kolejki. Teraz po przetworzeniu tych trzech pierwszych pozycji w kolejce znajdą się katalogi takie jak: pochodzące z C:\Program Files: Common Files, Messenger, Microsoft Office, MSN itd., pochodzące z C:\: Documents and Settings, Windows oraz... Program Files! W ten sposób katalog Program Files zostanie po raz drugi dodany do kolejki katalogów przeznaczonych do przeszukania. Jak temu zapobiec?

Musimy niestety zapamiętać wszystkie katalogi, które już przeszukaliśmy, aby nie dodać ich do kolejki po raz drugi. Potrzebujemy do tego kolekcji, która ma następujące własności: pamiętając zbiór łańcuchów nie musi zachowywać ich kolejności, musi za to szybko sprawdzać, czy dany łańcuch należy do tego zbioru. Kolekcję taką odnajdziemy na przykład w bibliotece standardowej C++ w postaci klasy std::set. Niestety w .NET Framework nie ma jej odpowiednika, dlatego skorzystamy z klasy System.Collections.Specialized.StringDictionary. Ta kolekcja przechowuje zbiór par łańcuchów klucz-wartość i pozwala je szybko wyszukiwać. My jako klucze użyjemy ścieżek do przetworzonych już katalogów, a jako wartość, nieużyteczną dla nas w tym przypadku, wpiszemy dowolny stały łańcuch.

Implementacja

Tak wygląda główna metoda realizująca omawiany w tym artykule algorytm:

public static string TryLocateFxc()
{
    try
    {
         long EndTime = DateTime.Now.Ticks + MAX_LOCATE_TIME;

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

         // Add default paths
         // - Program files
            PathQueue.AddLast(Environment.GetFolderPath(Environment.SpecialFolder.ProgramFiles));
         // - Hard disks
         foreach (DriveInfo Drive in DriveInfo.GetDrives())
             if (Drive.DriveType == DriveType.Fixed)
                 PathQueue.AddLast(Drive.RootDirectory.Name);

         // Processing loop - perform 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");

             //System.Diagnostics.Debug.WriteLine("Processing: " + Dir);

             try
             {
                 // Look for fxc.exe file
                 string[] FxcFiles = Directory.GetFiles(Dir, "fxc.exe");
                 if (FxcFiles.Length > 0)
                     return FxcFiles[0];

                 // Look for subdirectories
                 foreach (string SubDir in Directory.GetDirectories(Dir))
                 {
                     // Interesting directory - add at the beginning of the queue
                     if (DirectoryIsInteresting(SubDir))
                         PathQueue.AddFirst(SubDir);
                     // Not interesting - add at the end of the queue
                     else
                         PathQueue.AddLast(SubDir);
                 }
             }
             catch (Exception ) { }

             // Time out
             if (DateTime.Now.Ticks >= EndTime)
                 return "";
         }
         
         // Not found
         return "";
    }
    catch (Exception )
    {
        return "";
    }
}

Po przeczytaniu wcześniejszego opisu zaprezentowany kod powinien być jasny. Dodatkowo zastosowałem w nim pewne mechanizmy, które wynikają z idei działania tej funkcji. Ma ona, jak jej nazwa wskazuje, spróbować zlokalizować przykładowy poszukiwany przez nas plik fxc.exe i zwrócić jako rezultat łańcuch z pełną ścieżką zawierającą jego lokalizację. Jeśli się jej to nie uda, to nic wielkiego się nie stanie - zwrócony zostanie łańcuch pusty, a program wyświetli okienko dialogowe i zleci użytkownikowi wpisać ścieżkę do tego pliku ręcznie.

Z tego właśnie powodu w dwóch miejscach łapane są wyjątki. Niemożność zajrzenia do wnętrza jakiegoś przetwarzanego w pętli katalogu skończy się pominięciem tego katalogu podczas poszukiwań i całkowitym przemilczeniem błędu. To dobry pomysł, jako że na dysku mogą się zdarzyć katalogi, do których zalogowany użytkownik nie ma dostępu (jak choćby System Volume Information) i algorytm nie powinien z tego powodu zawieźć. Z kolei jakikolwiek inny błąd (np. podczas pobierania listy napędów dyskowych) zakończy się zwróceniem przez funkcję łańcucha pustego, co zostanie potraktowane jako nieznalezienie pliku.

Ponieważ proces poszukiwania nie może być dla użytkownika uciążliwy, dodatkowo wprowadziłem ograniczenie czasowe. Wyrażenie DateTime.Now.Ticks zwraca bieżący czas mierzony w setkach nanosekund. Jeśli więc chcemy, aby maksymalny czas poszukiwań po jakim nasz algorytm "da sobie spokój" wynosił 5 sekund, jako stałą MAX_LOCATE_TIME musimy podać liczbę 50000000 (5 sekund * 1000 milisekund w sekundzie * 1000 mikrosekund w milisekundzie * 10 setek nanosekund w mikrosekundzie).

Podsumowanie

Przedstawiony w tym artykule algorytm jest rozwiązaniem dość specyficznego problemu poszukiwania na dysku użytkownika konkretnego pliku należącego do innego pakietu programowego, którego nasz program wymaga do działania. Jest to jednak problem, który można spotkać w praktyce, a przedstawione tu rozwiązanie sprawdza się bardzo dobrze skracając średni czas wyszukiwania z kilku minut potrzebnych na przeszukanie całego dysku do ułamka sekundy. Można je uogólnić na poszukiwanie dowolnego pliku lub katalogu, o ile posiadamy pewną wiedzę na temat jego lokalizacji czy nazwy mogącą dać nam wskazówki stanowiące podstawę do zbudowania funkcji heurystycznej.