Комментарии 26
Интересно, сам не участвовал в этом конкурсе, но по причине, что мне не понравилось условие задачи ( сделать то, что делает код жури. ИМХО это скучно и не интересно ).
Так же, если я правильно понял, то вы неверно поняли условие. Так как авторское решение ищет именно такие позиции, которые нельзя как-то сдвинуть вправо, что ещё больше теряет для меня интерес к задаче.
В вашем условии всё гораздо приятнее, и тут можно придумать множество решений. Например те же хэши, или даже распаралелленное суффиксное дерево.
И да, важный факт тут, использовать число M, потому как некоторые участники тупо на него забивали, а ведь если это число большое, решение, эффективно использующее M, будет работать куда шустрее.
У вас интересное решение, и оно как раз тоже использует M, что хорошо.
Могу ли я вас попросить в конце добавить оценку сложности времени выполнения и потребления памяти для вашего решения, так будет видно ещё больше насколько оно хорошее или плохое в отношении к другим решениям. Спасибо :)
Так же, если я правильно понял, то вы неверно поняли условие. Так как авторское решение ищет именно такие позиции, которые нельзя как-то сдвинуть вправо, что ещё больше теряет для меня интерес к задаче.
В вашем условии всё гораздо приятнее, и тут можно придумать множество решений. Например те же хэши, или даже распаралелленное суффиксное дерево.
И да, важный факт тут, использовать число M, потому как некоторые участники тупо на него забивали, а ведь если это число большое, решение, эффективно использующее M, будет работать куда шустрее.
У вас интересное решение, и оно как раз тоже использует M, что хорошо.
Могу ли я вас попросить в конце добавить оценку сложности времени выполнения и потребления памяти для вашего решения, так будет видно ещё больше насколько оно хорошее или плохое в отношении к другим решениям. Спасибо :)
Код жюри задачу не решает. При вполне практических по размерах входных строках он работает года (лучшие решения — меньше минуты).
И да, важный факт тут, использовать число M, потому как некоторые участники тупо на него забивали, а ведь если это число большое, решение, эффективно использующее M, будет работать куда шустрее.
Кстати, заметил что скорость референсного кода, практичеки, не зависит от M, конечно я понимаю что сравнивать референсный код с реализацией этого алгоритма — не корректно, но всеже это удивило)
Могу ли я вас попросить в конце добавить оценку сложности времени выполнения и потребления памяти для вашего решения, так будет видно ещё больше насколько оно хорошее или плохое в отношении к другим решениям. Спасибо :)
Если допустить, что M — константа (хотя от этого параметра сильно зависит скорость), то, если я не ошибаюсь, суммарная сложность будет:
O((N1 — M + 1) * N2) + O step3 = O(N1 * N2) + O step3, где N1, N2 — длина первой и второй строк соответственно; O step3 — сложность шага 3.
Пока что не могу точно сказать какова сложность шага 3, так как тут идет не совсем прямая зависимость от N1, N2.
НЛО прилетело и опубликовало эту надпись здесь
Спасибо, за заметку, поправил в теле поста)
Также благодарю Lockal, за то что указал на ошибки пунктуации.
Также благодарю Lockal, за то что указал на ошибки пунктуации.
Скажите, Вы разве ушли куда-то от квадратичной сложности? Основной поток решений задачи на форуме конкурса был на суффиксных структурах данных (дерево, автомат, массив), дающих логарифмическую сложность.
Если очень захотеть, то линейную. Хотя, к примеру, мои линейные наброски с суффиксным автоматом едва ли можно было как-то осмысленно распараллелить иначе чем в обработке всех тестов из входных данных. Интересно, как это у других участников.
Скажите, Вы разве ушли куда-то от квадратичной сложности?
Нет конечно, не ушел)
Основной целью было разработать и реализовать алгоритм, который хорошо параллелится. Как я и написал в «Заключении» — алгоритм пришел мне на ум почти сразу же после прочтения условия задачи, конечно это были только наброски, без деталей. После этого удалось более детализировать и более выгодным образом его распараллелить.
Плюсанул, бо код очень нравится, так сказать, максимум "++11"
мне алгоритм понравился, но я наверно бы решал «в лоб»:
1) взял бы строку и разбил бы её на n-частей (по потоку на каждую часть)
тут есть маленькая тонкость — части должны перекрываться как минимум на кол-во символов в сегменте подстроки (2-3 символа).
2) каждую часть начал бы параллельно проверять на вхождение первого сегмента.
3) если бы первый сегмент вошел — то запустил новый поток на проверку всей подстроки или следующего сегмента.
1) взял бы строку и разбил бы её на n-частей (по потоку на каждую часть)
тут есть маленькая тонкость — части должны перекрываться как минимум на кол-во символов в сегменте подстроки (2-3 символа).
2) каждую часть начал бы параллельно проверять на вхождение первого сегмента.
3) если бы первый сегмент вошел — то запустил новый поток на проверку всей подстроки или следующего сегмента.
Поздравляю, вы практически изобрели BLAST алгоритм :)
Очень активно применяется в генетике для анализа последовательностей.
en.wikipedia.org/wiki/BLAST
Очень активно применяется в генетике для анализа последовательностей.
en.wikipedia.org/wiki/BLAST
А можете подсказать какой-нибудь классический алгоритм поиска в первой строке максимальной подстроки, которая соответствует началу второй строки? Т.е. у нас есть строки S1 и S2, и надо в S1 найти максимальную подстроку, которая является началом S2.
FASTA вам поможет en.wikipedia.org/wiki/FASTA, это классика.
Для своей задачи можете просто ввести туда ограничения.
Для своей задачи можете просто ввести туда ограничения.
Ночью туго соображаю, но почему-то кажется, что можно чуть-чуть подправить классический алгоритм Кнута-Морриса-Пратта, что работает за O(|S1|+|S2|). Собственно, алгоритм ищет префиксы строки S2 в строке S1, заканчивая работу, когда/если префикс достигает длины S2, — вам же нужно запомнить самый длинный совпавший префикс, то бишь изменить один if.
Можно искать проекции хешированием. Поскольку у нас фиксированная длинна M, можно преподсчитать все хеши подстрок S2 длины M, а потом при проверке высчитать хеш нужной для проекции строки и сразу узнать позиции. Итого — O(|S2|) на препроцесс и O(M+log|S2|)
Возникала подобная мысль, только я хотел использовать хеш-таблицу или что-нибудь подобное для кеширования уже найденных проекций сегментов. Но идею отложил в сторону, так как, пока что не нашел метода, как параллельно, без блокировок, строить кеш.
Если конечно Ваше решение как-нибудь возможно распараллелить, то будет отлично, в противном же случае у нас появится последовательный участок, который, несмотря на то что в последовательном режиме может дать большой прирост всему алгоритму, в параллельном думаю может снизить эффективность (закон Амдаля).
Если конечно Ваше решение как-нибудь возможно распараллелить, то будет отлично, в противном же случае у нас появится последовательный участок, который, несмотря на то что в последовательном режиме может дать большой прирост всему алгоритму, в параллельном думаю может снизить эффективность (закон Амдаля).
Вы сами строите хеш-функцию.
Скажем F(pos) = Spos * p0 + Spos+1 * p1 +… + Spos+M-1 * pM-1
для pos = 0..|S|-M
p — простое число. желательно первое после количества букв в алфавите, тоесть 29 или 31. Функцию можно взять по модулю большого числа. Преподсчитываем за линию еще до вычислений для обоих строк.
Теперь, когда мы берем подстроку строки S2 — это преподсчитанное значение нашей функции. O(1). Нужно определить, в каких позициях это число находится в строке S. Это тривиально, так как работаем мы уже с числами, а не со строками.
Скажем F(pos) = Spos * p0 + Spos+1 * p1 +… + Spos+M-1 * pM-1
для pos = 0..|S|-M
p — простое число. желательно первое после количества букв в алфавите, тоесть 29 или 31. Функцию можно взять по модулю большого числа. Преподсчитываем за линию еще до вычислений для обоих строк.
Теперь, когда мы берем подстроку строки S2 — это преподсчитанное значение нашей функции. O(1). Нужно определить, в каких позициях это число находится в строке S. Это тривиально, так как работаем мы уже с числами, а не со строками.
> Поскольку у нас фиксированная длинна M
В условии дана минимальная длина ответа M. То бишь она не фиксирована, а подстрок и их хешей все еще порядка квадрата длины строки.
В условии дана минимальная длина ответа M. То бишь она не фиксирована, а подстрок и их хешей все еще порядка квадрата длины строки.
Хотел поучавствовать в конкурсе, даже реализовал прототип, который использовал 2 алгоритма — суффиксный массив и еще один простой квадратичный алгоритм, но который использовал SSE4.2. План был в зависимости от входных параметров выбирать алгоритм. Но время защиты диплома подкралось незаметно и я так и не доделал программу.
В статье описан интересный алгоритм. Возможно, для некоторых входных параметров он может быть оптимальнее других.
В статье описан интересный алгоритм. Возможно, для некоторых входных параметров он может быть оптимальнее других.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм параллельного поиска максимальных, общих подстрок в двух строках, и его имплементация на C++ (C++11)