Держите верхние N элементов массива по группам

Question

Я использую проприетарный язык в Blaze Advisor (правило enginge). Я ищу алгоритм, как сохранить только первые N элементов в массиве по группам, сформированным конкретным атрибутом. В качестве примера приведем два массива:

parrent[0].id = 1
parrent[1].id = 2

И второй массив:

child[0].parrentId = 1
child[0].result = 3.0
child[1].parrentId = 1
child[1].result = 2.0
child[2].parrentId = 1
child[2].result = 4.0
child[3].parrentId = 1
child[3].result = 6.0
child[4].parrentId = 1
child[4].result = -1.0
child[5].parrentId = 2
child[5].result = 1.0
child[6].parrentId = 2
child[6].result = 16.0
child[7].parrentId = 2
child[7].result = 2.0
child[8].parrentId = 2
child[8].result = -10.0
child[9].parrentId = 2
child[9].result = 5.0

Я хотел бы сохранить только три верхних элемента для каждого parrentId в child массив, как указано result приписывать. На моем языке я могу выполнять все основные операции - я могу использовать if / else, while, for, для каждой конструкции и создавать новые переменные. Я могу отсортировать массив asc / desc и получить индексы отсортированных элементов. Я могу удалить элементы массива.

Для моих данных мне нужен следующий результат:

child[0].parrentId = 1
child[0].result = 3.0
child[1].parrentId = 1
child[2].result = 4.0
child[3].parrentId = 1
child[3].result = 6.0
child[6].parrentId = 2
child[6].result = 16.0
child[7].parrentId = 2
child[7].result = 2.0
child[9].parrentId = 2
child[9].result = 5.0

Answer 1

Со вспомогательным классом:

И функция:

Это имеет код:

len is an integer initially top.children.count - 1;
idx is an integer initially len;
while idx > atIdx do {
    top.children[idx] = top.children[idx-1];
    decrement idx;
}
top.children[atIdx] = child;

Этот код может сделать то, что вы просили:

child is an fixed array of 10 Child;

counter is an integer initially 0;
while counter < 10 do { child[counter] = a Child; increment counter }

child[0].parrentId = 1;
child[0].result = 3.0;
child[1].parrentId = 1;
child[1].result = 2.0;
child[2].parrentId = 1;
child[2].result = 4.0;
child[3].parrentId = 1;
child[3].result = 6.0;
child[4].parrentId = 1;
child[4].result = -1.0;
child[5].parrentId = 2;
child[5].result = 1.0;
child[6].parrentId = 2;
child[6].result = 16.0;
child[7].parrentId = 2;
child[7].result = 2.0;
child[8].parrentId = 2;
child[8].result = -10.0;
child[9].parrentId = 2;
child[9].result = 5.0;

groups is an array of real;

topN is an integer initially 4;

//Init the hashmap of [group] -> [array of 'N' top Child]
top3fromGroup is an association from real to TopChildren;
for each Child in child do if not groups.contains(it.parrentId) then { 
    top3fromGroup[it.parrentId] = a TopChildren;
    initCounter is an integer initially 0;
    while initCounter < topN do {
        top3fromGroup[it.parrentId].children[initCounter] = a Child initially { it.result = Double.MIN_VALUE;} 
        increment initCounter;
    }
    groups.append(it.parrentId);
}

//Filling the groups at the hashmap with the Child elements ordered inside its groups
for each real in groups do { 
    group is a real initially it;
    for each Child in child do {
        localChild is some Child initially it;
        if it.parrentId = group then {
            top is some TopChildren initially top3fromGroup[group]; 
            topValuesIdx is an integer initially 0;
            while topValuesIdx < top.children.count do {
                topChild is some Child initially top.children[topValuesIdx];
                if localChild.result > topChild.result then { 
                    insertAt(topValuesIdx, localChild, top);
                    topValuesIdx = top.children.count;
                } 
                increment topValuesIdx;
            }
        }
    }
}

//Printing the hashmap
for each real in groups do {
    group is a real initially it;
    print("Group: " group);
    childIdx is an integer initially 0;
    for each Child in top3fromGroup[it].children do {
        print("\tchild["childIdx"].parrentId = " it.parrentId); 
        print("\tchild["childIdx"].result = " it.result);
        increment childIdx;
    }
}

Вывод на консоли Eclipse/Blaze будет:

Group: 1.0
    child[0].parrentId = 1.0
    child[0].result = 6.0
    child[1].parrentId = 1.0
    child[1].result = 4.0
    child[2].parrentId = 1.0
    child[2].result = 3.0
    child[3].parrentId = 1.0
    child[3].result = 2.0
Group: 2.0
    child[0].parrentId = 2.0
    child[0].result = 16.0
    child[1].parrentId = 2.0
    child[1].result = 5.0
    child[2].parrentId = 2.0
    child[2].result = 2.0
    child[3].parrentId = 2.0
    child[3].result = 1.0

Execution complete.

Я знаю, что это очень простое и не оптимальное решение.

Answer 2

Сохранение первых N элементов массива может быть выполнено с использованием алгоритма выбора. Тот факт, что у вас есть сгруппированные данные, не должен усложнять проблему, просто игнорируйте элементы, которых нет в группе.

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

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