Re: поиск

From

akrivosheev@utc.ru ()

To

Serj Okladnikov

Date

2002-09-08T21:54:42Z

Area

RU.ALGORITHMS

From: akrivosheev@utc.ru



>  SO>> Hyжно найти слово в пpедложении без пpобелов. Сейчас я пpовеpяю
>  SO>> символы по очеpеди и если очеpедной не совпадает с соответствyющим
>  SO>> в слове, то я начинаю сpавнивать пеpвый символ слова с
>  SO>> несовпавшим, второй с следующим: пчелылюбятмед

..давечечечевицауродилась..
слово чечевица по твоему алгоритму тут будет пропущено. Алгоритм неверен для слов с
повторяющимися элементами.

> > pеализация на каком языке?
> > на C - char *strstr(const char *str, const char *substr) <string.h>
> > на pascal - pos(substr, str);
> Исследовать их работу некогда, да и не факт что там оптимально правильно.

А зря некогда, можно много полезного почерпнуть.  Как правило такие команды очень
хорошо оптимизированны на уровне ассемблера и усовершенствовать их довольно сложно.
Скажем использование на современных 32 битных процессорах сравнения не по 8 битным
символам, а используя загрузку сразу 4 байт в регистр процессора и последущего
сравнения просто сдвигом на 8 разрядов. Одна пересылка из памяти в регистр -
сравнение 4 символов или по твоему алгоритму для каждого символа будет производится
загрузка - вот оцени быстродействие, учитывая что частота на которой работает
процессор в 5-10 выше чем та, на которой работает память. ....не говорите мне про
кеш и пр.. конечно данные загружаются из кеша, а не из памяти и скорость работы тут
выше, но как  загружается кеш вы знаете? Поверте, архитектуру процессора нужно
учитывать, и разработчики это учитывают, поэтому лучше чем использовать встроенные
комманды поиска наверняка будет более эффективным. По крайней мере можно
попробовать и сравнить быстродействие. Мне кажется что разрабатывать свой алгоритм
имеет смысл тогда когда нужет какой-то нетривиальный поиск... сравнение.... для
которого надо использовать несколько комманд "высокого" уровня, либо если всё-таки
скорость встроенной комманды будет недостаточна.

>
>
> > //втоpая - подстpока котоpyю нyжно найти и заменить(yдалить) на тpетью
> > //стpокy.
> > // возвpащает пpеобpазованнyю стpокy
> У меня уже реализован поиск и замена для файла который нельзя целиком загрузить
> и делать его копию на диске(скажем из-за размера), был бы рад узнать правилен
> ли приведенный мной метод поиска, всегда ли он результативен, покрайней мере
> пока он более быстродейственен т.к. не требует повторного чтения символов
> которые уже были прочитаны, по сравнению с приведенным мной вторым методом.
>
> С уважением
>           Serj

--- ifmail v.2.15dev5
 * Origin: JV Izhcom Ltd. (2:5020/400)