Ru-Board.club
← Вернуться в раздел «Прикладное программирование»

» Сравнение двух строк

Автор: D0minus
Дата сообщения: 17.11.2005 14:30
Здравствуйте
У меня возникла такая задача.
Есть две строчки a1 и a2 одинаковой длины n. Элементы строк - целые числа, от 1 до M, упорядочены по возрастанию, повторов в строчке нет. Требуется найти число одинаковых элементов в двух строках, и указать позиции отличающихся элементов. Если в ходе сравнения выясняется, что разных элементов больше 4, то их позиции можно не находить.

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

Навскидку я придумал два алгоритма.
1. Проходить одновременно две строки, сравнивать текущие элементы и сдвигаться на различных. Если сдвигов больше двух - прекращать.
2. Развернуть каждую строчку a_i в строку q_i длины M, записать едининички в позиции, номер которых равен значениям элементов a. Разность строк q1 и q2 содержит \pm единички как раз там, где были отличающиеся элементы. Остается воспользоваться поиском.

Первый алгоритм, хотя и использует упорядоченность элементов и ограничение по числу различий, работает медленнее, чем второй, at least, в интересующей меня области параметров n=10, M=30.

Оба, тем не менее, зарезают производительность всей программы. Пожалуйста, подскажите наиболее быстрый способ сравнения для моей задачи. Спасибо!

p.s. Происхождение задачи: строчки суть сочетания из M по n, определяют возбужденные состояния в многочастичной системе, и сравниваются при вычислении гамильтониана.
Автор: Glukodel
Дата сообщения: 17.11.2005 17:21
http://fastcode.sourceforge.net/fastcodeproject/index.htm
там и строки и математика и работа с памятью....... все отбиралось из нескольких вариантов - оставлся самый оптимальный....
там даже таблички ексельные мона скачать - что бы увидеть, чей вариант в каких случаях лучше.......... (не всегда победитель лидировал во всех тестах).....
Автор: D0minus
Дата сообщения: 17.11.2005 23:07
Glukodel
Спасибо Вам
Я скачал код, разбираюсь теперь.

Страницы: 1

Предыдущая тема: Задачи на Visual Basic (VB).


Форум Ru-Board.club — поднят 15-09-2016 числа. Цель - сохранить наследие старого Ru-Board, истории становления российского интернета. Сделано для людей.