#algorithm
#алгоритм
Вопрос:
Предположим, у нас есть два потока символов, подобных:
S = 1,2,3,5,7,4,4,10,11,12
T = 3,1,2,9,6,4,10,5,9
Я хочу найти самую большую подпоследовательность этих потоков, такую, чтобы они были одинаковыми при какой-либо перестановке, например, в этом случае 1,2,3 в первом и 3,1,2 во втором потоках, могут быть преобразованы друг в друга путем перестановки, и кажется, что это самая большая (с длиной 3).
Алгоритм для O (n ^ 2) доступен в алгоритмах квадратичного времени для нахождения общих интервалов в двух и более последовательностях.
Любая идея может быть реализована, нет необходимости ее улучшать, или, если у вас есть идея, докажите свою идею. Я хочу использовать is для получения результата в моей проблеме, временная сложность не подходит для моего текущего набора данных.
Комментарии:
1. Я думаю, что O (n ^ 2) — лучшее, на что вы можете надеяться (ну, технически это должно быть O (n * m), но если n = m, то это просто n ^ 2).
2. @JesusRamos да, вы правы, это O (m * n), но это для потоков, которые находятся в диапазоне 4000-5000, и на самом деле они находятся в том же порядке. но любая новая идея может помочь сделать это быстрее или, по крайней мере, разделить его на большую константу.
3. @SaeedAmiri: если вы не опубликуете свой текущий алгоритм, то устранение констант в нем практически невозможно.
4. @larsmans google «алгоритмы с квадратичным временем для нахождения общего интервала в двух и более последовательностях»
5. Нашел его, исправил ссылку.
Ответ №1:
2 вещи, которые вы можете сделать, чтобы ускорить это:
-
Убедитесь, что вы сравниваете их как целые числа, а не как строки (на всякий случай, если вы используете переработанный алгоритм, который использует сравнение строк, которое выполняется медленно).
-
Подход динамического программирования к этой задаче требует большой таблицы (m * n). Для продолжения рекуррентного соотношения требуется только текущая строка и предыдущая строка в таблице. Если вы используете эту оптимизацию, вам потребуется всего 2 * min (m, n) места для вычисления последовательности.
Как я уже говорил в своем комментарии выше, AFAIK, вы не можете сделать лучше, чем O (n * m), который может вырождаться в O (n ^ 2) для ввода одинакового размера. Эти оптимизации помогают только во времени сравнения и экономии памяти (поскольку, как вы заявили, в вашем худшем случае вам потребуется таблица ввода 5000 * 5000, которая занимает много памяти).
Комментарии:
1. Спасибо за ответ, но меня не волнует память, потому что 5000 ^ 2 символа в настоящее время невелики.
2. Тогда, если вы уже рассмотрели первый случай, это настолько быстро, насколько вы можете получить теоретически.
3. Мне потребовалось бы больше времени и места, чем у меня есть здесь, чтобы показать формальное доказательство, но поверьте мне, O (n * m) или O (n ^ 2) — это самое быстрое, что вы можете получить. Вы можете использовать дерево решений для доказательства теоретической нижней границы, показав, что требуется не менее такого количества уровней принятия решений, чтобы сказать, что вы нашли самую длинную последовательность. Решение для динамического программирования также вытекает из этого результата.
4. но я нашел более быстрый способ в среднем случае, это не очень быстро, это O (n ^ 2 / log n) амортизируется при нормальном распределении входных данных, но мое доказательство в настоящее время не завершено. На самом деле я согласен, что в худшем случае это не может быть лучше, чем O (n ^ 2), но в среднем случае это неверно.
5. Среднее время может варьироваться в зависимости от того, какую эвристику вы используете, чтобы знать, когда прекратить проверку в определенный момент. Дело в том, что доминирующий фактор по-прежнему равен n ^ 2, поэтому при большем вводе ваше время не будет сильно отличаться от стандартного алгоритма.
Ответ №2:
Я попробую.
Для обработки перестановки я буду использовать функцию f , которая сопоставляет набор целых чисел с одним и тем же значением независимо от их порядка. Конечно, возможны ложноположительные результаты, но вероятность одного из них очень мала. Одной из таких функций может быть следующая:
f(a1,a2,...,an) = Sum(ai^2) Sum(ai^3) Product(ai)
Вы могли бы использовать любую другую функцию, обладающую аналогичными свойствами.
Пусть n количество элементов в S и m количество элементов в T . Найдите минимум k между n и m . Теперь, начиная с k и возвращаясь назад до 1, получаем все подпоследовательности S и T и вычисляем f для этих подпоследовательностей. Если эти два fs совпадают, убедитесь, что подстроки равны. Если они есть, вы нашли максимальную общую подпоследовательность, которую хотите, если не продолжите.
Комментарии:
1. «Теперь, начиная с k и возвращаясь назад до 1, получаем все подпоследовательности S» В худшем случае требуется O (n! / (k! (n-k)!)). Т.е. решение с экспоненциальным временем. Чрезвычайно медленно.
2. Вы правы, если будете следовать итеративному подходу. Но вы можете сделать это за O (n ^ 2), если создадите суффиксное дерево для S и второе дерево для T. В каждом узле дерева вы можете сохранить частичную сумму значений подпоследовательности f, ведущих к этому узлу. Теперь вам просто нужно найти самые глубокие узлы одинаковой высоты в обоих деревьях, которые имеют одинаковые значения. Поскольку обход дерева может быть выполнен за O (N) (где N узлов в дереве), решение может быть найдено за квадратичное время.
3. 1 спасибо, следует подумать о вашей идее, чтобы посмотреть, как ее можно расширить, может быть, это полезно для меня. но я думаю, что следует найти лучшую функцию, более быструю для вычислений и большую уникальность.