Ваша задача - решить задачу Longest Common Subsequence для n строк длины 1000.
Действительное решение проблемы ЛВП для двух или более строк S 1 , ... S п любая строка T максимальной длины, что характеры Т появляются во всех S I , в том же порядке , как и в T .
Обратите внимание , что T не должен быть суб строка из S я .
Мы уже решили эту проблему в кратчайшем количестве кода . На этот раз размер не имеет значения.
пример
Строки axbycz
и xaybzc
имеют 8 общих подпоследовательностей длиной 3:
abc abz ayc ayz xbc xbz xyc xyz
Любое из них будет правильным решением проблемы LCS.
подробности
Напишите полную программу, которая решает проблему LCS, как описано выше, соблюдая следующие правила:
Ввод будет состоять из двух или более строк длиной 1000, состоящих из символов ASCII с кодовыми точками от 0x30 до 0x3F.
Вы должны прочитать вход от STDIN.
У вас есть два варианта формата ввода:
Каждая строка (включая последнюю) сопровождается переводом строки.
Строки объединены в цепочку без разделителя и без перевода строки.
Количество строк будет передано в качестве параметра командной строки вашей программе.
Вы должны записать вывод, т. Е. Любое из действительных решений для LCS, в STDOUT, за которым следует один перевод строки.
У вашего языка должен быть бесплатный (как у пива) компилятор / интерпретатор для моей операционной системы (Fedora 21).
Если вам требуются какие-либо флаги компилятора или специальный интерпретатор, пожалуйста, укажите это в своем посте.
счет
Я буду запускать ваш код со строками 2, 3 и т. Д., Пока для печати правильного решения не потребуется более 120 секунд. Это означает, что у вас есть 120 секунд для каждого значения n .
Наибольшее количество строк, для которых ваш код завершен вовремя, является вашим счетом.
В случае связанного числа n , представление, которое решило проблему для n строк в кратчайшие сроки, будет объявлено победителем.
Все представления будут приурочены к моей машине (Intel Core i7-3770, 16 ГБ ОЗУ, без подкачки).
В п струна (п-1) й тест будет генерироваться путем вызова rand n
(и зачистки перевода строки, если требуется), где rand
определяются следующим образом :
rand()
{
head -c$[500*$1] /dev/zero |
openssl enc -aes-128-ctr -K 0 -iv $1 |
xxd -c500 -ps |
tr 'a-f' ':-?'
}
Ключ находится 0
в приведенном выше коде, но я оставляю за собой право изменить его на нераскрытое значение, если я подозреваю, что кто-то (частично) жестко закодировал вывод.
источник
public static void main(...)
?Ответы:
C, n = 3 через ~ 7 секунд
Алгоритм
Алгоритм является прямым обобщением стандартного решения динамического программирования для
n
последовательностей. Для 2 строкA
иB
стандартное повторение выглядит так:Для 3 -х строк
A
,B
,C
я использую:Код реализует эту логику для произвольных значений
n
.КПД
Сложность моего кода O (s ^ n), с
s
длиной строк. Исходя из того, что я обнаружил, похоже, проблема в NP-полноте. Таким образом, хотя опубликованный алгоритм очень неэффективен для больших значенийn
, на самом деле может быть невозможно добиться больших успехов. Единственное, что я увидел, - это некоторые подходы, которые повышают эффективность для маленьких алфавитов. Поскольку здесь алфавит умеренно мал (16), это может привести к улучшению. Я все еще предсказываю, что никто не найдет законное решение, которое идет выше, чемn = 4
через 2 минуты, иn = 4
выглядит уже амбициозным.Я уменьшил использование памяти в первоначальной реализации, чтобы она могла обрабатывать
n = 4
достаточно времени. Но это только произвело длину последовательности, а не саму последовательность. Проверьте историю изменений этого поста, чтобы увидеть этот код.Код
Поскольку для циклов над n-мерными матрицами требуется больше логики, чем для фиксированных циклов, я использую фиксированный цикл для наименьшего измерения и использую только универсальную логику циклов для остальных измерений.
Инструкция по бегу
Бежать:
lcs.c
.Компилировать с высокими параметрами оптимизации. Я использовал:
В Linux я бы попробовал:
Запустите от 2 до 4 последовательностей, заданных в качестве аргументов командной строки:
При необходимости заключите в кавычки аргументы командной строки, так как алфавит, используемый для примеров, содержит специальные символы оболочки.
Полученные результаты
test2.sh
иtest3.sh
тестовые последовательности от Денниса. Я не знаю правильных результатов, но результат выглядит как минимум правдоподобным.источник
N_MAX
как макрос и добавить флаг компилятора,-std=c99
чтобы компилировать ваш код с помощью GCC.Этот ответ в настоящее время не работает из-за ошибки. Исправление скоро ...
C, 2 строки за ~ 35 секундЭто очень проделанная работа (о чем свидетельствует ужасная неразбериха), но, надеюсь, она даст хорошие ответы!
Код:
Соответствующая функция, которая выполняет все вычисления LCS, является функцией
LCS
. Приведенный выше код будет время собственного вызова этой функции.Сохранить как
main.c
и скомпилировать с:gcc -Ofast main.c -o FLCS
Код можно запустить либо с аргументами командной строки, либо через stdin. При использовании stdin он ожидает несколько строк, за которыми следуют сами строки.
Или же:
На компьютере Mac OS X с Intel Core i7 1,7 ГГц и тестовым набором, который предоставил Деннис, мы получаем следующий вывод для 2 строк:
Подход очень похож на мой подход к предыдущему вызову, здесь . В дополнение к предыдущей оптимизации мы теперь проверяем общее количество общих символов между строками в каждой рекурсии и рано выходим, если нет способа получить более длинную подстроку, чем уже существует.
На данный момент, он обрабатывает 2 строки в порядке, но имеет тенденцию к краху при большем. Больше улучшений и лучшее объяснение!
источник