Эффективный алгоритм поиска файлов с указанным расширением C / C ++

Question

Я хочу реализовать более быстрый поиск в каталоге. Есть ли какой-нибудь алгоритм в c / c ++ для этого?

Answer 1

Проверьте библиотеку надстройки :: файловой системы на http://www.boost.org/doc/libs/1_47_0/libs/filesystem/v3/doc/index.htm, там у вас есть класс recursive_directory_iterator.

Answer 2

Сам по себе C ++ не существует, но обычно поиск в каталоге происходит медленно из-за ввода-вывода, а также потому, что вы должны регистрировать каждый файл (или любой другой эквивалент ОС, не являющийся Unix-системой), чтобы найти что-либо, кроме его имени.Один из способов сделать это быстрее - сохранить сервер, который хранит inode и имена файлов в памяти.Конечно, сложность заключается в том, что информация об узле не является статичной.Вам нужно будет прослушивать изменения файловой системы, чтобы поддерживать ваш кэш в актуальном состоянии.Это определенно возможно в Linux, но у меня нет опыта работы с другими системами.Как вы можете видеть, другая тема этой проблемы заключается в том, что она сильно зависит от системы и, возможно, от файловой системы.Может быть, системно-независимая библиотека, такая как Boost :: Filesystem, может помочь, но я сомневаюсь, что она реализует обратные вызовы обновления каталога.

Может быть, просто установить Google Desktop?

Answer 3

Поиск - это функция ОС в наши дни, и те, кто пытается внедрить стороннюю индексацию, сдаются. Даже Google Desktop не обновляется, и большинство считает его мертвым:

https://superuser.com/questions/194082/is-google-desktop-search-a-dead-project

Если вы установите поисковый сервер на чей-то компьютер и попадаете в ловушку диска и процессора - а у вас нет очень, ОЧЕНЬ веской причины для этого - вы не только потратите много времени время написания кода и исправления ошибок, но вы также оттолкнете своих пользователей.

Для большинства кроссплатформенных приложений лучше всего разрешить пользователям находить файлы в Explorer / Finder / Nautilus, а затем заставлять ваше приложение принимать многофайловое перетаскивание. Кроме того, большинство «общих диалогов» для открытия файлов теперь предоставляют встроенные функции поиска.

Если вы пытаетесь написать инструмент для ускорения поиска для конкретной платформы, подключитесь к API этой платформы, что может даже позволить вам дополнить ее индекс. Вот API программного поиска Microsoft:

http://msdn.microsoft.com/en-us/library/windows/desktop/bb266517(v=vs.85).aspx

OS / X имеет API внимания:

http://developer.apple.com/library/mac/#documentation/Carbon/Conceptual/SpotlightQuery/SpotlightQuery.html

Я не совсем уверен, есть ли «канон» для поиска в мире Linux, но большинство всех соответствующих версий Ubuntu теперь поставляются с Tracker:

http://live.gnome.org/Tracker/Documentation

Answer 4

Вот решение для Windows (http://ideone.com/5dFVf)

class file_iterator : std::iterator<std::output_iterator_tag, const WIN32_FIND_DATA> {
    HANDLE handle;
    WIN32_FIND_DATA fdata;
public:
    file_iterator() :handle(NULL) { 
#ifdef _DEBUG
        memset(&fdata, 0, sizeof(fdata); 
#endif //_DEBUG
    }
    file_iterator(const std::wstring& path) :handle(FindFirstFile(path.c_str(), &fdata)) {}
    file_iterator(file_iterator&& b) :handle(b.handle) {b.handle = NULL;}
    file_iterator& operator=(file_iterator&& b) {close(); handle = b.handle; b.handle = NULL;}

    void close() {
        if (handle) 
            FindClose(handle); 
#ifdef _DEBUG
        memset(&fdata, 0, sizeof(fdata); 
#endif //_DEBUG
    }

    const WIN32_FIND_DATA& operator*() {return fdata;}
    file_iterator& operator++() {if (FindNextFile(handle , &fdata)==false) close(); return *this;}
    bool operator==(const file_iterator& b) {return handle == b.handle;}
    bool operator!=(const file_iterator& b) {return handle != b.handle;}
};

std::vector<std::wstring> 
    find_files_with_extension(
        const std::wstring& folder, 
        const std::wstring& extension, 
        std::vector<std::wstring>* result=NULL) 
{
    std::wstring filepath = folder + L"/*";
    std::vector<std::wstring> local_result;
    std::deque<std::wstring> todo;
    if (result == NULL) 
        result = &local_result;
    file_iterator iter(filepath);
    while(iter != file_iterator()) {
       std::wstring folder_file((*iter).cFileName);
       if ((*iter).dwFileAttributes | FILE_ATTRIBUTE_DIRECTORY)
           todo.push_back(folder_file);
       else if (folder_file.size() > extension.size() && folder_file.substr(folder_file.size()-extension.size())==extension)
           result->push_back(folder_file);
       ++iter;
    }
    for(int i=0; i<todo.size(); ++i)
        find_files_with_extension(todo[i], extension, result);
    return *result;
}

При этом используется поиск в ширину, который занимает немного больше оперативной памяти и немного сложнее, но быстрее из-за кэширования.