Форум: "Начинающим";
Текущий архив: 2007.04.01;
Скачать: [xml.tar.bz2];
ВнизСравнение строк. Найти похожие ветки
← →
Riply © (2007-03-05 21:59) [0]Здравствуйте !
Вопрос такой:
Есть строковая константа с которой (так много раз, аж страшно),
надо сравнивать другие строчки (not case-sensitive) и получать
результат <, = или >
Какой вариант лучше использовать ?
const
BaseStr = "bla-bla";
if LowerCase(TestedString) < BaseStr then
......
const
BaseStr = "BLA-BLA";
if UpperCase(TestedString) < BaseStr then
......
if CompareText(TestedString, BaseStr) < 0 then
...
P.S. Хотела найти подсказку в исходниках, но там ассемблер,
а мы с ним еще не подружились :(
← →
DVM © (2007-03-05 22:01) [1]
> Какой вариант лучше использовать ?
Мое мнение CompareText() или CompareString().
← →
DVM © (2007-03-05 22:08) [2]Сравнил ждля 1000 повторов так:
s1:="qwerty";
s2:="ytrewq";
for i:= 1 to 1000 do
begin
//if UpperCase(s1) < s2 then begin end; // 2 место 97 микросекунд
//if LowerCase(s1) < s2 then begin end; // 3 место 101 микросекунд
if CompareText(s1, s2) < 0 then begin end; // 1 место 27 микросекунд
end;
← →
Аноним (2007-03-05 22:11) [3]
> (так много раз, аж страшно),
Сколько раз? Приблизительно?
> DVM ©
> for i:= 1 to 1000 do
Надо больше брать, до миллиона
← →
Eraser © (2007-03-05 22:13) [4]> [2] DVM © (05.03.07 22:08)
> CompareText()CompareText is not case sensitive
т.о. Upper/LowerCase лишние.
PS лучше использовать AnsiCompareText.
← →
DVM © (2007-03-05 22:14) [5]
> Надо больше брать, до миллиона
s1:="qwerty";
s2:="ytrewq";
for i:= 1 to 1000000 do
begin
//if UpperCase(s1) < s2 then begin end; // 2 место 90597 микросекунд
//if LowerCase(s1) < s2 then begin end; // 3 место 94217 микросекунд
if CompareText(s1, s2) < 0 then begin end; // 1 место 19254 микросекунд
end;
← →
DVM © (2007-03-05 22:16) [6]
> Eraser © (05.03.07 22:13) [4]
> > [2] DVM © (05.03.07 22:08)
>
>
> > CompareText()
>
> CompareText is not case sensitive
> т.о. Upper/LowerCase лишние.
Так ему вроде и надо not case
← →
DVM © (2007-03-05 22:18) [7]
> т.о. Upper/LowerCase лишние.
У меня они закоментированы, это же для теста.
← →
Eraser © (2007-03-05 22:19) [8]> [6] DVM © (05.03.07 22:16)
прошу прощение, хотел её процитировать, а процитировал тебя )
← →
Riply © (2007-03-05 22:19) [9]> [2] DVM © (05.03.07 22:08)
Для лучшего результата надо сравнивать равные строки
(иначе ты сравниваешь только первый символ)
P.S.
Забыла добавить в [0] Riply © (05.03.07 21:59)
Предполагается, что TestedString такой же длины, как и BaseStr.
>[3] Аноним (05.03.07 22:11)
>Сколько раз? Приблизительно?
Возможно, для выражения этого числа, DWord-а хватит :)
← →
DVM © (2007-03-05 22:25) [10]
> Для лучшего результата надо сравнивать равные строки
ok, справнил одинаковые - разницы практически нет.
← →
Riply © (2007-03-05 22:29) [11]Спасибо всем. Пока остановлюсь на AnsiCompareText.
← →
DVM © (2007-03-05 22:31) [12]
> Спасибо всем. Пока остановлюсь на AnsiCompareText.
Зря. Он в 10(!) раз медленнее чем CompareText()
← →
Palladin © (2007-03-05 22:37) [13]
> DVM © (05.03.07 22:31) [12]
девствительно, только вот AnsiCompareText("б","Б") почемуто 0, а CompareText("б","Б") не 0 ...
← →
DVM © (2007-03-05 22:44) [14]
> Palladin © (05.03.07 22:37) [13]
Надо же, а я и не знал.
Исходя из того, что требуется сравнение
> not case-sensitive
Я бы выбрал комбинацию Upper/LowerCase + CompareText - все быстрее получится.
← →
DVM © (2007-03-05 22:47) [15]Upper/LowerCase + CompareText - 180000 микросекунд
AnsiCompareText - 220000 микросекунд - почти на 20% медленнее.
← →
Kedge © (2007-03-05 22:47) [16]> [14] DVM © (05.03.07 22:44)
Что-то я не пойму: А зачем, при использовании CompareText, еще нужны и Upper/LowerCase ?
← →
DVM © (2007-03-05 22:50) [17]А если учесть, что в верхний регистр базовую константу-строку переводить придется только 1 раз - то разница еще выше 110000
← →
DVM © (2007-03-05 22:52) [18]
> Kedge © (05.03.07 22:47) [16]
там вот в [13] написали
← →
DVM © (2007-03-05 23:00) [19]Хотя UpperCase() не работает с русскими буквами, а использование AnsiUpperCase сводит на нет все преимущества того, что я написал выше.
← →
Sha © (2007-03-05 23:15) [20]Хорошо бы добавить в описание немного специфики из области использования, тогда можно будет дать определенный ответ.
Например, разовый поиск в несортированном списке и вставка в
сортированный список могут быть оптимизированы по-разному.
В общем, может есть какие-то особенности задачи,
на которых можно сыграть, а именно:
сравниваются ли строки разной длины, или всегда одинаковой,
какой тип сравнения нужен =, <> или <,=,>, все или один,
наиболее частый результат сравнения,
надо ли сравнивать национальные символы,
насколько константы являются "константами".
Приведение к LowerCase (ANSILowerCase) неверно в принципе,
если требуется результат, совместимый с CompareText (ANSICompareText).
Вместо AnsiCompareText лучше написать свою с использованием таблицы,
сформированной на основе ANSILowerСаse
← →
Johnmen © (2007-03-05 23:28) [21]
> Sha © (05.03.07 23:15) [20]
А я тут FastCode вспомнил, там CompareText или что-то аналогичное было...
← →
Игорь Шевченко © (2007-03-05 23:30) [22]
> Предполагается, что TestedString такой же длины, как и BaseStr.
а можно использовать _memicmp из ntdll.dll, если не требуется case-insensitive сравнения русских букв :)
← →
Sha © (2007-03-05 23:37) [23]> Johnmen © (05.03.07 23:28) [21]
> А я тут FastCode вспомнил, там CompareText или что-то аналогичное было...
Угу
← →
Riply © (2007-03-06 00:03) [24]> [20] Sha © (05.03.07 23:15)
>Хорошо бы добавить в описание немного специфики из области использования,
>тогда можно будет дать определенный ответ.
>В общем, может есть какие-то особенности задачи,
>на которых можно сыграть
Заранее задан массив строк (10 - 60 элементов, по 1 - 255 символов)
В нашей власти, перед работой, его сортировать по любому признаку,
делать Upper/LowerCase, перебросить в TStringList или еще куда :)
можем выбирать они - ShortString или string, кирилица допустима, East Asian не поддерживаем.
Cравнение not case-sensitive.
Поступающие строки для проверки: 0 - 1023 символа.
Никаких ограничений на их формат нет (например, могут содержать #0 в любом месте).
Требуется определить
заканчивается ли тестируемая строка на одну из строчек массива,
("xxxx#0xxxyyyyyyyф" заканчивается на "yyyф")
если нет, то определить содержит ли она хотябы одну из них
← →
Riply © (2007-03-06 00:06) [25]>[21] Johnmen © (05.03.07 23:28)
>А я тут FastCode вспомнил
А кто такой "FastCode" и где его дают ? :)
← →
Sha © (2007-03-06 00:19) [26]> Riply © (06.03.07 00:03) [24]
Так это ж совсем другое дело )
Поступающие для проверки строки - это буфер с PChar"ами ?
> Riply © (06.03.07 00:06) [25]
http://www.fastcodeproject.org/
http://fastcode.sourceforge.net/
← →
Sha © (2007-03-06 00:23) [27]> кирилица допустима
равны ли "Ф" и ф"" ?
← →
Riply © (2007-03-06 01:32) [28]> [27] Sha © (06.03.07 00:23)
>равны ли "Ф" и ф"" ?
Равны.
>Поступающие для проверки строки - это буфер с PChar"ами ?
Мы сами можем выбирать в каком виде их нам поставлять
← →
Sha © (2007-03-06 09:22) [29]Тогда, похоже, оптимальным будет представление его любом виде,
позаоляющем определить длину элемента:
буфер ShortString"ов,
массив ANSI-строк,
StringList.
Для массива шаблонов заранее вычисляешь хеш-значения при помощи Case-нечувствительной функции.
И просто бежишь по массиву строк для проверки от последнего элемента к первому, вычисляешь хеши и ищешь их в таблице.
← →
Sha © (2007-03-06 09:42) [30]Если это будет медленно, можно попробовать использзовать для сравнения информацию о длине строк и двухуровневое хеширование.
Первая функция, например, может хешировать 2 первых (начиная с младшего байта длины) и 2 последних символа строки и предназначена для быстрого отсева ненужных строк.
← →
Sha © (2007-03-06 09:48) [31]* начиная с байта длины - для ShortString
для AnsiString можно хешировать word длины, и первый и последний word строки
← →
Leonid Troyanovsky © (2007-03-06 10:28) [32]
> Riply © (06.03.07 00:03) [24]
> Заранее задан массив строк (10 - 60 элементов, по 1 - 255
> символов)
Пусть это будет массив записей длина; строка.
Приведем строки, скажем, к нижнему регистру.
> В нашей власти, перед работой, его сортировать по любому
> признаку,
Признак этот должен быть примерно таким: ожидаемая частота
появления во входном тексте данной цепочки.
Т.е., сначала будут идти односимвольные цепочки, двух и т.д.
Ну, а цепочки одинаковой длины упорядочены по частоте.
Возможен, чтобы требуемое упорядочение придется получать
по некому представительному образцу анализируемого текста.
Возможно, что для двух задач - окончание на цепочку и
вхождение цепочки потребуют разного упорядочения.
> Поступающие строки для проверки: 0 - 1023 символа.
> Никаких ограничений на их формат нет (например, могут содержать #0 в
Подобную цепочку надо распарсить примерно так же: длина;строка
и привести строки к тому же регистру.
Производить проверки будем начиная с самых частых цепочек,
(напрмер, это будут самые короткие).
Ну и рабочей лошадкой для первой задачи (окончание) я б выбрал
AnsiStrLComp.
Для второй (вхождение) AnsiStrPos, хотя, можно еще подумать.
Да, при всех операциях мы не должны использовать StrLen и т.п.
а лишь арифметические операции с PChar.
--
Regards, LVT.
PS А чего это за задача? Работа со словарем Зализника?
← →
Leonid Troyanovsky © (2007-03-06 10:35) [33]
> Sha © (06.03.07 09:48) [31]
> для AnsiString можно хешировать word длины, и первый и последний
А чего даст хеширование, если среди образцов есть односимвольные?
--
Regards, LVT.
← →
Sha © (2007-03-06 11:37) [34]> Leonid Troyanovsky © (06.03.07 10:35) [33]
>> для AnsiString можно хешировать word длины, и первый и последний word строки
> А чего даст хеширование, если среди образцов есть односимвольные?
Например, для строки " 1" мы хешируем word"ы:
$0001 - word длины, смещение -4 от начала строки
$0031 - первый word, смещение 0 от начала строки (возможно с залезанием в терминатор)
$3100 - последний word, смещение -2 от терминатора строки (возможно с залезанием в старший байт длины)
Результат зависит от использованной функции
--
Regards, Aleksandr )
← →
Sha © (2007-03-06 11:41) [35]Там в примере опечатка - строка односимвоьная должна быть "1"
← →
Riply © (2007-03-06 13:02) [36]>[29] Sha © (06.03.07 09:22)
>И просто бежишь по массиву строк для проверки от последнего элемента к первому, вычисляешь хеши и ищешь их в таблице.
>[32] Leonid Troyanovsky © (06.03.07 10:28)
>Возможен, чтобы требуемое упорядочение придется получать
>по некому представительному образцу анализируемого текста.
>Подобную цепочку надо распарсить примерно так же: длина;строка
>и привести строки к тому же регистру.
А оправданы ли временные затраты на "вычисляешь хеши"
или "и привести строки к тому же регистру" ?
Ведь текст мы протестировали и выбросили. Второй раз искать в нем
что-то другое мы уже не будем.
Наверное, я чего-то не понимаю, или плохо ставлю задачу :(
Попробую еще раз, заодно упростив(?) условия:
Тестируемые строки будем считать полученными так SetLength(TestString, Random(1024))
и заполненные Random - значениями, взятыми из объединения
"Войны и мира", "Оценки остаточного члена в предельных теоремах для сумм
независимых случайных величин с распределением специального вида" (вместе с формулами) и Гамлета в оригинале :)
Заранее задан массив строк (10 - 30 элементов, по 2 - 32 символов).
Требуется определить только
заканчивается ли тестируемая строка на одну из строчек массива (регистро-независимо).
(совпадают = заканчивается)
P.S. Вот уж не думала, что с таким, внешне простым вопросом, придется так разбираться :)
← →
Leonid Troyanovsky © (2007-03-06 13:40) [37]
> Riply © (06.03.07 13:02) [36]
> А оправданы ли временные затраты на "вычисляешь хеши"
> или "и привести строки к тому же регистру" ?
Ну, в, любом случае, сравнение-то не одно - мы ж должны
сравнить поступившее с каждой из констант.
> Заранее задан массив строк (10 - 30 элементов, по 2 - 32
> символов).
> Требуется определить только
> заканчивается ли тестируемая строка на одну из строчек массива
> (регистро-независимо).
А, я так и подозревал, что там нет односимвольных цепочек :)
И, значит, все-таки, вхождения тоже нет - только окончание.
В любом случае, то, что я говорил в прошлом сообщении
значения не потеряло.
Кстати, с массивом констант нужно провести дополнительную
работу, например, исключить из массива те элементы,
которые не проходят ту же проверку, т.е. если первый элемент
"нт", то из массива надо убрать "ент" и т.п.
Кста, словарь Зализняка (sic!) построен, как раз, так,
т.е. буквы слова следуют в обратнов порядке -"екдяроп".
И, вообще-то, неплохо б было огласить всю задачу (или цель),
может кто еще чего вспомнит.
--
Regards, LVT.
← →
Leonid Troyanovsky © (2007-03-06 13:53) [38]
> Riply © (06.03.07 13:02) [36]
> вида" (вместе с формулами)
Ну, а что будет в случае формул поступать во входном потоке
описание в кнутовском TeX или еще что?
--
Regards, LVT.
← →
Riply © (2007-03-07 07:35) [39]>И, вообще-то, неплохо б было огласить всю задачу (или цель),
>может кто еще чего вспомнит.
Вся задача слишком глобальна - "анализ статьи(материала)(в определенной области) на предмет плагиата",
а у меня маленький алгоритм из маленькой подпрограммы, маленького блока основной задачи :)
>Ну, а что будет в случае формул поступать во входном потоке
>описание в кнутовском TeX или еще что?
Сейчас, вроде, все основные журналы с удовольствием принимают и в "pdf" формате :)
"вместе с формулами" - в моем случае надо понимать не так широко,
я имела ввиду, что "x >= y" врядли встретиться в "Войне и мире" или Гамлете :)
← →
Leonid Troyanovsky © (2007-03-07 10:50) [40]
> Riply © (07.03.07 07:35) [39]
> а у меня маленький алгоритм из маленькой подпрограммы, маленького
> блока основной задачи :)
Чего-то он у тебя уж очень маленький, судя по 10-30/60 элементам :)
> я имела ввиду, что "x >= y" врядли встретиться в "Войне
В математической статье, кроме формул, словарь не намного
больше, чем у Эллочки-людоедки.
--
Regards, LVT.
Страницы: 1 2 вся ветка
Форум: "Начинающим";
Текущий архив: 2007.04.01;
Скачать: [xml.tar.bz2];
Память: 0.56 MB
Время: 0.039 c