Сортировка контейнеров

[kgksoft]

Всегда не хватало сортировки контейнеров в DAX. Только руки дошли написать.
Навеяно
http://gatesasbait.wordpress.com/200...n-a-container/
можно указывать несколько полей для сортировки (контейнер индексов).

//class Global

static container quickSort(
    container   _qsc,
    container   _cIndexKey  = [1],
    int         _qsstart    = 1,
    int         _qsend      = conlen(_qsc)
    )
{
    int         qsi = _qsstart;
    int         qsj = _qsend;
    container   qsx;
    container   qsKey;

    boolean less(container _c1, container _c2)
    {
        int qsk;
        int idx;
        ;

        for (qsk=1; qsk<=conlen(_cIndexKey); qsk++)
        {
            idx = conpeek(_cIndexKey, qsk);
            if (conpeek(_c1, idx) < conpeek(_c2, idx)) return true;
            if (conpeek(_c1, idx) > conpeek(_c2, idx)) return false;
        }
        return false;
    }
    ;

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

    do
    {
        qsKey = conpeek(_qsc, qsi);
        while (less(qsKey, qsx))
        {
            qsi++;
            if (qsi <= conlen(_qsc))
            {
                qsKey = conpeek(_qsc, qsi);
            }
            else
            {
                break;
            }
        }

        qsKey = conpeek(_qsc, qsj);
        while (less(qsx, qsKey))
        {
            qsj = qsj - 1;
            if (qsi > 0)
            {
                qsKey = conpeek(_qsc, qsj);
            }
            else
            {
                break;
            }
        }

        if (qsi <= qsj)
        {
            qsKey = conpeek(_qsc, qsi);
            _qsc = conpoke(_qsc, qsi, conpeek(_qsc, qsj));
            _qsc = conpoke(_qsc, qsj, qsKey);
            qsi++;
            qsj = qsj - 1;
        }
    } while (qsi <= qsj);

    if (_qsstart < qsj)
    {
        _qsc = Global::quickSort(_qsc, _cIndexKey, _qsstart, qsj);
    }
    if (qsi < _qsend)
    {
        _qsc = Global::quickSort(_qsc, _cIndexKey, qsi, _qsend);
    }

    return _qsc;
}

Примеры использования:

    container c = [ [2, 3], [5, 2], [1, 2], [20, 2], [10, 2] ];
    c = quickSort(c, [2,1]);
    //[ [1, 2], [5, 2], [10, 2], [20, 2], [2, 3] ]
    c = quickSort(c);
    //[ [1, 2], [2, 3], [5, 2], [10, 2], [20, 2] ]

[gl00mie]

А, если не секрет, зачем это?.. . В Аксапте есть классы-коллекции, поддерживающие сортировку, - Set и Map, если нужно сортировать данные, то лучше, мне кажется, использовать их. Скажем, если есть контейнер значений одного базового типа, то получить их в отсортированном по возрастанию виде можно так:

container conValues = ...;
Types baseType = typeof(conpeek(conValues, 1));
Set setOfValues = Set::create([1, any2int(baseType), conlen(conValues)] + conValues);

И все, ядро само отсортирует значения при распаковке Set'а, останется только перебрать их. А если возникает задача отсортировать контейнер контейнеров по нескольким элементам внутри контейнеров, то, возможно, стоило выбрать более подходящую структуру данных, скажем, временную таблицу.

[Diman]

Позвольте позанудствовать, но для реального использования не самая лучшая реализация, а для разминки или задачки на собеседовании вполне себе.

[kgksoft]

Иногда возникает необходимость отсортировать мизерный набор данных (до 10 строк), но не простые типы, а кортежи. Задача "не заслуживает" отдельной временной таблицы. Вот для этих целей и создавался метод. В моём случае это были контейнер из 2 элементов (лот и некое несопоставленное кол-во по лоту). Сортировал по кол-ву и подбирал нужный лот. Свою задачу я решил. Производительность устраивает. Ничего подобного в базовом фунционале не нашёл.

[mazzy]

Цитата:

Сообщение от kgksoft

Всегда не хватало сортировки контейнеров в DAX.

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

поэтому ваш алгоритм имеет очень ограниченное применение.
надо отдать должное функция less - прикольная.
но потенциально опасна runtime-ошибками.

1.
насколько я помню (пусть меня поправят знающие люди), контейнер - это атомарный объект в Аксапте.

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

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

2.
контейнер - чисто аксаптовская структура, для которой нет аналога ни на .net., ни в SQL, ни в OLAP...
в связи с планами перевода всего и вся на .net, контейнеры будут все более более неприемлемым инструментом.

поэтому:

• По возможности, не используйте контейнеры для хранения данных.
• Если уж используете контейнер, постарайтесь минимизировать число модификаций контейнера

=================================
в связи с вышесказанным лучше:
* преобразовать контейнер в объект-коллекцию, например в set, (при преобразовании выполните проверку)
* (опционально для несортирующих коллекций) выполнить сортировку
* преобразовать объект-коллекцию обратно в контейнер.

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

myContainer = set2con(con2set(myContainer)); // сортируем контейнер, содержащий индексы

(сейчас аксапты нет под рукой, чтобы проверить наличие именно этих функций)

[mazzy]

теперь по существу алгоритма.

1.
использовать во вложенной функции less переменную _cIndexKey, глобальную по отношению к функции less - безусловный моветон.

2.
мне кажется, что будут проблемы с пустыми контейнерами (поскольку _cIndexKey и _qsstart инициализируются единицей)

3.
вместо вычисления conlen в цикле по неизменному контейнеру, лучше один раз вычислить и хранить в переменной. поскольку conlen каждый раз просматривает контейнер и вычисляет.

4.
и мне кажется... что будут серьезные проблемы, если контейнер будет содержать одинаковые элементы.

например, как мне кажется (аксапты нет под рукой чтобы проверить), будет неправильно отсротирован такой контейнер

[ [1, 1], [10,10], [1,1], [5,5], [1,1] ]


В общем:
* за попытку - зачет
* но по реализации - Дональд Кнут в помощь

[kgksoft]

Цитата:

Сообщение от mazzy

1.
использовать во вложенной функции less переменную _cIndexKey, глобальную по отношению к функции less - безусловный моветон.

это вложенная функция, так что считаю такой подход приемлемым

Цитата:

Сообщение от mazzy

2.
мне кажется, что будут проблемы с пустыми контейнерами (поскольку _cIndexKey и _qsstart инициализируются единицей)

проблем не было, но это только из-за особенностей поведения интерпретатора.
Сделал дополнительную проверку на пустой контейнер

Цитата:

Сообщение от mazzy

3.
вместо вычисления conlen в цикле по неизменному контейнеру, лучше один раз вычислить и хранить в переменной. поскольку conlen каждый раз просматривает контейнер и вычисляет.

Исправил

Цитата:

Сообщение от mazzy

4.
и мне кажется... что будут серьезные проблемы, если контейнер будет содержать одинаковые элементы.

например, как мне кажется (аксапты нет под рукой чтобы проверить), будет неправильно отсротирован такой контейнер

[ [1, 1], [10,10], [1,1], [5,5], [1,1] ]

Нормально отсортировало.

Попутно доделал возможность указывать порядок сортировки для каждого элемента. Исправленная версия:

static container quickSort(
    container   _qsc,
    container   _cIndexKey  = [[1, SortOrder::Ascending]],
    int         _qsstart    = 1,
    int         _qsend      = conlen(_qsc)
    )
{
    int         qsi = _qsstart;
    int         qsj = _qsend;
    container   qsx;
    container   qsKey;

    boolean less(container _c1, container _c2)
    {
        int qsk;
        int idx;
        SortOrder so;
        int len = conlen(_cIndexKey);
        ;

        for (qsk=1; qsk<=len; qsk++)
        {
            [idx, so] = conpeek(_cIndexKey, qsk);
            if (conpeek(_c1, idx) < conpeek(_c2, idx)) return (so==SortOrder::Ascending)?true:false;
            if (conpeek(_c1, idx) > conpeek(_c2, idx)) return (so==SortOrder::Ascending)?false:true;
        }
        return false;
    }
    ;

    if (! conlen(_qsc)) return _qsc;
    qsx = conpeek(_qsc, (_qsstart +_qsend)/2);

    do
    {
        qsKey = conpeek(_qsc, qsi);
        while (less(qsKey, qsx))
        {
            qsi++;
            if (qsi <= conlen(_qsc))
            {
                qsKey = conpeek(_qsc, qsi);
            }
            else
            {
                break;
            }
        }

        qsKey = conpeek(_qsc, qsj);
        while (less(qsx, qsKey))
        {
            qsj = qsj - 1;
            if (qsi > 0)
            {
                qsKey = conpeek(_qsc, qsj);
            }
            else
            {
                break;
            }
        }

        if (qsi <= qsj)
        {
            qsKey = conpeek(_qsc, qsi);
            _qsc = conpoke(_qsc, qsi, conpeek(_qsc, qsj));
            _qsc = conpoke(_qsc, qsj, qsKey);
            qsi++;
            qsj = qsj - 1;
        }
    } while (qsi <= qsj);

    if (_qsstart < qsj)
    {
        _qsc = Global::quickSort(_qsc, _cIndexKey, _qsstart, qsj);
    }
    if (qsi < _qsend)
    {
        _qsc = Global::quickSort(_qsc, _cIndexKey, qsi, _qsend);
    }

    return _qsc;
}

Тестирование:

    container c = [ [1, 2], [10,10], [1,5], [5,5], [1,10] ];
    ;
    
    c = global::quickSort(c, [[1, SortOrder::Descending],[2, SortOrder::Ascending]]);
    // [ [10,10], [5,5], [1, 2], [1,5], [1,10]  ]

[mazzy]

Спасибо за конструктивный подход.

Цитата:

Сообщение от kgksoft

Нормально отсортировало.

Тестирование:

    container c = [ [1, 2], [10,10], [1,5], [5,5], [1,10] ];
    ;
    
    c = global::quickSort(c, [[1, SortOrder::Descending],[2, SortOrder::Ascending]]);
    // [ [10,10], [5,5], [1, 2], [1,5], [1,10]  ]

нет-нет-нет.
Согласно вашей функции less, кортежи [1,2], [1,5], [1,10] - это разные элементы.
я же говорил об одинаковых элементах [1,1], [1,1], [1,1].

посмотрю чуть позже, когда доберусь до аксапты.

[kgksoft]

Одинаковые кортежи тоже нормально отсортировались. Новый пример привел для демонстрации управления порядком сортировки

[mazzy]

Цитата:

Сообщение от kgksoft

Одинаковые кортежи тоже нормально отсортировались. Новый пример привел для демонстрации управления порядком сортировки

да, добралсямдо аксапты. работает корректно.
спасибо.

на маленьких контейнерах заданной структуры вполне можно использовать.
тем более, что функций con2set, set2con в стандарте нет.
и к тому же вы добавили порядок сортировки.

===================
маленькое дополнение на будущее:
= в качестве значения по умолчанию используйте литералы
= в качестве значения по умолчанию никогда НЕ используйте потенциально-долго-выполняющиеся функции, вместо них используйте prmisdefault

Дело в том, что Аксапта ВСЕГДА вычисляет значение по умолчанию. Даже если значение было передано в вызывающем классе.

static container quickSort(
    container   _qsc,
    container   _cIndexKey  = [[1, SortOrder::Ascending]],
    int         _qsstart    = 1,
    int         _qsend      = 0
    )
{
    int         _qsend      = prmisdefault(_qsend) ? conlen(_qsc) : _qsend;
...

===================
но в целом - контейнеры лучше не использовать.

[S.Kuskov]

Цитата:

Сообщение от mazzy

Аксапта ВСЕГДА вычисляет значение по умолчанию. Даже если значение было передано в вызывающем классе.

Первый раз об этом слышу.

AX2009:

    boolean defaultValue()
    {
        ;
        info("!");
        return true;
    }
    
    void test(boolean _prm = defaultValue())
    {
        ;
        info(strfmt("%1", _prm));
    }
    ;
    
    test();
    test(true);
    test(false);

Функция расчета значения по-умолчанию вызвалась только когда параметр был опущен.

Цитата:

!
true
true
false

[mazzy]

Цитата:

Сообщение от S.Kuskov

Первый раз об этом слышу.

Перепроверю.
столкнулся с этим, когда занимался производительностью в ax2012.
conlen,, map.elements и т.п. приходилось убирать из дефолта.

[russ]

есть еще системный класс KeySum

[mazzy]

Цитата:

Сообщение от S.Kuskov

Первый раз об этом слышу.

проверил. действительно не вычисляется.
спасибо.

извините, что ввел в заблуждение.

[dech]

Цитата:

Сообщение от russ

есть еще системный класс KeySum

Об этом уже говорили:

Цитата:

Сообщение от mazzy

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

Кстати, не припомню, чтобы там можно было сортировать контейнеры.
Всё же придерживаюсь мнения использовать классы-коллекции для сортировки.