C# производственное

[109]

по долгу службы неожиданно оказалось нужно оптимизировать относительно тривиальный код (потому что bing pipeline требует, чтобы наш кусок выполнялся за 10 ms, а в этом нашем куске мастурбации с коллекциями по 10К объектов).

в процессе оптимизации открылся ряд вещей, о которых при написании обычного кода просто не задумывается никто.

например, оказалось, что properties are no-go в такого рода коде. за то время, пока происходит доступ - просто доступ - к property, можно десять операций с плавающей точкой сделать.

но вот в кое-что не вторчу никак. например, List[double] размером 10К сортируется за пол-миллисекунды. а List[MyClass] с компарером по тому же double - в десять раз медленнее. wtf? это из-за одного indirection-a? так ведь List[MyStruct] тоже в десять раз медленнее.

Comments

[109.livejournal.com]

что это такое?

[polycode.livejournal.com]

Алгоритм, который выдает отсортированными top k элементов массива. http://en.wikipedia.org/wiki/Partial_sorting

[109.livejournal.com]

эээ... это то, что я написал :)
но мне нужен код, а ни List, ни Linq не умеют partial sort.

[wizzard]

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

если бы stdlib меньше оглядывался на джаву, а инлайнер был умнее, компареры могли бы иметь 0% оверхед.

причем инлайнера нынешнего даже хватает, можно написать на генериках список с втыкающимся компаратором без оверхеда

но, увы, дефолтный лист этого не делает.

[109.livejournal.com]

ну если что-то писать вручную, то не полную сортировку, а partial sort, как мне подсказывают. но удивило, что я не нашёл C# имплементации в сети вообще. может, он не настолько быстрее (или совсем не быстрее)?

[polycode.livejournal.com]

Должно быть быстрее. Фактически, O(n). Алгоритм простой, так что должно быть несложно попробовать и сравнить.