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

← →
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 бита на состояние остается

← →
Rouse_ © (2012-11-07 19:10) [46]

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

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

← →
Rouse_ © (2012-11-07 19:20) [47]

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

← →
kilkennycat © (2012-11-07 19:59) [48]

> Jimmy

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

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

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

← →
Dennis I. Komarov © (2012-11-07 20:38) [50]

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

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

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

← →
sniknik © (2012-11-07 21:22) [51]

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

← →
Очень злой (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 - мизер

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

← →
kilkennycat © (2012-11-08 01:23) [55]

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

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

← →
MsGuns © (2012-11-08 12:48) [56]

>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]
> Перевод стрелок и раздача слонов.
> Как обычно.

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

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