TypeScript: разбираем исходный код Radash

[return]

Нет ничего хуже использования null там, где можно без них обойтись. Если у тебя всюду в языке доступ к элементу массива, которого нет, возвращает undefined, а в твоей библиотеке – null, то это диссонанс, который отпугнёт часть пользователей

[printf]

const randomInt = (min: number, max: number) => ~~(Math.random() * (max - min + 1) + min)

Я эту функцию, буквально эту самую, даю соискателям на собеседовании и прошу найти в ней ошибку.

Грубых ошибок в ней две:

• Распределение не униформное, см. как правильно.

• Результат обрезан до int32, и получаются причудливые результаты вида

randomInt(8500000000, 9000000000)
// 40568060

Уверен, что это просто случайность, и остальные функции в библиотеке не скопированы из самого глупого ответа на StackOverflow.

[aio350]

"Распределение не униформное..." - покажите реализацию на TypeScript?
"Результат обрезан до int32..." - это я погорячился, в библиотеке вместо ~~ используется Math.floor(), поправил.

[fransua]

Наверное в Objectify лучше заменить reduce на Object.fromEntries():

function *getEntries(arr, getKey, getValue){
    for (let x of arr)
        yield [getKey(x), getValue(x)]
}
export function objectify<T, U>(arr: T[], getKey: (x: T) => string, getValue: (x: T) => U) {
    return Object.fromEntries(getEntries(arr, getKey, getValue))
}

[aio350]

В чем преимущества?

[fransua]

В варианте предложенном автором:

• создается и уничтожается O(n) объектов (это легко исправить)

• возвращаемый объект в V8 хранится менее эффективным способом (это исправить сложнее)

• Когнитивная сложность у reduce большая

[Alexandroppolus]

В listify та же проблема - reduce, который мусорит массивами. Итого, на ровном месте, N^2 по времени и памяти. Надо пушить.

[corporateanon]

Там простого map-а с головой хватит:

const listify = <TVal, KRes>(
  obj: Record<string, TVal>,
  // функция-преобразователь
  toItem: (key: string, val: TVal) => KRes
) => {
  return Object.entries(obj).map((entry) =>
    toItem(entry[0], entry[1])
  );
};

Попутно, почему я заменил TKey на string. С Symbol в качестве ключа Object.entries не работает. Числовые ключи всё равно преобразует в строки.

[corporateanon]

Ваш вариант тоже аллоцирует n массивов из 2 элементов. Да, они не собираются в один большой массив благодаря использованию гератора. Но сами порождаемые генератором значения [getKey(x), getValue(x)] тоже расходуют память.

Предлагаю по старинке:

function objectify<T, U>(
  arr: T[],
  getKey: (x: T) => string,
  getValue: (x: T) => U
) {
  const res:{ [k: string]: U } = {};

  for (const x of arr) {
    res[getKey(x)] = getValue(x);
  }

  return res;
}

[fransua]

Согласен, аллоцирует, но по очереди, так что нельзя говорить о затратах по памяти O(n), кроме результата.
Посмотрел примерно скорость работы, Ваш вариант быстрее в 2-10 раз, в зависимости от n.
Возможно, в каких-то супер предельных случаях мой вариант может быть быстрее, но это неважно.
И должен признать, я до конца не понимаю, что конкретно делает код res[a] = 0 и какая у него сложность)

[corporateanon]

но по очереди

Я думал над этим. Мне кажется, что все пары аллоцируются в куче, и только после прохождения полного цикла уничтожаются сборщиком мусора. Хотя, возможно, движок это как-то и оптимизирует.

Шутки ради решил проверить ваш вариант без аллокаций массивов, получилось вот что:

function *getEntries<T, U>(arr: T[], getKey: (x: T) => string, getValue: (x: T) => U) {
    const pair = [];
    for (let x of arr) {
      pair[0] = getKey(x);
      pair[1] = getValue(x);
      yield pair;
    }
}

function objectify<T, U>(arr: T[], getKey: (x: T) => string, getValue: (x: T) => U) {
    return Object.fromEntries(getEntries(arr, getKey, getValue))
}

[fransua]

Должны уничтожаться внутри цикла, вроде:

function fromEntries(iterable){
    const res = {};
    for (let [key, value] of iterable){
        res[key] = value;
    }
    return res;
}

Я надеялся на то, что эта функция реализована в с++ и res[key] = value не создает всякие схемы объектов, и отдает уже что-то готовое.
Можно для проверки подсунуть бесконечный итератор:

function* getEntries(arr, getKey, getValue) {
    while (true)
        for (let x of arr)
            yield [getKey(x), getValue(x)]
}

и будет бесконечный цикл без OutOfMemory (в моем NodeJS по крайней мере так)

[Alexandroppolus]

я до конца не понимаю, что конкретно делает код res[a] = 0

Если в res ещё не было ключа с таким именем, это приводит к замене некоего "внутреннего класса" (читал что-то подобное про v8). Раньше добавление ключей в цикле считалось не слишком быстрым вариантом. Как теперь, не знаю. Возможно, стоит попробовать создать объект через arr.map+Object.fromEntries, без генераторов

[fransua]

тогда точно О(n) памяти на массив уйдет.
Замерил примерно, вариант по старинке с циклом быстрее всех, потом arr.map+fromEntries и генератор самый медленный((