Решил задачу 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 — все же большая разница)
Заранее спасибо
Погуглите про такую вещь, как менеджер памяти. Именно он и отжирает дополнительные 100МБ для своей работы.
Вероятно, локально Вы компилируете решение без оптимизации. Добавьте ради интереса флаг -O2 и сравните результат.
Оффтопик: Вы пользуетесь FAR'ом, не так ли?
Оффтоп: А почему на всех олимпиадах компалят именно с О2, а не с О3?
Есть легенда, что раньше O3 был более забагованным, и кроме того оптимизации O3 очень строгие к соблюдению стандарта и могут дать по рукам за неосторожное обращение: http://stackoverflow.com/questions/11546075/is-optimisation-level-o3-dangerous-in-g
Погуглил. Походу, минимальный размер выделяемой через new памяти равен 16 байтам.
Провел тест: создал 107 char'ов (размер 1 байт) и столько же структур размером 8 байт. Оба варианта захавали 156 мб ≈
. Теперь понятно, откуда разница в 2 раза.
Я был уверен, что компилирую с оптимизацией, но действительно флага -O2 не было. Спасибо!
P.S. Нет, FAR'ом не пользуюсь.