Comments 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.
UFO just landed and posted this here
Спасибо, за заметку, поправил в теле поста)
Также благодарю 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. План был в зависимости от входных параметров выбирать алгоритм. Но время защиты диплома подкралось незаметно и я так и не доделал программу.
В статье описан интересный алгоритм. Возможно, для некоторых входных параметров он может быть оптимальнее других.
В статье описан интересный алгоритм. Возможно, для некоторых входных параметров он может быть оптимальнее других.
Sign up to leave a comment.
Алгоритм параллельного поиска максимальных, общих подстрок в двух строках, и его имплементация на C++ (C++11)