Пример вспомнил:
Нужна была реализация A* на as3
Нашёл либу на хабре
Прогнал на своём поле - в 5 раз медленнее обычного волнового алгоритма
Полез внутрь и очень удивился - после добавления элемента в всписок открытых - они сортировали его методом sort!
Вообще вместо массива там должна была бы быть куча, реализующая очередь с приоритетом - и сложность _этого места в коде_ вместо n*log n была бы log n. Но зачем же - А* - он же быстрый, какая разница какую структуру для хранения выбрать!
Тогда я не стал лепить кучу - просто сделал бинарную вставку вместо сортировки (поиск места вставки log n + вставка splice - n). Не смотря на линейную сложность самдой вставки splice - оно отработало в 10 раз быстрее волнового алгоритма (видимо за счёт нативности splice). Так то, если руководствоваться одной сложностью - можно было просто без бинарного поиска - обычным влепить.
Короче - небольшая модификация работы со структурой данных - 5 * 10 * 100 = 5000% прироста скорости. И после этого должно быть всё равно какой структурой пользоваться?
Цитата:
|
не проще ли переложить его на другой функционал или на другой язык
|
- Не проще - поменять структуру как раз проще, чем переписывать и делать связки между кусками на разных языках
- для флеша обычно это не возможно - иначе оно во флешплеере в вебе работать не будет. Да, там есть возможность с алхимией(была бесплатной по крайней мере) и на С++ загнать и либы для работы со звуком и кодировкой PNG/JPEG делались - но надо было попотеть чтобы оное срастить и был выигрыш
- на другом языке пишут обычно, когда уже реализовали эффективный алгоритм на текущем и не хватает.
На практике чаще всего приходилось оптимизировать/выбирать работу со структурами при (не касаясь рендеринга - чисто вычисления):
- поиске пути
- сотрировке объектов в изометрии
- поиске всяких областей подсветки, прокладке дорог при строительстве в социалках
- выборке данных из модели (тут оптимизировать приходится редко, но между ними встречаются сложные соотношения, надо подключать мозги, чтобы, например не сравнивать параметры каждого из 1000 элементов в магазине с каждым из 100 в инвентаре в каждом кадре)