Задача: groupBy, chunk, uniqBy и другие утилиты
На этой странице
Небольшие утилиты коллекций — частая разминка на лайвкодинге: groupBy (сгруппировать по ключу), chunk (разбить на части по size), uniq / uniqBy (убрать дубликаты), intersection / difference (пересечение и разность массивов), countBy, partition, zip. Хорошее решение — короткое, без мутаций входа и с понятной сложностью; часто достаточно reduce, Map и Set.
Вопрос
Реализуйте groupBy, chunk, uniqBy, intersection, difference, partition и zip. Какова сложность каждого решения?
groupBy
function groupBy(items, getKey) {
const keyFn = typeof getKey === "function" ? getKey : (item) => item[getKey];
return items.reduce((groups, item) => {
const key = keyFn(item);
(groups[key] ??= []).push(item);
return groups;
}, {});
}
groupBy([{ city: "Казань", n: "А" }, { city: "Москва", n: "Б" }, { city: "Казань", n: "В" }], "city");
// { "Казань": [{…А}, {…В}], "Москва": [{…Б}] }
groupBy([1.2, 1.8, 2.1], Math.floor); // { "1": [1.2, 1.8], "2": [2.1] }Встроенный аналог — Object.groupBy(items, fn) и Map.groupBy (ES2024).
chunk
function chunk(arr, size) {
if (size <= 0) throw new RangeError("size должен быть больше 0");
const result = [];
for (let i = 0; i < arr.length; i += size) {
result.push(arr.slice(i, i + size));
}
return result;
}
chunk([1, 2, 3, 4, 5], 2); // [[1, 2], [3, 4], [5]]uniq и uniqBy
const uniq = (arr) => [...new Set(arr)];
function uniqBy(arr, getKey) {
const seen = new Set();
return arr.filter((item) => {
const key = getKey(item);
if (seen.has(key)) return false;
seen.add(key);
return true;
});
}
uniq([1, 2, 2, NaN, NaN]); // [1, 2, NaN] — Set считает NaN равными
uniqBy([{ id: 1 }, { id: 2 }, { id: 1 }], (u) => u.id); // [{ id: 1 }, { id: 2 }]arr.filter((x, i) => arr.indexOf(x) === i) тоже работает, но O(n²) и не находит NaN.
intersection и difference
const intersection = (a, b) => {
const setB = new Set(b);
return [...new Set(a)].filter((x) => setB.has(x));
};
const difference = (a, b) => {
const setB = new Set(b);
return a.filter((x) => !setB.has(x));
};
intersection([1, 2, 3, 3], [2, 3, 4]); // [2, 3]
difference([1, 2, 3], [2]); // [1, 3]Set дает O(n + m) вместо O(n·m) с includes. В новых движках есть Set.prototype.intersection и difference.
partition, countBy, zip
const partition = (arr, predicate) =>
arr.reduce(([pass, fail], x) => (predicate(x) ? pass.push(x) : fail.push(x), [pass, fail]), [[], []]);
partition([1, 2, 3, 4], (x) => x % 2 === 0); // [[2, 4], [1, 3]]
const countBy = (arr, fn) =>
arr.reduce((acc, x) => {
const key = fn(x);
acc[key] = (acc[key] ?? 0) + 1;
return acc;
}, {});
countBy(["a", "bb", "cc", "d"], (s) => s.length); // { "1": 2, "2": 2 }
const zip = (...arrays) =>
Array.from({ length: Math.max(...arrays.map((a) => a.length)) }, (_, i) => arrays.map((a) => a[i]));
zip([1, 2], ["a", "b"], [true]); // [[1, "a", true], [2, "b", undefined]]Сложность
| Функция | Время | Память |
|---|---|---|
| groupBy, countBy, partition | O(n) | O(n) |
| chunk | O(n) | O(n) |
| uniq / uniqBy (Set) | O(n) | O(n) |
| intersection / difference (Set) | O(n + m) | O(m) |
| zip | O(k · max) | O(k · max) |
Что важно помнить
- Не мутируйте входные массивы — возвращайте новые.
SetиMap— главный инструмент для O(n) вместо O(n²).- Ключи обычного объекта становятся строками; для ключей-объектов используйте
Map. - Знайте встроенные аналоги:
Object.groupBy,Set.prototype.union/intersection/difference,Array.prototype.toSorted. - Теория: Set, Map.
Мини-шпаргалка
groupBy — reduce + (acc[key] ??= []).push(x). chunk — slice(i, i + size) с шагом size. uniq — [...new Set(arr)], uniqBy — Set ключей + filter. intersection/difference — Set второго массива. partition, countBy — reduce. Всё O(n).
Документация
MDN: Object.groupBy, MDN: Set, MDN: Set.prototype.intersection, Lodash.