Нашел время, ага

[metaclass]

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

БЛИН!!!!
Проблему понял буквально полсекунды назад, когда после начала написания поста глянул на профилировщик и на выводимые им данные. Там время ближе к(N^2), чем к o(log(n)) из-за того что загружаемые из БД данные вставляются в начало отсортированного списка(основанного на массиве). Ну я и дятел, однако, убить производительность на такой очевидной мелочи.
И чтобы найти, нужно было всего лишь нажраться вина, впихнуть в состоянии крайнего умопомрачения отладочные логи и вызовы встроенного профилировщика в код и посмотреть на результат. А при разработке загружаемых данных было немного, поэтому сразу не обратил внимания.

Comments

[lupus-lupusum.livejournal.com]

в языке перл подобные проблемы невозможны

[metaclass.livejournal.com]

Как это невозможны? Я понимаю, что можно обойти эту проблему, используя какой-нибудь другой способ хранения списков, вместо массива, но чисто теоретически - от копирования блока памяти N раз при вставке N элементов в начало массива никуда не уйти.

[lupus-lupusum.livejournal.com]

я не знаю, как работает алгоритм команды unshift и push но тесты показывают, что добавление 10 млн. уникальных элементов длиной около 37 байт в начало и в хвост массива берет примерно одинаковое процессорное время
"10000000 iterations
Adding to beginning of array took 20 wallclock secs (19.64 usr + 0.39 sys = 20.03 CPU)
Adding to end of array took 55 wallclock secs (20.80 usr + 1.17 sys = 21.97 CPU)"

[metaclass.livejournal.com]

Ага, там алгоритм оказывается хитрый: ссылко
Они выделяют память дополнительную и в начале и в конце массива, и поэтому реаллокация занимает одинаково времени, вне зависимости от того, в начало вставлять или в конец.

[zamotivator.livejournal.com]

У любой структуры данных есть сильные и слабые стороны.
Никогда не бывает идеала.
А в тестах структур данных любого языка обычно приводят в пример как раз "хорошие" для тестируемой реализации ситуации.