Поиск медианы

[demianimp]

Добрый день.

Спешу поделиться алгоритмом поиска медины.

Немного теории:
Медиан - возможное значение признака, которое делит ранжированную совокупность (вариационный ряд выборки) на две равные части: 50 % «нижних» единиц ряда данных будут иметь значение признака не больше, чем медиана, а «верхние» 50 % — значения признака не меньше, чем медиана.

Немного практики:
Логика выполнения:
- Отсортировать массив;
- Если кол-во чисел четное, то найти среднее между серединными ячейками массива;
- Если кол-во числе не четное, то взять серединную ячейку.

static real con2median(container _con)
{
    container   con;
    int         lenCon = conLen(_con),
                i;
    real        ret;
    anytype     any;
    ;
    for(i = 1; i <= lenCon; i++)
    {
        any = conPeek(_con, i);
        con +=  any2real(any);
    }
    con = quickSort(con);
    
    info(con2Str_NV(con, '\n'));

    if(lenCon mod 2 == 0)
    {
        ret = conPeek(con, trunc(lenCon / 2));
        ret += conPeek(con, trunc(lenCon / 2) + 1);
        ret = ret / 2;
    }
    else
    {
        ret = conPeek(con, trunc(lenCon / 2));
    }

    return ret;
}

Код метода quickSort взят от сюда --> Сортировка контейнеров


Я использую контейнер, т.к. при поиске медианы важны все данные. Set и Map убирает дубликаты.

Друзья, если есть идеи по улучшению алгоритмы, то говорите. Буду рад узнать что-то новое.

Цитата:

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

...

Я использую контейнер, т.к. при поиске медианы важны все данные. Set и Map убирает дубликаты.

А почему не использовать ArrayList ?

[belugin]

Цитата:

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

Я использую контейнер, т.к. при поиске медианы важны все данные. Set и Map убирает дубликаты.

Если подмешать к данным счетчик, то дубликатов не будет.

container dataKey = xxxxxx;
index ++;
mySet.insert(dataKey + [index])

[demianimp]

Цитата:

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

А почему не использовать ArrayList ?

ArrayList == System.Collections.ArrayList?

У меня при ArrayList.add() с разными типами. Метод ArrayList.sort() в ошибку падает.

Цитата:

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

Если подмешать к данным счетчик, то дубликатов не будет.

container dataKey = xxxxxx;
index ++;
mySet.insert(dataKey + [index])

belugin, Не понял с mySet.insert(dataKey + [index]).
У меня нет метода insert в Set, только add.

[demianimp]

    static real con2median(container _con)
{
    container   con;
    int         lenCon = conLen(_con),
                i;
    real        ret;
    anytype     any;
    ;
    for(i = 1; i <= lenCon; i++)
    {
        any = conPeek(_con, i);
        con +=  any2real(any);
    }
    con = quickSort(con);

    if(lenCon mod 2 == 0)
    {
        ret = conPeek(con, trunc(lenCon / 2));
        ret += conPeek(con, trunc(lenCon / 2) + 1);
        ret = ret / 2;
    }
    else
    {
        ret = conPeek(con, trunc(lenCon / 2) + 1);
    }

    return ret;
}

...
{
ret = conPeek(con, trunc(lenCon / 2) + 1);
}
...
Нашел у себя ошибку и мусор небольшой. Исправил.

[Владимир Максимов]

Цитата:

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

Друзья, если есть идеи по улучшению алгоритмы, то говорите. Буду рад узнать что-то новое.

Угу. Таблица называется. С индексом.

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

Ну, и идея, которую подкинул (но не развернул) belugin.

Если у Вас есть повторяющиеся значения, то для уникальности надо "подмешать" дополнительное значение. Вариантов "вагон и маленькая тележка" Ну, например так

    Set             set;
    SetEnumerator   se;
    ;

    set = new Set(types::Container);
    set.add([5, set.elements() + 1]);
    set.add([1, set.elements() + 1]);
    set.add([2, set.elements() + 1]);
    set.add([1, set.elements() + 1]);
    set.add([1, set.elements() + 1]);
    set.add([3, set.elements() + 1]);
    info(strFmt('Элементов %1', set.elements()));
    se = set.getEnumerator();
    while (se.moveNext())
    {
        info(strFmt('Значение = %1, Номер вставки = %2', conPeek(se.current(),1), conPeek(se.current(),2)));
    }
    return;

Но если вместо Set использовать индексированную таблицу будет еще проще

[demianimp]

Цитата:

Сообщение от Владимир Максимов

Угу. Таблица называется. С индексом.

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

Но если вместо Set использовать индексированную таблицу будет еще проще

Владимир Максимов , большое спасибо за разнесения.

Теперь включу нуба

А как из табличной переменой или set выдернуть медиану?
Перебирать через цикл и останавливаться на нужной записи?

[macklakov]

Цитата:

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

А как из табличной переменой выдернуть медиану?
Перебирать через цикл и останавливаться на нужной записи?

Как в обычном sql. Через count находишь количество записей, а потом while-ом отматываешь до нужной. По сравнению с quickSort должно быть гораздо быстрее искаться. Главное данные изначально в индексированную таблицу пихать, минуя стадию container-а.

[Raven Melancholic]

Цитата:

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

Добрый день.
Спешу поделиться алгоритмом поиска медины.
Немного теории:

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

Цитата:

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

ArrayList == System.Collections.ArrayList?

У меня при ArrayList.add() с разными типами. Метод ArrayList.sort() в ошибку падает.

Да.
А почему у вас ArrayList.add() с разными типами? Если смотреть ваше преобразование то any2real как бы сводит все к одному типу.
Сортировка на real у меня выполняется без ошибок.
Подозреваю что в силу кучи причин это будет быстрее + корректнее чем самописки сортировки.

[demianimp]

Цитата:

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

Да.
А почему у вас ArrayList.add() с разными типами? Если смотреть ваше преобразование то any2real как бы сводит все к одному типу.
Сортировка на real у меня выполняется без ошибок.
Подозреваю что в силу кучи причин это будет быстрее + корректнее чем самописки сортировки.

Действительно удобнее через ArrayList. Я правильно понимаю, что он работает только с типом real? Или он по первому arrayList.Add() определяет тип?

[demianimp]

Вот новый код алгоритм поиска с System.Collections.ArrayList:

static real con2median(container _con)
{
    System.Collections.ArrayList    arrayList = new System.Collections.ArrayList();
    container                       con;
    int                             lenCon = conLen(_con),
                                    i;
    real                            ret,
                                    ret1;
    anytype                         any;
    ;
    for(i = 1; i <= lenCon; i++)
    {
        arrayList.Add(any2real(conPeek(_con, i)));
    }
    arrayList.Sort();

    if(lenCon mod 2 == 0)
    {
        ret  = arrayList.get_Item(real2int(trunc(lenCon / 2)) - 1);
        ret1 = arrayList.get_Item(real2int(trunc(lenCon / 2)));

        ret = (ret + ret1) / 2;
    }
    else
    {
        ret = arrayList.get_Item(real2int(trunc(lenCon / 2)));
    }
    
    return ret;
}

Цитата:

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

Действительно удобнее через ArrayList. Я правильно понимаю, что он работает только с типом real? Или он по первому arrayList.Add() определяет тип?

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

[Raven Melancholic]

Цитата:

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

Действительно удобнее через ArrayList. Я правильно понимаю, что он работает только с типом real? Или он по первому arrayList.Add() определяет тип?

Он работает с любым простым типом NET. В принципе, даже с разными типами должен работать, если они совместимы между собой. Из C# можно заставить его работать с любым типом, реализовав свой ICompare. Из DAX, понятно, ICompare не реализуешь, поэтому придется обойтись стандартными.