Алгоритм для реализации SQL-подобных группирования с функциями агрегирования по коллекции?

Question

Допустим, у вас есть такой массив:

[
  {'id' : 1, 'closed' : 1 },
  {'id' : 2, 'closed' : 1 },
  {'id' : 5, 'closed' : 1 },
  {'id' : 7, 'closed' : 0 },
  {'id' : 8, 'closed' : 0 },
  {'id' : 9, 'closed' : 1 }
]

Я хотел бы обобщить этот набор данных (не используя SQL!) И получить идентификатор min и max для каждой группы.определяется вариацией строки 'closed'.В результате получается такой вывод:

[
  {'id__min' : 1, 'id__max' : 5, 'closed' : 1},
  {'id__min' : 7, 'id__max' : 8, 'closed' : 0},
  {'id__min' : 9, 'id__max' : 9, 'closed' : 1}
]

Это всего лишь пример того, что я хотел бы сделать. Я хочу реализовать что-то похожее на то, что обеспечивает itertools.groupby в Python, но будучи немного более полным.(Хотелось бы определить мои собственные функции агрегирования).

Я ищу указатели, псевдокод и даже любой код PHP, Python или Javascript, если это возможно.

Спасибо!

Answer 1

Аргумент key для itertools.groupby() позволяет вам передавать свою собственную функцию агрегирования.

Answer 2

код рубина:

def summarise array_of_hashes
    #first sort the list by id
    arr = array_of_hashes.sort {|a, b| a['id'] <=> b['id'] }
    #create a hash with id_min and id_max set to the id of the first
    #array element and closed to the closed of the first array element
    hash = {}
    hash['id_min'] = hash['id_max'] = arr[0]['id']
    hash['closed'] = arr[0]['closed']
    #prepare an output array
    output = []
    #iterate over the array elements
    arr.each do |el|
        if el['closed'] == hash['closed']
            #update id_max while the id value is the same
            hash['id_max'] = el['id']
        else #once it is different
            output.push hash #add the hash to the output array
            hash = {} #create a new hash in place of the old one
            #and initiate its keys to the appropriate values
            hash['id_min'] = hash['id_max'] = el['id']
            hash['closed'] = el['closed']
        end
    end
    output.push hash #make sure the final hash is added to the output array
    #return the output array
    output
end

Обобщенная версия:

def summarise data, condition, group_func
    #store the first hash in a variable to compare t
    pivot = data[0]
    to_group = []
    output = []
    #iterate through array
    data.each do |datum|
        #if the comparison of this datum to the pivot datum fits the condition
        if condition.call(pivot, datum)
            #add this datum to the to_group list
            to_group.push datum
        else #once the condition no longer matches
            #apply the aggregating function to the list to group and add it to the output array
            output.push group_func.call(to_group)
            #reset the to_group list and add this element to it
            to_group = [datum]
            #set the pivot to this element
            pivot = datum
        end
    end
    #make sure the final list to group are grouped and added to the output list
    output.push group_func.call(to_group)
    #return the output list
    output
end

Следующий код будет работать для вашего примера:

my_condition = lambda do |a, b|
    b['closed'] == a['closed']
end

my_group_func = lambda do |to_group|
    {
        'id_min' => to_group[0]['id'],
        'id_max' => to_group[to_group.length-1]['id'],
        'closed' => to_group[0]['closed']
    }
end

summarise(my_array.sort {|a, b| a['id'] <=> b['id']}, my_condition, my_group_func)

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

Answer 3

Может быть, я неправильно понимаю проблему, но разве это не просто стандартная карта / уменьшение проблема?

Answer 4

PHP-версия кода Ruby с немного более общей обработкой имен и идентификаторов:

<code>$input = array(
    array('id' => 3, 'closed' => 1),
    array('id' => 2, 'closed' => 1),
    array('id' => 5, 'closed' => 1),
    array('id' => 7, 'closed' => 0),
    array('id' => 8, 'closed' => 0),
    array('id' => 9, 'closed' => 1)
);

$output = min_max_group($input, 'id', 'closed');
echo '<pre>'; print_r($output); echo '

'; функция min_max_group ($ массив, $ имя, $ group_by) { $ output = array (); $ tmp [$ name .'__ max '] = $ tmp [$ name .'__ min'] = $ array [0] [$ name]; $ tmp [$ group_by] = $ array [0] [$ group_by]; foreach ($ массив как $ значение) { if ($ value [$ group_by] == $ tmp [$ group_by]) { if ($ value [$ name] <$ tmp [$ name .'__ min ']) {$ tmp [$ name .'__ min'] = $ value [$ name]; } if ($ value [$ name]> $ tmp [$ name .'__ max ']) {$ tmp [$ name .'__ max'] = $ value [$ name]; } } еще { $ output [] = $ tmp; $ tmp [$ name .'__ max '] = $ tmp [$ name .'__ min'] = $ value [$ name]; $ tmp [$ group_by] = $ value [$ group_by]; if ($ value [$ name] <$ tmp [$ name .'__ min ']) {$ tmp [$ name .'__ min'] = $ value [$ name]; } if ($ value [$ name]> $ tmp [$ name .'__ max ']) {$ tmp [$ name .'__ max'] = $ value [$ name]; } } } $ output [] = $ tmp; вернуть $ output; }