|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 28 May 2003 21:57:33
To : Yuri Burger
Subject : Re: Hечеткое сравнение строк
--------------------------------------------------------------------------------
"Yuri Burger" <kruger@selena.net.ua> wrote in message
news:bb269u$2q5$1@news.lucky.net...
> SK> безымянное namespace в данном случае практически
> SK> бесполезно
>
> В нем лежит вспомогательная тулза, видимостью готорой я не хочу
вводить в
> заблуждение юзера. Так что оправдано.
и что мешает пользователю написать
void f(){
using namespace fuzzy;
int a[1];
compare(&a[0],&a[1],&a[0],&a[1],0,0,0,0);
}
в данном случае все остается видимым пользователю,
сокрытия в хидере можно достичь например введением
функтора дружественного только к вызываемой
пользователем функции
(либо локальный класс-функтор в функции)
> SK> ведущие подчеркивания в идентификаторах не
> SK> рекомендуются
>
> Открой STL, boost ;-)
вот именно, лидиоующие подчеркивания оставлены за
реализацией (читай - компилятор и стандартная библиотека)
а в boost я открыл наугад с десяток ходеров и в одном таки
обнаружил два локальных случая начальных подчеркиваний,
но это исключение в пользовательских библиотеках, а не правило
> SK> параметры d и maxD вполне ИМХО можно заменить одним,
>
> Ы? maxD - это сквозной барьер, константа, задаваемая в корневом вызове
> (принимать const int - изврат). d - это текущий счетчик величины разрыва
> строки.
>
> SK> хотя проверка _d в цикле и присвоение ему 0 в конце
> SK> выглядит несколько подозрительно
>
> Проверка - это барьер для рекурсии. Проверка в цикле - это конечно
излишне,
> достаточно былоб сделать проверку в самом начале функции, но писать
> if(d==maxD){return best;} вместо дополнительной проверки в цикле - эт тож
смое
> что ты написал про временные s1 и s2 ;-)
не совсем, в данном случае упрощается понимание,
при прочтении не надо думать как меняется d, в том смысле,
что настроится на итерацию или на рекурсию отдельно достаточно
легко, но вот когда они смешаны вместе - это уже чересчур
> А сброс в 0... Логика такая - при сравнении строк делается попытка
> "раздвинуть" одну из них так, чтоб у них совпало максимум символов.
Тоесть,
> сделать вместо сравнения "1234" с "124" сравнение "1234" с "12_4". Размер
> максимальной "дыры" - это maxD. Если же при входе в очередную рекурсию мы
> сделали сравнение двух текущих символов и сдвинулись на следующие, то
размер
> текужей дыры сбрасывается в 0, т.к. таковая завершилась в момент сравнения
> текущих символов, но при этом онаже (дыра) продолжает рости в той ветке,
где
> происходит повторый вход в рекурсию.
>
> SK> в первом темплейте в типе T указатель можно угадать
> SK> после третьего прочтения, (возможно подразумевались
> SK> итераторы,
>
> Они и есть. Тоесть, подходит всё, что может быть использовано в
качестве
> итератора (в том числе и указатель).
>
> SK> но +1 для стандартных итераторов недопустимо)
>
> Ды ну ;-) Допустимо для итераторов произвольного доступа - таких как у
> вектора и стринга. Hо вообще, ты прав в том смысле, что сравнивать могут и
> листы. Так что лучше поправить на инкремент.
недопустимо ни для вектора ни для стринга,
просто во многих реализациях стандартной библиотеки
итераторы вектора и стринга определены как простые
указатели - вот оно и проходит ... пока
> SK> minmax нестандартен (стандартным есть <algorithm> )
> SK> и иклудится по-видимому только для одного min и одного max,
>
> Справедливо. Лучше заюзать std::min/max да и s1 и s2 отпадут за
> ненадобностью.
>
> SK> while(true) с последующим if()brake; и ++ для параметров в конце,
> SK> вы меня извините, но в этом for() видится за версту
>
> Hу не скажи. Часто например запрещают (на фирмах) использование for
без
> инициализации, типа for(;a<b;a++) изза извращенного прочтения: для /пусто/
> делать a++ пока a<b
> В таких случаях требуют использование while, дабы оно читалось.
то есть единственная причина - отсутствие инициализации?
так она же у тебя и была :)
с другой стороны ты сразу декларируешь, что ты будешь делать
с параметрами цикла, и избавляешся от длинных условий, ь.е.
вместо
while(true)
{
if(d==maxD||fb==fe||sb==se||(f+std::min(fe-fb,se-sb))<=best){break;}
[...]
++fb;
++sb;
d=0;
}
даже в случае запрета на отсутствие инициализации в for,
вряд ли кто запретит переписать подобное как
while( d!=maxD && fb!=fe && sb!=se &&
f+std::min(fe-fb,se-sb)>best) ){
[...]
++fb;
++sb;
d=0;
}
хотя мне более нравится явное выделение трех причин завершения
if(d==maxD) return best;
for(/* no initialization needed*/; fb!=fe && sb!=se; ++fb,++sb,d=0){
if(f+std::min(fe-fb,se-sb)<=best) break;
[...]
}
> SK> трижды встречающийся кусок lf=...; if(best<lf){best=lf;} так и
> SK> просится в инлайновую функцию
>
> Ты прав. Только не в инлайновыю функцию, а просто заменить на
присваивание
> результатом std::max. Оптимизатор должен обойти лишнее приравнивание, а
код
> гораздо меньше и понятней становится.
в двух последних случаях можно просто
best =compare(...,best);
ибо compare, как я понял, может только увеличить best
> SK> введение s1 и s2 основано на предвосылке, что экономия
> SK> одного такта при компиялции без оптимизации важнее, чем
>
> Можно выкинуть и не потерять в производительности, просто нужно
пользовать
> min/max не из макросов.
а-а-а ... тяжкое наследие С ... :)
> SK> static_cast<doube> - ИМХО это не то место, где стоит
> SK> его использовать
>
> Что ты предлагаешь, сишное преобразование? Одна из причин введения
кастов -
comapre(...)*1.0/size - каст отсутствует совсем
> это возможность быстрого нахождения их в сырце.
самая очевидная причина, но не самая главная
> SK> пустые строки не сравниваются,
>
> Справедливо. Фиксим :)
>
> SK> а что стоило немного расширить область параметров чтобы немного
оградить
> SK> пользователя
>
> Ы? Что ты имеешь в виду?
да именно ту проверку на size>0, которую ты и сделал
> Вот что получилось:
>
> #ifndef __FUZZYCOMPARE_H__
> #define __FUZZYCOMPARE_H__
>
> #include <algorithm>
>
> namespace fuzzy
> {
> namespace
> {
> template<typename T> int compare(T fb,T fe,T sb,T se,int d,int
maxD,int
> f,int best)
> {
> int of;
зачем оно здесь, если можно ограничить зону видимости без ущерба,
то стоит ее ограничить
> while(true)
> {
>
> if(d==maxD||fb==fe||sb==se||(f+std::min(fe-fb,se-sb))<=best){break;}
вычитание, кстати, тоже не определо для итераторов
> of=f;
int of =f;
> if(*fb==*sb){best=std::max(best,++f);}
>
> T t=sb;
> best=std::max(best,compare(fb,fe,++t,se,d+1,maxD,of,best));
> t=fb;
> best=std::max(best,compare(++t,fe,sb,se,d+1,maxD,of,best));
мне честно сказать очень подозрительны длинные списки параметров,
особенно если они практически повторяются (Refactoring, "bad smell")
что если попытаться обернуть этот набор 4-х последних параметров
в класс, а compare сделать функцией-членом данного класса?
конечно это итерациионно-рекурсивные изменения отследить не
очень просто, но мне кажется, что и не чересчур сложно -
d и f возможно прийдется локально запоминать, но maxD - константа,
а best - един для всех
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
