Сравнение строк.

← →
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 последних символа строки и предназначена для быстрого отсева ненужных строк.

* начиная с байта длины - для ShortString
для AnsiString можно хешировать word длины, и первый и последний word строки

> Riply © (06.03.07 00:03) [24]

> Заранее задан массив строк (10 - 60 элементов, по 1 - 255
> символов)

Пусть это будет массив записей длина; строка.
Приведем строки, скажем, к нижнему регистру.

> В нашей власти, перед работой, его сортировать по любому
> признаку,

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

Возможен, чтобы требуемое упорядочение придется получать
по некому представительному образцу анализируемого текста.

Возможно, что для двух задач - окончание на цепочку и
вхождение цепочки потребуют разного упорядочения.

> Поступающие строки для проверки: 0 - 1023 символа.
> Никаких ограничений на их формат нет (например, могут содержать #0 в

Подобную цепочку надо распарсить примерно так же: длина;строка
и привести строки к тому же регистру.
Производить проверки будем начиная с самых частых цепочек,
(напрмер, это будут самые короткие).

Ну и рабочей лошадкой для первой задачи (окончание) я б выбрал
AnsiStrLComp.
Для второй (вхождение) AnsiStrPos, хотя, можно еще подумать.

Да, при всех операциях мы не должны использовать StrLen и т.п.
а лишь арифметические операции с PChar.

--
Regards, LVT.

PS А чего это за задача? Работа со словарем Зализника?

> Sha © (06.03.07 09:48) [31]

> для AnsiString можно хешировать word длины, и первый и последний

А чего даст хеширование, если среди образцов есть односимвольные?

--
Regards, LVT.

> Leonid Troyanovsky © (06.03.07 10:35) [33]

>> для AnsiString можно хешировать word длины, и первый и последний word строки

> А чего даст хеширование, если среди образцов есть односимвольные?

Например, для строки " 1" мы хешируем word"ы:
$0001 - word длины, смещение -4 от начала строки
$0031 - первый word, смещение 0 от начала строки (возможно с залезанием в терминатор)
$3100 - последний word, смещение -2 от терминатора строки (возможно с залезанием в старший байт длины)

Результат зависит от использованной функции

--
Regards, Aleksandr )

Там в примере опечатка - строка односимвоьная должна быть "1"

>[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. Вот уж не думала, что с таким, внешне простым вопросом, придется так разбираться :)

> Riply © (06.03.07 13:02) [36]

> А оправданы ли временные затраты на "вычисляешь хеши"
> или "и привести строки к тому же регистру" ?

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

> Заранее задан массив строк (10 - 30 элементов, по 2 - 32
> символов).
> Требуется определить только
> заканчивается ли тестируемая строка на одну из строчек массива
> (регистро-независимо).

А, я так и подозревал, что там нет односимвольных цепочек :)
И, значит, все-таки, вхождения тоже нет - только окончание.

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

Кста, словарь Зализняка (sic!) построен, как раз, так,
т.е. буквы слова следуют в обратнов порядке -"екдяроп".

И, вообще-то, неплохо б было огласить всю задачу (или цель),
может кто еще чего вспомнит.

--
Regards, LVT.

> Riply © (06.03.07 13:02) [36]

> вида" (вместе с формулами)

Ну, а что будет в случае формул поступать во входном потоке
описание в кнутовском TeX или еще что?

--
Regards, LVT.

>И, вообще-то, неплохо б было огласить всю задачу (или цель),
>может кто еще чего вспомнит.
Вся задача слишком глобальна - "анализ статьи(материала)(в определенной области) на предмет плагиата",
а у меня маленький алгоритм из маленькой подпрограммы, маленького блока основной задачи :)
>Ну, а что будет в случае формул поступать во входном потоке
>описание в кнутовском TeX или еще что?
Сейчас, вроде, все основные журналы с удовольствием принимают и в "pdf" формате :)
"вместе с формулами" - в моем случае надо понимать не так широко,
я имела ввиду, что "x >= y" врядли встретиться в "Войне и мире" или Гамлете :)

> Riply © (07.03.07 07:35) [39]

> а у меня маленький алгоритм из маленькой подпрограммы, маленького
> блока основной задачи :)

Чего-то он у тебя уж очень маленький, судя по 10-30/60 элементам :)

> я имела ввиду, что "x >= y" врядли встретиться в "Войне

В математической статье, кроме формул, словарь не намного
больше, чем у Эллочки-людоедки.

--
Regards, LVT.

>Leonid Troyanovsky © (07.03.07 10:50) [40]
>Чего-то он у тебя уж очень маленький
Зато очень нужный :)
Так что берегитесь ! Скоро всех плагиаторов прищучим :)

> Riply © (07.03.07 13:10) [41]

> Зато очень нужный :)

Это хорошо, что нужный.
Расскажешь, что получилось.

> Так что берегитесь ! Скоро всех плагиаторов прищучим :)

Теперь будем осторожней.
Грешим-то, в основном, заимствованием и самоцитированием ;)

--
Regards, LVT.

> ак что берегитесь ! Скоро всех плагиаторов прищучим :)

А мы изобретаем параллельно с вами "иносказатель" математических текстов и "исказитель" математических же формул.
Так шта..

Сравнение строк. Найти похожие ветки