分割困難な集計 - 西尾泰和の外部脳

分割困難な集計

https://gyazo.com/074de177bd8d8dc1505ae0505e41e18b

ある集合の要素を種類ごとに分割してからそれに対して集計fを行いたいが、分割のコストが高い場合

fが二項演算の繰り返しで実現できるような関数なら

例: sum, min

あらかじめ分割することなく集計ができる

code:python

for x in S:

subgrouptypeof(x).append(x)

for t, xs in subgroup:

resultt = f(xs)

code:python

for x in S:

resulttypeof(x).update(x)

注意機構と関連する？？