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

← →
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"

← →
Anatoly Podgoretsky © (2012-11-05 21:25) [29]

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

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

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

> Jimmy (05.11.12 21:14) [28]

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

← →
Anatoly Podgoretsky © (2012-11-05 21:26) [31]

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

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

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

> 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

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

← →
DVM © (2012-11-05 22:08) [34]

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

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

← →
DVM © (2012-11-05 22:11) [35]

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

То что код

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

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

← →
AV © (2012-11-06 09:21) [36]

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

← →
sniknik © (2012-11-06 09:36) [37]

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

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

← →
Rouse_ © (2012-11-06 10:21) [38]

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

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

← →
Медвежонок Пятачок © (2012-11-06 13:25) [39]

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

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

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

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

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

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

← →
И. Павел © (2012-11-07 16:27) [41]

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

Это не минус, а норма для хеш-функций.

← →
MsGuns © (2012-11-07 17:01) [42]

>Не, это просто какая-то Жопа.

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

ХЗ, я так даже будучи скубентом 2-го курса не писал - сразу двубалили за такое.
Суперизбыток кода, масса тавтологий, имена переменных и функций...
Короче, не Жопа, а Ж О П А.

Я не знаю, что Медвежонок имел в виду, но я бы за стиль просто выгонял бы в дворники таких "умельцев" :)

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

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

а что скажет первый вариант на случай, когда St1 или St2 содержит пустую строку?

← →
DVM © (2012-11-07 18:16) [44]

> MsGuns © (07.11.12 17:01) [42]

Ой, да ладно. Высосано из пальца все. Все перечисленные недостатки как то имена функций, типы на первый взгляд лишние - есть результат портирования оригинального кода Си на паскаль с максимальным сохранением имен. Оставлены осознанно, а не по недосмотру/незнанию.

Медвежонок имел в виду, что в WinApi есть Com обертка к некоторым функциям CryptoApi которая умеет вычислять хэши. Обертка для делфи имхо неудобная.

← →
Dennis I. Komarov © (2012-11-07 18:42) [45]

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

Фи, как не педагогично :)
2 бита на масть, 3 на вес (если не ошибаюсь там 32 листа).
+ еще 3 бита на состояние остается

> ХЗ, я так даже будучи скубентом 2-го курса не писал - сразу
> двубалили за такое.

Я так думаю исходники оригинальной Cryptoapi ваших преподавателей минимум бы ввергли бы в ступор :))
У DVM-а в принципе практически один в один с оригиналом, разве что с учетом уклона в дельфю.

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

> Jimmy

если делать так как предложил я, то перебор всех вариантов у тебя будет в сотни раз быстрее. да и вообще это будет самое быстрое решение, так как переборов ВСЕХ вариантов не нужно.

← →
Очень Злой (2012-11-07 20:30) [49]

Я не понял. а задаче автора сравнение строк вообще для чего нужно? для поиска? если да, то не проще ли проиндексировать это все и искать по индексу?

> Я не понял. а задаче автора сравнение строк вообще для чего
> нужно?

Да не нужно, велосипед будет ;)

З.Ы.
Автору: Пример строки с расшифровкой в студию...

> Так что шутки с бабиной неуместны, причем уже не в первый раз.
всегда уместны, при голословных, без подтверждения утверждениях о чем-то хорошо всем известном и удовлетворяющем... но не подходящим автору.

← →
Очень злой (2012-11-07 23:21) [52]

> Jimmy (05.11.12 20:26) [13]
>
> Создаю хэш таблицы при игре в преферанс на открытых картах.
> Запоминаю карты всех трех игроков на анализе определенного
> хода и результат этой "позиции", и если далее встречается
> такая же ситуация - пользуюсь уже готовым результатом. Проблема
> в том, что сравнивая имеющиеся карты с теми, что хранят
> хэш-таблицы уходит много времени. Пока сравниваю строки.
>

Хм. В преферансе 32 карты. Т.е. для хранения карт всех трех игроков достаточно 64 битного числа.
2 бита на 1 карту т.е.
01 карта у первого игрока
10 - карта у второго игрока
11 - карта у третьего игрока
00 - карта не у игроков

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

Выход считаем что у первого игрока.

получается 8 байт, и зачем тогда нужен какой-то хеш?

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

Ну это конечно если я правильно понимаю задачу.. Хотя не уверен на 100%, что правильно ее понял.

← →
Очень злой (2012-11-07 23:25) [53]

да, пардон, забыл что еще нужно хранить инфу о еще 2-х картах (выходы первого и второго игроков. но для этого достаточно еще 10 бит, хотя в принципе можно подумать как ее вместить в те 64 бита (где информация и так вроде как избыточная)

← →
Очень злой (2012-11-07 23:46) [54]

да. и еще 2 бита нужны для:
00 - обычная игра
01 - без козырей
10 - распасовка
11 - мизер

ну и байты (вернее слова) отвечающие за условные масти (те, что не являются козырем) размещать например в порядке возрастания.

> Очень злой (07.11.12 23:21) [52]

нечто подобное я и предлагал. относительно давно. но что может сравнится с хэшем! к чему какие-то примитивные древовидные поиски по простым байтам.

>Rouse_ © (07.11.12 19:20) [47]
>Да и кстати, раз уж данный стиль плохой (ничего что я политкорректно? :) >хотелось бы увидеть реализацию любого криптоалгоритма в исполнении >противников данного стиля :)

Стесняюсь спросить, а чем стиль реализации криптоалгоритма принципиально отличается от стиля реализации любых иных алгоритмов ?
И еще вопрос.
Если написано такое:

if ((a == 0) ||
(a == 1) ||
(a == 2) ||
...
(a == 999)) {}

то прежде чем сделать выводы о СУТИ написанного (в данном случае тупой проверки числа на положительное целое до тыщи), надо въехать в глобальную суть ВСЕГО проекта ?

Или "жена Цезаря вне подозрений" ?

← →
Очень Злой (2012-11-08 12:50) [57]

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

> MsGuns © (08.11.12 12:48) [56]

> Если написано такое:
>

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

Я код не приводил как образец, он не претендует на идеал, он работает, способен выполнить задачу озвученную автором вопроса максимально просто, работает стабильно.
Визуальную привлекательность и читабельность его как и любого криптоалгоритма, улучшить сложно. Осмысленные имена функциям _F, _G, _H, FF, GG дать просто невозможно, т.к. невозможно кратко и понятно описать смысл действий, которые они производят (в основном битовые операции и сдвиги). В оригинале это было макросами си.

> Стесняюсь спросить, а чем стиль реализации криптоалгоритма
> принципиально отличается от стиля реализации любых иных
> алгоритмов ?

Та лехко - в крипто обычно происходит куча трансформов/перестановок.
описать их осмысленно не представляется возможным. Как собственно и произвести рефакторинг кода в читабельный вид.
Нет ну конечно можно писать функции вида:
СдвинутьПятыйБитВлевоНаЗначениеПервыхТрехБитовИПрибавитьВосемь() и так раз тридцать подряд на каждый тип трансформа, но это будет абсолютно не читабельно :)

А по поводу сути алгоритма - тут еще проще, данные алгоритмы описаны целиком и полностью, и вникнуть в них на порядок проще чем в какую-то самопальную псевдокрипту.

По поводу вопроса - это уже из серии индусского кода.

> MsGuns ©

Вот кстати тот оригинальный код MD5: http://tools.ietf.org/html/rfc1321
Официальный документ между прочим. Прошу обратить внимание на имена макросов и прочие дефайны и сравнить. Если взять все и переименовать, то сопоставить написанное на паскале с RFC будет на порядок сложнее в случае проблем. Зачем спрашивается.

>Rouse_ ©
>DVM ©

Перевод стрелок и раздача слонов.
Как обычно.

Далее дискутировать бессмысленно, ибо налицо переход на аргументы "сам дурак".

> MsGuns © (08.11.12 23:19) [61]

Не я начал дискуссию со слова ЖОПА. Не, даже так, Ж О П А. Вообще это отлично Вас характеризует.

← →
Коллект (2012-11-09 01:22) [63]

> MsGuns © (08.11.12 23:19) [61]

Экстра-фат троллинг детектед!

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

RFC 1321 датируется апрелем 1992 года, а 21 июня 1991 года (20 лет назад) он существовал только в головах и записях Ривеста и соратников.

Впрочем, тебе никто не мешает самому взять, да написать офигительный криптоалгоритм с изящными витиеватыми названиями функций, типа, SchwaineAlgoritmForIdiots(). Так что иди, пиши! Пока не напишешь - не возвращайся даже!

P.S. Прошу прощения у присутствующх за моветон...

> MsGuns © (08.11.12 23:19) [61]
> Перевод стрелок и раздача слонов.
> Как обычно.

Кода, как я понимаю, не будет?
Зачем тогда выпендриваться было?

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