Есть некая папка с кучей файлов. В расширении файла пишется номер п/п (например файл: вв5вввв.345). Подскажите быстрый алгоритм поиска максимального номера (на С/С++). файлы считаются с 000, отдельные номера могут отсутствовать, сортировка по дате файлов не подходит.
Если номера файлов идут по порядку используй метод половинного деления 1. n=500, m=250 2. Проверяем существует ли файл n, если да n=n+m, m=m/2, если нет - n=n-m, m=m/2 3. Повторяем шаг 2 пока m>0
Ну тогда вот примерно так Код (Text): var finddata: WIN32_FIND_DATA; i: byte; s: string; begin i:=9; s:='*.'; while(FindFirstFile(s+char(i+48)+'*',finddata)=INVALID_HANDLE_VALUE) do i:=i-1; i:=9; s:=s+pchar(dword(cFileName)+strlen(finddata.cFileName)-3)^; while(FindFirstFile(s+char(i+48)+'*',finddata)=INVALID_HANDLE_VALUE) do i:=i-1; i:=9; s:=s+pchar(dword(cFileName)+strlen(finddata.cFileName)-2)^; while(FindFirstFile(s+char(i+48),finddata)=INVALID_HANDLE_VALUE) do i:=i-1; s:=s+pchar(dword(cFileName)+strlen(finddata.cFileName)-1)^;
Получаешь список файлов, начинаешь сравнивать текущий максимальный со следующим. Сложность O(n), быстрее не бывает Что не понятно?
murder Весьма примерно По мелочи понятно: нужно добавить в while ограничение на i >= 0 (иначе если вообще нет файлов с цифрами в расширении, то первый цикл будет крутиться до посинения), ну и ес-но FindClose не забыть добавить. По существу: после первого цикла надо бы проверить соответствие расширения цифровому шаблону и второй цикл крутить не от 9 вниз, а от второй цифры найденного файла вверх, т.к. мы ищем макс.номер. Ну и третий цикл - если на втором ничего не нашли, то выходим, если нашли, то от найденной цифры - вверх agrischuk Найти макс.число в списке - не проблема, т.к. тут основное время уйдет на получение списка файлов. Поэтому основной вопрос - что быстрее, получить сразу весь список или же хитрить с масками FindFirst как murder. Если файлов мало, то скорее всего быстрее будет получить весь список (т.к. на FindFirst и FindClose требуется доп.время), если же - много, то возможно хитрости с масками окажутся быстрее.
Также быстро получить список файлов в директории можно с помощью GetFileInformationByHandleEx При этом не происходит перебора всех файлов, а сразу читается содержимое директории.
Что-то мне подсказывает, что поиск среди имён файлов даже банальнейшим перебором всё равно будет быстрее, чем собственно чтение списка всех файлов в директории с предварительным выделением под него памяти.
А как по твоему эти маски проверяются? Они же не с неба падают, это значит ОС делает за тебя эту работу. Причем можно показать что в общем случае оно будет медленее нежели самому сделать этот перебор, так как каждый раз когда делается запрос по маске, проверяется весь список. Никак FindFirst/Next не будет быстрее.
agrischuk А ты как предлагаешь "получить список файлов" ? Через шелл-апи или последовательны перебором через те же FindFirst\FindNext или NtQueryDirectoryObject ? Если перебором, то нужно учитывать накладные расходы на многократные переходы из юзермода в кернел, плюс копирование кучи ненужных FIND_DATA. Поэтому при большом числе файлов может оказаться, что пробежаться несколько раз по списку внутри ОС окажется быстрее чем "выдавать в час по чайной ложке" для формирования полного списка на стороне юзера
leo Вопрос в том, каким должно быть количество файлов, чтобы получить выигрыш. Здесь идёт речь максимум о 1000 файлах.
murder Да может и вообще никакого выигрыша не будет - я же не утверждаю, а лишь рассуждаю А именно уточняю, что под сложностью O(n) может скрываться x*N, где x зависит от конкретной реализации
NtQueryDirectoryFile возвращает много файлов. Кстати почему ты считаешь что каждый раз FindNextFile будет обращаться в kernel? Сие очень не тривиально, и если оно действительно так делает - еще один камень в огород win api.
agrischuk Упс, и в самом деле FindFirst вызывает NtQueryDirectoryFile и получает сразу весь список файлов, а FindNext только копирует данные из этого списка в буфер (ес-но в юзермоде). Значит я не прав, посыпаю голову пеплом и бегу поджавши хвост
