Решил задачу 427D - Расшифровка сигнала с помощью суффиксного дерева. Однако мое решение за O(N) (6579114) работало дольше, чем решения за O(n2) — 717 мс и кушало ~200 мб памяти!
Сразу нашелся тест, на котором локально это решение работало долго (около 5,8 секунды!!!):
aaa...aa
aaa...aa
Стал разбираться. Выяснилось, что по ходу построения дерева, создается ~12,5 млн. позиций в дереве (объект, который указывает на вершину в сжатом боре). Эти объекты я создавал в куче, через new. Это удобно тем, что можно вернуть указатель на NULL (например, при попытке перехода из вершины по символу).
Я, конечно, знал, что выделение памяти в куче работает дольше, чем на стеке, но не в 15 же раз! :) Вообще, изначально я хотел избавиться от new из-за лишнего потребления памяти: в каждой позиции хранится указатель на вершину(4 байта) + номер буквы на ребре(4 байта) * 12,5 млн. ≈ 100 мб.
В итоге без использования new мое решение получило AC (6579111) за 171 мс, при этом потребляя 2 мб памяти.
У меня только 2 вопроса:
Почему 200 - 100 = 2
И почему локальное время выполнения так сильно отличается от серверного(без new стало работать быстрее на 1 секунду, но 4,8 и 0,17 — все же большая разница)
Заранее спасибо
Comments (0)
