はじめに
groupBy を書いてみたメモ。
こういうのが揃っているライブラリもあるけれど、
バニラで書きたいときもあるし、
色々と応用も効きそうだしということで書き留め。
例
何かゲームの個人記録があったとして、
各チームの平均点が知りたい、みたいなケース。
const records = [
{ player: 'a', team: 'red', score: 10 },
{ player: 'b', team: 'blue', score: 3 },
{ player: 'c', team: 'red', score: 4 },
{ player: 'd', team: 'green', score: 15 },
// ...
];
/*
const result = [
{ team: 'red', score: ... },
{ team: 'blue', score: ... },
{ team: 'green', score: ... },
// ...
]
*/
ナイーブな実装
filter で振り分けちゃおうか、という発想。
const result = ['red', 'blue', 'green']
.map(team => {
const list = records.filter(r => r.team === team);
return {
team,
score: list.reduce((sum, r) => sum + r.score, 0) / list.length
};
});
書くのは楽だけれど、filter のループ回数が要素数×分割数 になるので、
件数多いときにちょっと使いたくない感じ。
チームも決め打ちになってしまっているので、拡張性に乏しい。
やはり汎用的な groupBy が欲しい。
groupBy オブジェクト版
グループに分け、結果を { key: values } なオブジェクトで返す。
わりとよく見る実装。(underscore.js とか)
js
const groupBy = (array, getKey) =>
array.reduce((obj, cur, idx, src) => {
const key = getKey(cur, idx, src);
(obj[key] || (obj[key] = [])).push(cur);
return obj;
}, {});
ts
const groupBy = <K extends PropertyKey, V>(
array: readonly V[],
getKey: (cur: V, idx: number, src: readonly V[]) => K
) =>
array.reduce((obj, cur, idx, src) => {
const key = getKey(cur, idx, src);
(obj[key] || (obj[key] = []))!.push(cur);
return obj;
}, {} as Partial<Record<K, V[]>>);
振り分けのループ回数が要素数に抑えられている。
Usage
const groups = groupBy(records, r => r.team);
const result = Object.entries(groups)
.map(([team, list]) => ({
team,
score: list.reduce((sum, r) => sum + r.score, 0) / list.length
}));
単に振り分けるだけならいいのだけれど、その後になにか続けようとすると、ちょっと使い勝手が悪い。
他にも色々と不満点がある。
- 振り分けがオブジェクトのキーに出来るもの (
string,number,symbol) に限定される。 - ケースによっては、グループの順序が登場した順にならない。
groupBy タプル版
オブジェクト { key: values } ではなくタプル群 [key, values][] を返すようにしよう。
js
const groupBy = (array, getKey) =>
Array.from(
array.reduce((map, cur, idx, src) => {
const key = getKey(cur, idx, src);
const list = map.get(key);
if (list) list.push(cur);
else map.set(key, [cur]);
return map;
}, new Map())
);
ts
const groupBy = <K, V>(
array: readonly V[],
getKey: (cur: V, idx: number, src: readonly V[]) => K
): [K, V[]][] =>
Array.from(
array.reduce((map, cur, idx, src) => {
const key = getKey(cur, idx, src);
const list = map.get(key);
if (list) list.push(cur);
else map.set(key, [cur]);
return map;
}, new Map<K, V[]>())
);
使い方。
Usage
const result = groupBy(items, item => item.team)
.map(([team, items]) => ({
team: team,
score: items.reduce((sum, item) =>
sum + item.score, 0) / items.length
}));
そうそう、せめてこうでなくては。
返してくるのが配列なので素直に続けて書ける。
振り分けに Map を使用しているので、グループ登場順が維持される。
また、boolean や object (参照) も振り分けに使える。
最終的にオブジェクトにしたい場合も、ES2019 以降であれば Object.fromEntries を用いて変換できる。
const objGroupBy = (array, getKey) =>
Object.fromEntries(groupBy(array, getKey));
const objGroupBy = <K extends PropertyKey, V>(
array: readonly V[],
getKey: (cur: V, idx: number, src: readonly V[]) => K
) =>
Object.fromEntries(groupBy(array, getKey)) as
Partial<Record<K, V[]>>;
応用: インデックス分配 (配列→配列の配列)
ちょっと方向を変えて、キーで分類するのではなくて、
インデックスで分類し、配列の配列を返すものも作ってみる。
groupBy の亜種みたいなものだけれど、これが何かと便利。
javascript
const scatter = (array, getIndex) =>
array.reduce((result, cur, idx, src) => {
const i = getIndex(cur, idx, src) | 0;
if (i >= 0) (result[i] || (result[i] = [])).push(cur);
return result;
}, []);
typescript
const scatter = <T>(
array: readonly T[],
getIndex: (cur: T, idx: number, src: readonly T[]) => number
) =>
array.reduce((result, cur, idx, src) => {
const i = getIndex(cur, idx, src) | 0;
if (i >= 0) (result[i] || (result[i] = [])).push(cur);
return result;
}, [] as T[][]);
こんな感じ。
Usage
const a = [1, 2, 3, 4];
const [even, odd] = scatter(a, x => x % 2);
console.log(even); // [2, 4]
console.log(odd); // [1, 3]
振り分け (groupBy 代わり)
// 各商品は、0 以上 10 未満の人気度(レーティング)を持っている。
const items = [
{ name: 'minor', rating: 3.8, desc: "..." },
{ name: 'niche', rating: 1.5, desc: "..." },
{ name: 'major', rating: 9.0, desc: "..." },
// ...
];
// 3段階にランク分け
const [low = [], middle = [], high = []] =
scatter(items, item => item.rating / 10 * 3 | 0);
バケットソート
そのまま flat すれば、いわゆるバケットソートと同じことになる。
// レーティング順でなくランク順、ランク内の順序は維持
const rankedItems = scatter(items,
item => item.rating / 10 * 3 | 0).flat();
サイズ分割
元のインデックスを用いれば、配列を分割できる。
const chunk = (a, n) => scatter(a, (_, i) => i / n | 0);
chunk([0,1,2,3,4,5], 3); // [[0,1,2], [3,4,5]]
行列周りに応用してみたりとか。
const array = [
0, 1, 2, 3,
4, 5, 6, 7,
8, 9, 10, 11,
12, 13, 14, 15
];
const rowMatrix = scatter(array, (_, i) => i / 4 | 0);
// [
// [0, 1, 2, 3],
// [4, 5, 6, 7],
// [8, 9, 10, 11],
// [12, 13, 14, 15]
// ]
const colMatrix = scatter(array, (_, i) => i % 4);
// [
// [0, 4, 8, 12],
// [1, 5, 9, 13],
// [2, 6, 10, 14],
// [3, 7, 11, 15]
// ]
// 行と列の入れ替え
const transpose = m => scatter(m.flat(), (_, i) => i % m[0].length);
const mat = [
[0, 1, 2],
[3, 4, 5]
];
console.log(transpose(mat));
// [
// [0, 3],
// [1, 4],
// [2, 5]
// ]
console.log(transpose(transpose(mat))); // 元に戻る
おまけ: 疎な配列を埋める・詰める
scatter で返ってくる配列は、疎な配列の可能性があるので、便利関数もついでに。
js
const fillEmpty = (array, supply) => Array.from(array,
(x, i) => array.hasOwnProperty(i) ? x : supply(i));
const skipEmpty = array => array.filter(() => true);
ts
const fillEmpty = <T>(array: readonly T[], supply: (i: number) => T) =>
Array.from(array, (x, i) => array.hasOwnProperty(i) ? x : supply(i));
const skipEmpty = <T>(source: readonly T[]) =>
source.filter(() => true);
Usage
const sparse = [0, , 2, , 4, , 6];
// [0, <empty>, 2, <empty>, 4, <empty>, 6]
// 空き領域を値で埋める。
const filled = fillEmpty(sparse, _ => 0);
// [0, 0, 2, 0, 4, 0, 6]
// 空き領域を詰める
const packed = skipEmpty(sparse);
// [0, 2, 4, 6]