Как быстро сравнить две строки?

← →
Jimmy (2012-11-05 19:36) [0]

Подскажите, как можно быстро сравнить две строки? (Быстрее, чем St1=St2.) Заранее спасибо!

← →
brother © (2012-11-05 19:46) [1]

эээ, быстрее чем посимвольно не будет имхо...

← →
Медвежонок Пятачок © (2012-11-05 19:47) [2]

А приведенный способ типа медленный?

← →
Jimmy (2012-11-05 20:00) [3]

if (St1[1]=St2[1])then
if (St1=St2)then ...
работает быстрее, чем
if (St1=St2)then ...
Значит второй вариант уже не самый оптимальный

← →
Очень Злой (2012-11-05 20:03) [4]

> if (St1[1]=St2[1])then
> if (St1=St2)then ...
> работает быстрее, чем
> if (St1=St2)then ...

Очень сомневаюсь

← →
DVM © (2012-11-05 20:06) [5]

> Jimmy (05.11.12 20:00) [3]
> if (St1[1]=St2[1])then
> if (St1=St2)then ...
> работает быстрее, чем
> if (St1=St2)then ...

В частных случаях он быстрее, в общем чуть медленнее даже.

Длину можно еще сравнивать. Не равна длина строки точно не равны.

← →
Jimmy (2012-11-05 20:10) [6]

Тогда такой вопрос: как можно быстро по строке однозначно определить какой-нибудь ее код в виде числа? Кажется, это называется, хэш-суммой. Хэш-суммы я могу определить заранее, когда дело дойдет до сравнения они уже будут известны.

← →
DVM © (2012-11-05 20:14) [7]

Для того чтобы вычислить хэш придется пробежаться по всей строке. А это не быстро весьма может быть. А хэшей полно разных MD5 SHA-1 и т.д. На крайний случай банальный CheckSum, но он много коллизий даст - одних и тех же значений для разных строк.

← →
kilkennycat © (2012-11-05 20:15) [8]

вообще вопрос слишком общий, и потому бессмысленный без контекста.

← →
Jimmy (2012-11-05 20:16) [9]

Можно поподробней про MDS, SHA-1. Где можно найти код?

← →
Медвежонок Пятачок © (2012-11-05 20:18) [10]

в msdn

← →
kilkennycat © (2012-11-05 20:21) [11]

во, выясняется, что есть возможность предварительного хэширования. потом высянится, что это поиск по некоему справочнику. и что строка ввода не бывает менее N символов. И в конечном итоге сведется к проблеме тормозов клавиатуре в едите.
Автор, огласите весь список, пожалуйста (с)

← →
DVM © (2012-11-05 20:24) [12]

> Где можно найти код?

http://dvmuratov.narod.ru/uSHA1.pas
http://dvmuratov.narod.ru/uMD5.pas

← →
Jimmy (2012-11-05 20:26) [13]

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

← →
kilkennycat © (2012-11-05 20:29) [14]

прикольно. это как, карты имеют строковый идентификатор? байта мало?

← →
Jimmy (2012-11-05 20:31) [15]

>DVM
Большое спасибо, еще бы пример использования... Я не знаю, что такое класс.

← →
Медвежонок Пятачок © (2012-11-05 20:32) [16]

http://dvmuratov.narod.ru/uMD5.pas

Не, это просто какая-то Жопа.
И это написано в 2011 году.

А сейчас еще и расползется по неокрепшим умам.

← →
Jimmy (2012-11-05 20:35) [17]

kilkennycat ©
Хорошо, как зная массив байтов получить контрольную сумму?

← →
DVM © (2012-11-05 20:37) [18]

> Медвежонок Пятачок © (05.11.12 20:32) [16]

да неужели? ну ка аргументируй.

← →
Медвежонок Пятачок © (2012-11-05 20:41) [19]

да какие ту могут быть аргументы?
у тебя поди весь win32 апи на вело-паскале есть.

← →
DVM © (2012-11-05 20:44) [20]

> Медвежонок Пятачок © (05.11.12 20:41) [19]

Я так и думал, что у тебя нет аргументов. А жопа у тех вместо головы, кто думает, что связкой Win32/Delphi ограничивается круг применения кода на паскале. Использую в Lasarus под Linux без проблем, нету там WinApi. Да, в Linux есть библиотеки для вычисления хэшей, но это лишние зависимости, хидеры все равно переводить.

← →
Медвежонок Пятачок © (2012-11-05 20:47) [21]

А кто здесь говорил про проблемы?
Ты не переживай, лет 20 назад я точно так же бы юзал такие модули.

← →
kilkennycat © (2012-11-05 20:50) [22]

> Jimmy (05.11.12 20:35) [17]

не нужна в этом случае контрольная сумма. нужно лишь однозначное правило формирования данных.
например:
1) карты нумеруются сквозной нумерацией.
2) запись набора идет от меньших карт к большим.

← →
Jimmy (2012-11-05 20:50) [23]

DVM
Очень бы хотелось пример использования, извините, что злоупотребляю Вашим вниманием.

← →
DVM © (2012-11-05 20:55) [24]

> Jimmy (05.11.12 20:50) [23]

> Очень бы хотелось пример использования

Да там уж проще некуда все:

var
Digest: TMD5Digest;
...
Digest := TMD5.Calculate("твоя строка");

← →
DVM © (2012-11-05 20:57) [25]

> Медвежонок Пятачок © (05.11.12 20:47) [21]

ты еще скажи, что ты msxml 20 лет назад юзал

← →
Jimmy (2012-11-05 21:09) [26]

DVM
Digest1,Digest2:TMD5Digest;
Что следует сравнивать?
Digest1.A=Digest2.A?

← →
DVM © (2012-11-05 21:11) [27]

> Jimmy (05.11.12 21:09) [26]

if TMD5.DigestCompare(Digest1,Digest2) then
они одинаковые

← →
Jimmy (2012-11-05 21:14) [28]

Ошибка "Integer Overflow"

> Jimmy (05.11.2012 20:00:03) [3]

В первом случае нет сравнения строк, поэтому пример бессмысленный, а если
рассматривать эти две строки как целое, то еще и мделеннее

> Jimmy (05.11.12 21:14) [28]

У меня нет никаких ошибок. Приводи весь код.

> DVM (05.11.2012 20:06:05) [5]

Думаешь сравнение иначе делается?

> Anatoly Podgoretsky © (05.11.12 21:26) [31]

> Думаешь сравнение иначе делается?

Думаю, что где то в другом месте у него ошибка (возможно в моем коде, т.к. на D7 я не проверял), в коде TMD5.DigestCompare ошибке подобной описанной возникать негде.

← →
Очень Злой (2012-11-05 22:05) [33]

> В частных случаях он быстрее, в общем чуть медленнее даже.
>

Почему?
Вроде как само сравнение St1=St2 должно осуществляться посимвольно начиная с первого и при несовпадении очередного символа сразу сказать что строки не равны, не пробегаясь далее по остальным символам...

и тогда код

if (St1[1]=St2[1])then
if (St1=St2)then ...

должен работать всегда не быстрее сравнения St1=St2

Или я что-то не правильно понимаю?

> Или я что-то не правильно понимаю?

если строки окажутся не равны и это выяснится на последнем символе, то плюс к общему времени прохождения по строке будет добавлена еще операция сравнения первых символов. Итого первые символы будут проверены дважды.

> Очень Злой (05.11.12 22:05) [33]

То что код

if (St1[1]=St2[1])then
if (St1=St2)then ...

оказался быстрее при условиях автора вопроса я принял на веру, иначе чего он спрашивает вообще. Это и есть частный случай. Проверять во что компилируется выражение St1=St2 надо.

Мысля
Когда писали компилятор, они что, думали "А давайте напишем как нибудь потормознее что бы было, если пишут"
St1=St2
Тем более, в паскале строки - фишка паскаля. Тем более, базовая. Тем более, эти операции медленные. Наверняка, все продумали.
Если что-то выкинуть, "для оптимизации", рванет в другом месте

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

имхо, "дело не в бобине".

> Медвежонок Пятачок © (05.11.12 20:47) [21]
> А кто здесь говорил про проблемы?
> Ты не переживай, лет 20 назад я точно так же бы юзал такие
> модули.

А сейчас АПИ юзаешь? Ну-ну...

Я уже испугался и приготовился к неприятностям

← →
Jimmy (2012-11-07 16:10) [40]

> sniknik
Точно не считал, но даже с учетом альфа-бета отсечения десятки-сотни тысяч, если не больше. Если не верите, такой факт: лучшая программа для игры в Преферанс Макарова по крайней мере в первых версиях думала еще дольше. Так что шутки с бабиной неуместны, причем уже не в первый раз.

> DVM
Да, ошибку выдавала какая-то другая дочерняя функция.

А проблему решил так: нашел код на ассемблере в справке "DelphiWord 2006" определения хеш-суммы строки. Ее небольшой минус в том, что она может иногда разным строкам поставить в соответствие одинаковые числа, но это мелочи. Быстродействие увеличилось очень сильно, причем это позволило увеличить количество хеш таблиц что привело еще к более быстрому раздумью над ходом. И теперь я понял почему мои попытки использовать хеш таблицы в шахматах только увеличивали машинное время - проблема была та же.

Всем спасибо за помощь.

Как быстро сравнить две строки? Найти похожие ветки