Оперативная сортировка по убыванию

Запись от Gustav размещена 15.03.2010 в 10:40

Программисту-аксаптоведу известно, что если поместить набор однотипных элементов в базовый класс Set ("множество"), а потом выбрать их оттуда при помощи итератора (SetIterator) или перечислителя (SetEnumerator), то порядок извлечения будет соответствовать порядку сортировки этих элементов по возрастанию.

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

Итак, использование Set позволяет нам получить список значений, отсортированный в возрастающем порядке (A..Z). Но как быть, если требуется сортировка по убыванию (Z..A)?

При сортировке чисел - int или real - можно использовать прием, о котором я уже как-то рассказывал в теме order by и group by. Суть приема заключается во врЕменном изменении знака числа на противоположный при добавлении в Set и в восстановлении знака при извлечении из Set'а.

X++:

static void Job_Numeric(Args _args)
{
    Set             set = new Set(Types::Integer);
    SetEnumerator   setEnumerator;
    int             i;
    int             t;

    t = WinAPI::getTickCount();
//--------------------------------------------
    for (i=1; i<=9000; i++)
        set.add(-i);

    setEnumerator = set.getEnumerator();
    while (setEnumerator.moveNext())
        i = -1*setEnumerator.current();
//--------------------------------------------
    info(strFmt('Milliseconds: %1', WinAPI::getTickCount()-t));

    setEnumerator.reset();
    while (setEnumerator.moveNext())
        info(strFmt('%1', -1*setEnumerator.current()));
}

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

Пусть вас не смущает выглядящая несколько странной операция присваивания i = -1*setEnumerator.current(). Она здесь лишь для того, чтобы показать, как следует восстанавливать исходные значения чисел, а также для учёта времени, затрачиваемого на восстановление, в общем времени сортировки. Вы можете видеть, что чуть ниже цикла с этим фиктивным присваиванием цикл перебора множества повторяется еще раз, но теперь уже исключительно для вывода значений в окно Infolog. Аналогичный подход принят и в следующих демонстрационных джобах, при рассмотрении сортировок других типов данных.

Переходим к обратной сортировке дат. С ними - чуть сложнее, чем с числами. Их нельзя просто так взять со знаком минус, но можно вычесть из одной и той же заведомо большей (более поздней) даты. Получившиеся разницы в днях (целые положительные числа) можно загрузить в Set - внимание: типа Integer, а не Date! В качестве очень большой даты можно использовать значение, возвращаемое функцией dateMax() = 31.12.2153 (по крайней мере для сортировок в течение ближайших ста сорока лет нам ее должно хватить

)

X++:

static void Job_Date(Args _args)
{
    Set             set = new Set(Types::Integer);
    SetEnumerator   setEnumerator;
    date            d, dMax=dateMax(), td=today(), tdMin=td-9000;
    int             t;

    t = WinAPI::getTickCount();
//--------------------------------------------
    for (d=td; d>tdMin; d--)
        set.add(dMax-d);

    setEnumerator = set.getEnumerator();
    while (setEnumerator.moveNext())
        d = dMax-setEnumerator.current();
//--------------------------------------------
    info(strFmt('Milliseconds: %1', WinAPI::getTickCount()-t));

    setEnumerator.reset();
    while (setEnumerator.moveNext())
        info(strFmt('%1', dMax-setEnumerator.current()));
}

Теперь о текстовых строках. Сразу отмечу, что обратно-сортировочное решение для данных этого типа ко мне шло как-то очень долго. Временами в голове рисовались какие-то побайтные инвертирования и прочие головоломки. Я всячески гнал эти мысли от себя и, как выяснилось, поступил правильно, когда, наконец, вдруг вспомнилось, что в базовый класс List элементы можно добавлять как в конец, так и в начало списка! (Ну, не часто я использую List в своей практике, ну, извиняйте!)

X++:

static void Job_String(Args _args)
{
    Set             set = new Set(Types::String);
    SetEnumerator   setEnumerator;
    str             s;
    int             t, i;
    List            list = new List(Types::String);
    ListEnumerator  listEnumerator;

    t = WinAPI::getTickCount();
//--------------------------------------------
    for (i=1; i<=9000; i++)
        set.add('Строка '+subStr(int2str(10000+i),2,4));

    setEnumerator = set.getEnumerator();
    while (setEnumerator.moveNext())
        list.addStart(setEnumerator.current());

    listEnumerator = list.getEnumerator();
    while (listEnumerator.moveNext())
        s = listEnumerator.current();
//--------------------------------------------
    info(strFmt('Milliseconds: %1', WinAPI::getTickCount()-t));

    listEnumerator.reset();
    while (listEnumerator.moveNext())
        info(strFmt('%1', listEnumerator.current()));
}

Как видно из кода Job_String, добавился еще один шаг - загрузка строк, отсортированных в Set, в List в обратном порядке. Из этого List'а теперь и получается окончательный результат. Несмотря на дополнительный шаг, процедура для строк претендует на статус универсальной, пригодной для данных любого типа.

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

X++:

static void Job_Numeric_Univers(Args _args)
{
    Set             set = new Set(Types::Integer);
    SetEnumerator   setEnumerator;
    int             i;
    int             t;
    List            list = new List(Types::Integer);
    ListEnumerator  listEnumerator;

    t = WinAPI::getTickCount();
//--------------------------------------------
    for (i=1; i<=9000; i++)
        set.add(i);

    setEnumerator = set.getEnumerator();
    while (setEnumerator.moveNext())
        list.addStart(setEnumerator.current());

    listEnumerator = list.getEnumerator();
    while (listEnumerator.moveNext())
        i = listEnumerator.current();
//--------------------------------------------
    info(strFmt('Milliseconds: %1', WinAPI::getTickCount()-t));

    listEnumerator.reset();
    while (listEnumerator.moveNext())
        info(strFmt('%1', listEnumerator.current()));
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

static void Job_Date_Univers(Args _args)
{
    Set             set = new Set(Types::Date);
    SetEnumerator   setEnumerator;
    date            d, td=today(), tdMin=td-9000;
    int             t;
    List            list = new List(Types::Date);
    ListEnumerator  listEnumerator;

    t = WinAPI::getTickCount();
//--------------------------------------------
    for (d=td; d>tdMin; d--)
        set.add(d);

    setEnumerator = set.getEnumerator();
    while (setEnumerator.moveNext())
        list.addStart(setEnumerator.current());

    listEnumerator = list.getEnumerator();
    while (listEnumerator.moveNext())
        d = listEnumerator.current();
//--------------------------------------------
    info(strFmt('Milliseconds: %1', WinAPI::getTickCount()-t));

    listEnumerator.reset();
    while (listEnumerator.moveNext())
        info(strFmt('%1', listEnumerator.current()));
}

У меня лично в среднем получилось: для чисел - 100 ms в частном случае против 170 ms универсального решения; для дат - 140 и 170 ms соответственно.

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

Как бы то ни было, но аппетит, как говорится, пришёл во время еды, и в результате следующий джоб решает задачу комплексной сортировки набора контейнеров, состоящих из пяти элементов (для удобства изложения будем называть их полями - по аналогии со строкой таблицы БД, на которую контейнер вполне похож). Поля контейнеров в примере имеют типы: 1 - действительное, 2 - дата, 3,4,5 - строки. Требуемый порядок сортировки: 1,2 - по возрастанию, 3 - по убыванию, 4 - по возрастанию, 5 - по убыванию.

Мы сосредоточимся на интересной для нас обратной сортировке, которая "начинается" в глубине контейнера - с 3-го поля. Для того чтобы два первых поля при этом не "фонили", заполним их одинаковыми повторяющимися значениями (3.62 и 31\12\2009).

Вспомогательные действия и врЕменные изменения, которые нужно проделать с набором контейнеров при желании отсортировать некоторые текстовые поля по убыванию:

определить общее количество контейнеров в наборе (элементов в Set) и найти ближайшее число "10 в степени x", превышающее это количество (x - положительное целое число);
.
переставить поля в контейнерах так, чтобы на первых местах слева оказались поля, по которым хочется выполнить сортировку по убыванию;
.
создать еще один вспомогательный набор (SetTmp), который заполнить переставленными контейнерами. При этом контейнеры автоматически отсортируются, правда, пока по возрастанию;
.
очистить исходный набор (Set) и заполнить его контейнерами из вспомогательного набора, возвращая всем полям контейнеров исходный порядок и дописывая в начало значений из сортируемых по убыванию полей подстроку, состоящую из x-значного цифрового кода, рассчитываемого по убыванию, начиная со значения 10^x-1 ("99..99"). К повторяющимся исходным значениям текстовых полей добавляются и повторяющиеся (одинаковые) цифровые коды;
.
окончательно прочитать контейнеры из Set, восстанавливая исходные текстовые значения путем обрезания слева x временно добавленных символов.

Перечисленные алгоритмические шаги реализованы в джобе:

X++:

static void Job_Container_AscDesc(Args _args)
{
// СОРТИРОВКА КОНТЕЙНЕРОВ В ВОЗРАСТАЮЩЕ-УБЫВАЮЩЕМ ПОРЯДКЕ
// Имеется множество контейнеров вида [r1,d2,s3,s4,s5] (real,date,str,str,str)
// Нужно выполнить сортировку: r1 ASC, d2 ASC, s3 DESC, s4 ASC, s5 DESC

    Set             set     = new Set(Types::Container);
    Set             setTmp  = new Set(Types::Container);
    SetEnumerator   setEnumerator;
    real            r1;
    date            d2;
    str             s3, s4, s5, sprev, s3prev, s5prev;
    int             t, i, j, k, pwr, tenInPwr;
    ;

    t = WinAPI::getTickCount();
//--------------------------------------------
    // Заполнение Set исходным набором данных - контейнерами [r1,d2,s3,s4,s5]
    for (i=1; i<=20; i++)
        for (j=1; j<=20; j++)
            for (k=1; k<=20; k++) // итого 20 * 20 * 20 = 8000 элементов
                set.add([3.62, 31\12\2009,
                        'Строка '+subStr(int2str(100+i),2,2),
                        'Строка '+subStr(int2str(100+j),2,2),
                        'Строка '+subStr(int2str(100+k),2,2)]);

    // вычисляем кол-во элементов в Set и число 10^x, достаточное для их нумерации
    pwr = trunc(log10(set.elements()))+1; // х
    tenInPwr = any2int(power(10,pwr));    // 10^x

    // 1 => 2: перебираем Set и заполняем вспомогательный SetTmp контейнерами с переставленными элементами
    setEnumerator = set.getEnumerator();
    while (setEnumerator.moveNext())
    {
        [r1,d2,s3,s4,s5] = setEnumerator.current();
        // выводим на первые позиции контейнера все сортируемые по убыванию строковые поля - s3, s5
        setTmp.add([s3,s5, r1,d2,s4]);
    }

    //  2 => 1: очищаем Set и заполняем его из SetTmp
    // строками с добавленными в начало "номерами" для изменения порядка сортировки
    set = new Set(Types::Container);
    i = tenInPwr;
    j = tenInPwr;
    s3prev = strMax(); 
    s5prev = strMax();
    setEnumerator = setTmp.getEnumerator();
    while (setEnumerator.moveNext())
    {
        [s3,s5, r1,d2,s4] = setEnumerator.current(); // например, s3 = "Вася"

        // первое убывающее текстовое поле
        if (s3 != s3prev) // "номер" в s3 изменяем только при изменении значения
        {
            i--;
            s3prev = s3;
        }
        s3 = subStr( int2str(tenInPwr+i), 2, pwr) + s3; // например, s3 станет = "9999Вася"

        // второе убывающее текстовое поле
        if (s5 != s5prev) // "номер" в s5 изменяем только при изменении значения
        {
            j--;
            s5prev = s5;
        }
        s5 = subStr( int2str(tenInPwr+j), 2, pwr) + s5;

        // здесь также можно преобразовать нетекстовые убывающие поля (если есть такие)

        // восстановление исходного порядка элементов в контейнере
        set.add([r1,d2,s3,s4,s5]);
    }

    // окончательное извлечение и восстановление измененных значений
    setEnumerator = set.getEnumerator();
    while (setEnumerator.moveNext())
    {
        [r1,d2,s3,s4,s5] = setEnumerator.current();
        s3 = subStr(s3, pwr+1, strLen(s3)); // "9999Вася" => "Вася"
        s5 = subStr(s5, pwr+1, strLen(s5));
        // здесь также восстанавливаем нетекстовые убывающие поля (если есть)
    }
//--------------------------------------------
    info(strFmt('Milliseconds: %1', WinAPI::getTickCount()-t));

    setEnumerator.reset();
    while (setEnumerator.moveNext())
    {
        [r1,d2,s3,s4,s5] = setEnumerator.current();
        s3 = subStr(s3, pwr+1, strLen(s3));
        s5 = subStr(s5, pwr+1, strLen(s5));

        info(strFmt('%1 -- %2 -- %3 -- %4 -- %5', r1,d2,s3,s4,s5));
    }
}

Если помимо обратной сортировки по текстовым полям требуется также и обратная сортировка по полям чисел или дат, то для них манипуляции существенно проще: их не надо переставлять внутри контейнера, достаточно лишь "изменить знак" перед окончательной ("сортирующей") загрузкой в Set и затем в процессе считывания восстановить значения повторным "изменением знака". Потенциальные места преобразования нетекстовых полей в джобе отмечены соответствующими комментариями.

Используя сортирующую способность Set, не следует забывать и о его группирующей способности - содержать в себе только уникальные значения, игнорируя повторное добавление уже имеющихся элементов. Поэтому если сортируется набор неуникальных простых значений (чисел, дат, строк), их следует превратить в контейнеры путем добавления на вторую позицию уникального значения целочисленного счетчика (своеобразного "RecId"), как это было сделано, например, здесь: order by и group by (в результате чего оба значения "200" попали в финальный результат). Если сортируются неуникальные контейнеры, то их так же надо сделать уникальными, добавив аналогичный "RecId" последним элементом.

Размещено в Без категории

Просмотров 172904 Комментарии 1

« Предыдущее Главная страница Следующее »

Всего комментариев 1

Давно хотел написать комментарий. На самом деле интересный эксперимент, однако получилось очень много кода, причем не самого простого в восприятии. Честно говоря, если бы я сейчас решал подобную задачу, то я бы сделал следующим образом: создал бы классы обертки для всех нужных базовых типов, которые предполагается сортировать. Имплементировал бы для них аналог .NET-овских или Java "компараторов". Суть в том, что данный интерфейс имеет всего один метод "сравнить с" и возвращает 0 если объекты равны, отрицательное значение в случае если наш текущий объект меньше того, с которым сравниваем и наоборот если больше. Кстати, путем инвертирования сразу получаем и обратную сортировку.

Дальше взять какой нить QuickSort(хотя поскольку он рекурсивный, возможно не лучший выбор для больших массивов) и реализовать его один раз, именно вокруг ссылок на интерфейс "компаратора". Таким образом мы получили бы универсальный сортировщик для любых типов данных, кроме таблиц конечно. Такие вот мысли вслух.

Запись от Lemming размещена 30.04.2010 в 19:02 Lemming is offline

Архив
< Ноябрь 2024
Вс	Пн	Вт	Ср	Чт	Пт	Сб
20	21	22	23	24	25	26
27	28	29	30	31	1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

Сообщение форума

Отменить изменения