Re: Вопросец возник...

From

Oleg Khovayko ()

To

Evgeniy Jirnov ()

Date

2003-01-25T04:48:28Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Так. За три дня никто не ответил.
Придется мне отвечать.

Evgeniy Jirnov wrote:
> Мир твоему дому, All.
> 
> Что-то я не соображу: бинарный поиск imho применить нельзя.

Нельзя. точно.

> Как же быть? 

Какой пустяк - медведя раздобыть! ;)

> Не
> перебирать же 3000 строк на совпадение с маской по возрастанию? 

А придется! :(

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

К сожалению:

1. У меня нет готового генератора КА для списка масок.
Поэтому поделиться готовым рецептом не могу.

2. Всегда может существовать такой набор масок, где
КА не даст выигрыша по сравнению с простым сравнением
по маске "в лоб"

> Причем масок
> около 500. Получается мне надо перебрать 3000*500=1500000 комбинаций? :(
Ага.

Чем реально могу пособить - в свое время я написал эффективную процедуру
сравнения имени файла с маской, которая в худшем случае производит
(A+1)*L операций сравнения, где А - число звездочек в маске, а L - длина
строки-кандидата.

Хочу заметить, что это существенно лучше того, что сейчас применяется
в UNIX-ах. Ибо UNIX shell можно в легкую положить такой 
последовательностью команд:

touch aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
ls *a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b

Там процедура сравнения с маской написана убого, и при вышеуказаной
паре fname/fmask сваливается в факториальное время вычислений от 
количества звездочек.

Могу добавить, что та же убогость применяется и в ftpd, что
при известном умении и сноровке позволяет уложить удаленный
UNIX-сервер через internet.

Так же та же глюка есть в FAR-овском искателе по маске. Нарвавшись
на такой файл, FAR ложится напрочь, и затормаживает весь Windows.

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

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)