re:re:actable
Урок 064 минуты чтения

Задача: 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, partitionO(n)O(n)
chunkO(n)O(n)
uniq / uniqBy (Set)O(n)O(n)
intersection / difference (Set)O(n + m)O(m)
zipO(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.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам