gatesasbait: Quicksort on a container

[gl00mie]

Цитата:

Сообщение от Blog bot

Today, I wanted to fix the sorting in the Dynamics Ax 4.0x Active Directory user import wizard. I wanted the AD users sorted by their Windows alias. So I dug up the quicksort algorithm from a java website and coded the following method. You could easily adapt the code to sort by 'str' a container that would look like this '[[str, anytype], [str, anytype], [str, anytype], ...]'. That would make it a kind of Map(Types::String, Types::Anytype).

Вот именно! Зачем придумывать для такой частной задачи тяжеловесное тормозное ресурсоемкое общее решение? Мы знаем, что сетевые идентификаторы пользователей уникальны (во всяком случае, в рамках одного домена) - и ключи Map уникальны; нам нужно отсортировать их - и ключи Map всегда отсортированы (или автор, пользуясь отладчиком, никогда этого не замечал?). Так не проще ли сделать из контейнера Map, ключи которого ядро само отсортирует по ходу вставки элементов, а потом пройтись по этому Map'у enumerator'ом и создать из ключей и связанных значений новый контейнер?

Цитата:

Сообщение от Blog bot

Also note that containers are passed by value, so this will potentially take a lot of memory for containers larger than a few hundred elements.

Очень уместное замечание, если вспомнить, что conpoke каждый раз создает новый контейнер, причем чем больше отсортированно элементов, тем больше и размер этого контейнера. Это то, что у Джоэла Спольски называется алгоритм маляра Шлемиля:

Цитата:

Шлемиль устроился на работу маляром и должен был наносить разметку посредине дороги. В первый день он взял бочку краски и разметил 300 метров дороги. «Неплохо! - сказал босс. - Ты быстро работаешь!» И заплатил ему денежку. На следующий день Шлемль осилил только 150 метров. «Ну что ж, не так здорово, как вчера, но ты все равно быстро работаешь. 150 метров - это немало», - сказал босс и заплатил ему денежку. Еще через день Шлемиль расчертил 30 метров дороги. «Всего 30 метров! - рассверипел босс. - Это никуда не годится. В первый день ты сделал в десять раз больше, что случлось?» «Ничего не могу поделать, - говорит Шлемиль. - С каждым днем приходится все дальше и дальше уходить от бочки с краской.»