Поиск большой строки C++ из сопоставления файлов быстро и эффективно

Question

Быстрое предисловие. Мне очень удобно в .Net, но у меня ограниченный опыт работы на C++, поэтому я не уверен, что я делаю это хорошо. Я использую объект сопоставления файлов, чтобы получить то, что потенциально может быть относительно длинной строкой, состоящей из нескольких тысяч имен файлов. Эта функция может быть вызвана с помощью ImageOverlayHandler, подключенного к проводнику Windows, так что потребление скорости и памяти вызывает беспокойство. Этот код потенциально может быть вызван сотнями запросов оверлей одновременно (но только в случаях краев). В приведенном ниже коде это эффективный способ сделать это? Используя этот подход, если я правильно понял свой код, я не буду создавать локальную копию сопоставленного файла, а boost :: contains call должен быть довольно быстрым. Любые мысли о том, как я могу это улучшить, или как я должен делать это по-другому? в предыдущей итерации я использовал векторы и т. д., но похоже, что она будет использовать гораздо больше памяти.

HRESULT GetFolders() 
{ 
    HANDLE hMapFile; 
    LPCWSTR pBuf; 
    hMapFile = OpenFileMapping(
       FILE_MAP_ALL_ACCESS, // read/write access 
       FALSE,     // do not inherit the name 
       szFolderName);    // name of mapping object 

    if (hMapFile == NULL) 
    { 
     return NULL; 
    } 
    pBuf = (LPCWSTR) MapViewOfFile(hMapFile, // handle to map object 
      FILE_MAP_ALL_ACCESS, // read/write permission 
      0, 
      0, 
      BUF_SIZE); 

    if (pBuf == NULL) 
    { 
     CloseHandle(hMapFile); 

     return NULL; 
    } 

    wstring resOut = (wstring)pBuf; 

    bool val = boost::contains(resOut, L"C:\\FOLDER1"); 
    UnmapViewOfFile(pBuf); 
    CloseHandle(hMapFile); 
} 

Answer 1

Если вы создаете список имен файлов один раз или только изредка и неоднократно тестируете его, вы можете воспользоваться бинарным поиском. Бинарный поиск требует двух вещей: список ввода должен быть отсортирован, и вы должны иметь возможность индексировать любой элемент списка эффективно.

Вы можете выполнить первое требование, отсортировав список на C#, прежде чем записывать его в файл. Вы можете выполнить второе требование, создав список целых чисел, которые представляют смещение в строке для начала каждого имени файла. Поскольку каждое целое число одного размера, оно может быть проиндексировано, и одно простое обращение к фактическому имени файла.

Алгоритм std::equal_range выполнит двоичный поиск. Если возвращенные итераторы равны, элемент не найден, иначе первый итератор указывает на него.

Чтобы выполнить косвенную привязку к строке, вам понадобится пользовательская функция компаратора, чтобы перейти к equal_range.

Answer 2

Поскольку вы охарактеризовали эти данные в виде списка имен файлов, рассмотреть вопрос о создании каждого файла в std::set или std::unordered_set (C++ 11) или boost::unordered_set (C++ 03 и выше).

Ваш подход имеет O (n) эффективность.

std::set будет O (log n) эффективность.

unordered_set был бы O (1) эффективность.

Примечание: создание любого из этих контейнеров должно выполняться один раз, заранее. Не для каждого звонка GetFolders()