gatesasbait: Quicksort on a container

[Blog bot]

Источник: http://gatesasbait.spaces.live.com/B...B9F5!151.entry
==============


Good evening

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. There are mutiple tools in DAX to sort records (in particular: the RecordSortedList and temporary tables) but I couldn't find anything to sort lists, arrays or containers. At first I thought of using the .Net Framework's Collections.SortedList, but the SortedList.add() method didn't seem to work. So I dug up the quicksort algorithm from a java website and coded the following method.

'_qsc' is basically a container that contains one or many '[str]'. It would look like this '[[str], [str], [str], ...]'. The reason I didn't implement this with a simpler '[str, str, str, ...]' is that I wanted to be able to sort a container by an str key, but still allowing for another value or set of values to follow.

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). You can put the following method in your Global class if you want to call it from anywhere.

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. Implementing the sorting using a class like DAX's Array class would definitely take less ram at runtime since only one instance of the class would be needed throughout (you would need to modify my method though as you would need to remove the return type and return value since methods recursive by reference don't need to return anything.

public static container quickSortStrContainer(
    container _qsc,
    int _qsstart = 1,
    int _qsend = conlen(_qsc))
{
    int qsi = _qsstart
    int qsj = _qsend;
    str qsx;
    str qsKey;
    ;

    [qsx] = conpeek(_qsc, (_qsstart +_qsend)/2);

    do
    {
        [qsKey] = conpeek(_qsc, qsi);
        while (qsKey < qsx)
        {
            qsi++;
            if (qsi qsx)
        {
            qsj--;
            if (qsi > 0)
            {
                [qsKey] = conpeek(_qsc, qsj);
            }
            else
            {
                break;
            }
        }

        if (qsi

[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 метров! - рассверипел босс. - Это никуда не годится. В первый день ты сделал в десять раз больше, что случлось?» «Ничего не могу поделать, - говорит Шлемиль. - С каждым днем приходится все дальше и дальше уходить от бочки с краской.»