Python-сообщество

Всем привет!
Решаю задачу по поиску наибольшего общего подмассива в 2-х массивах. Длина массивов одинаковая.
Написал алгоритм, у меня на машине отрабатывает за 4 секунды на массивах из 1000 элементов, что наверное очень долго. Но тесты не проходит, пишет, что превышено время выполнения.
Алгоритм вроде верный, но долгий.
Можно ли как-то ускорить код, или подсказать узкие места в коде?
Код:

Всем большое спасибо!

artemu88
Можно ли как-то ускорить код, или подсказать узкие места в коде?

От строк надо избавиться.

artemu88
склеиваем массив через разделитель

Не надо ничего склеивать.

Надо сделать индексы в массиве в виде чисел и чисто на них исследовать массив.

py.user.next
От строк надо избавиться.

понял, пойду думать, как исправить. Просто решил склеивать массив в строки, чтобы было легче искать в другом массиве ( про помощи оператора in, чтобы получилось что-то типа оператора LIKE в других языках), для этого также добавил пробелы в начале и в конце массива.
Спасибо!

artemu88
Решаю задачу по поиску наибольшего общего подмассива

Это задача на тему динамического программирования, почитайте

xam1816
Это задача на тему динамического программирования

Не, там просто по индексам перебираешь первый массив и находишь входы во втором массиве. При нахождении входа идёшь по совпадающим элементам. Самый длинный массив запоминаешь по позиции и по длине.

Это ты просто перепутал похожие понятия: подстрока и подпоследовательность.
wiki. поиск подстроки
wiki. поиск подпоследовательности

Обратите внимание! Подпоследовательность отличается от подстроки. Например, если есть исходная последовательность “ABCDEF”, то “ACE” будет подпоследовательностью, но не подстрокой, а “ABC” будет как подпоследовательностью, так и подстрокой.

Отредактировано py.user.next (Авг. 1, 2024 01:03:41)

artemu88
Просто решил склеивать массив в строки, чтобы было легче искать в другом массиве ( про помощи оператора in, чтобы получилось что-то типа оператора LIKE в других языках)

Это ошибка новичков всех. Они думают, что делают что-то такое умное прямо, до чего бы никто не догадался, но в итоге почти каждый из них делает вот это. Так что ты не первый, кто столкнулся с суровой реальностью.

Понимаешь, когда есть задачи, особенно в реальном мире, не учебные, там нет ограничений на количество элементов. Тебе дали задачу на тысячу элементов, а ты её сразу должен расширить до миллиона элементов в уме и сделать, исходя из этого. В реальности же там может быть вообще бесконечное число элементов (пакеты внутри сети домофона или показания датчика температуры в офисе или сообщения пользователей в группе), из которых надо вот так что-то найти на любом временном этапе.

Поэтому ты не должен работать с числами как со строками и со списками как со строками. Что если списки станут не списками чисел, а списками пакетных объектов из томографа? А ведь алгоритм, его реализация, должен быть написан один раз и потом без переписываний применяться многократно. Сегодня - к тысяче чисел, завтра к ста тысячам строк, послезавтра - к миллиону сетевых пакетов, послепослезавтра - к бесконечному числу векторов в каком-нибудь анализаторе.

Что касается технического момента, тут тоже есть различия. Во многих языках строки хранятся не так, как хранятся числа. Чаще всего строки хранятся непрерывно в памяти, символ за символом, как массив. Также, например, число 1000000 занимает четыре байта, а строка 1000000 занимает семь байт. Уже есть разница, хотя это на вид одно и то же. То же самое по структурам самим. Список - это набор указателей на элементы. Реализовать такой набор указателей можно по-разному. Но факт в том, что, работая с указателями, ты можешь объединить в один большой список разные маленькие участки памяти, не затрагивая их границы. Со строкой же, которая по своей структуре представляет из себя массив символов, тебе нужно сначала найти непрерывный кусок в памяти такого размера, а если его нет, то надо сначала провести освобождение памяти, чтобы высвободить много мелких кусков памяти, стоящих рядом, и после этого объединить их в один большой свободный кусок памяти, в котором поместится вся эта строка. Из-за этого всего операции со строками становятся медленными, неповоротливыми, требуют дополнительных манипуляций и, соответственно, времени и памяти на это всё.

Так что это не хак, а новичковая ловушка. Конечно, есть и хаки на базе строк. Я видел такой хак, когда читал исходный код программы cat в GNU/Linux. Там опция -n, выводящая номера строк, делает это через строку, хотя вроде число выводится. Просто для бесконечности строк они так сделали там, чтобы длинную арифметику не делать. Но такие хаки, как и goto повсеместный в коде такого же уровня, - это дело профессионалов достаточно глубокого уровня, на котором тебя не спросят, что ты такое делаешь и можно ли так делать вообще, потому что новичков там не встретишь и все всё видят и понимают без слов.


tags: list string

Отредактировано py.user.next (Авг. 1, 2024 10:16:51)

Всем большое спасибо!
Пойду учить матчасть.