Эффективные алгоритмы поиска файлов в подкаталогах

Тема в разделе "WASM.ASSEMBLER", создана пользователем Thread, 17 авг 2005.

  1. Thread

    Thread New Member

    Публикаций:
    0
    Регистрация:
    12 июл 2005
    Сообщения:
    26
    Адрес:
    Ukraine
    Знаю, тема ламерская... Но стоит ребром.

    На небольшой алгоритм поиска файлов в подкаталогах (один, хочу заметить), в инете нарыл кучу вариаций... При чем далеко не самых эфективных, если сказать, что по скорости уступают даже виндузовскому поиску... =//



    Думаю, все в свое время реализовывали данный алгоритм, и все по своему... Кому не жалко, и кто хочет поделиться с миром своими разработками, огромнейшая просьба либо детально скинуть алгоритм, либо кусочек кода... :) Заранее благодарен. :)



    P.S. Некоторые могут подумать, что у меня у самого с реализацией поиска дела идут туго... Кстати, правильно подумают. :)
     
  2. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    Алгоритм действительно сложнейший...
    Код (Text):
    1. FindAll:
    2.  
    3. FindFirstFile(*.*)
    4. do
    5. if(Directory?)
    6. {
    7.   cd name
    8.   FindAll
    9.   cd ..
    10. }
    11. while(!FindNextFile())


    Какая-то смесь *.c и *.bat получилась :)
     
  3. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
  4. spencer

    spencer New Member

    Публикаций:
    0
    Регистрация:
    15 авг 2005
    Сообщения:
    277
    действительно, чем плохо?
     
  5. CyberManiac

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.473
    Адрес:
    Russia
    Наверное, все-таки вопрос был в другом: допустим, если искать все файлы типа BAT и BMP, то можно вместо поиска по маске *.* искать *.B* или даже *.B??. Сам я статистики по скорости поиска файлов не собирал и не могу сказать, даст ли такая оптимизация маски сколь-нибудь заметный эффект, однако не прочь был бы узнать, дает ли преимущество "усовершенствование" маски и использование вопросиков вместо звездочек.
     
  6. alpet

    alpet Александр

    Публикаций:
    0
    Регистрация:
    21 сен 2004
    Сообщения:
    1.221
    Адрес:
    Russia
    Имхо преимущество от оптимизации поиска можно получить, при грамотной реализации поддержки индексации файлов (NTFS такое поддерживает). Это с расчетом на то что поиск работает, по содержимому файлов. Еще есть вариант - регулярное обновление некоторой структуры файлов (проход по всем изменившимся папкам) в памяти приложения, в которой налажен эффективный поиск по маске. То есть при обращении на поиск информации - API функции не мучаются, а сканируется в таблице (по маске или без оной), что на ассемблере может быть реализовано очень эффективно (хотя при этом, если сама таблица не обновляется в Real-Time, некоторые файлы могут быть незамечены, или найдены уже удаленные файлы). Еще вариант - попробывать многопоточный поиск в различных папках, может на гипертрединговых и не только процессорах это даст прирост в производительности.
     
  7. Folk Acid

    Folk Acid New Member

    Публикаций:
    0
    Регистрация:
    23 авг 2005
    Сообщения:
    432
    Адрес:
    Ukraine
    Сначала нужно определиться с тем, что за файл ищем, а уж потом оптимизировать.



    Можно предусмотреть "белый список" и "черный список" имен подкаталогов для конкретного файла, поиграться с приоритетами поиска по атрибутам доступа к папке и датам последнего доступа. В конце, концов, сделать само-обучаемую систему определения вероятности нахождения файла в конркетном подкаталоге



    А сам поиск выполнять при многпоточной организации - в овтет на каждый найденный подкаталог программа стартует новый поток с поиском в этом каталоге, потоки синхронизируются с диспечтером (программы), который уж и ввыставляет приоритеты



    При самом безмозглом многпоточном алгоритме мат ожижание от среднего время поиска уменьшится



    Это, так, вольные рассуждения...
     
  8. dr_dred

    dr_dred Сергей

    Публикаций:
    0
    Регистрация:
    12 мар 2005
    Сообщения:
    301
    Адрес:
    Russia
    Вот в examples bcpp505 нашел.

    Вообще рекурсия и все. Типа как _DEN_ предложил.

    [​IMG] _641889575__FFIND.zip
     
  9. mix_mix

    mix_mix Михаил

    Публикаций:
    0
    Регистрация:
    8 окт 2005
    Сообщения:
    277
    Адрес:
    Токио
    Кстати, немного не в тему, но надо стараться избегать рекурсии, а обходиться одними циклами - рекурсия жрет ой как много памяти.
     
  10. IceStudent

    IceStudent Active Member

    Публикаций:
    0
    Регистрация:
    2 окт 2003
    Сообщения:
    4.300
    Адрес:
    Ukraine
    mix_mix

    И сколько же? 8 байт на каждый вызов (при одном параметре)?
     
  11. rst

    rst New Member

    Публикаций:
    0
    Регистрация:
    5 май 2003
    Сообщения:
    165
    microsoft indexing service -ищем не по диску а по индексированной базе файлов.

    мс его и использует.

    есть начиная с вин2000



    читай спеки по xfs filesystem -более быстрой я не видел



    в любом случае тебе нужно создавать базу файлов(индекс) а потом по ней искать.