Хранить верхние 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, в то время как для каждой конструкции и для создания новых переменных. Я могу сортировать массив 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

С дополнительным классом:

И функции:

То есть код:

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

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 элементов массива можно выполнить с помощью selection algorithm. Тот факт, что у вас есть сгруппированные данные, не должен усложнять задачу, просто игнорируйте элементы, которые не входят в группу.

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

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