Как улучшить производительность функционального кода в JS

Question

Я пытаюсь научиться функциональному программированию и не могу понять это. В моем минимальном рабочем примере у меня есть список словарей, каждый словарь содержит имя файла и размер файла. Я хочу создать новый словарь, который группирует файлы по размеру (это часть более крупного алгоритма, который находит дублированные файлы).

Вот "традиционный" подход к этому, мутирование данных:

const groupFilesBySize = (allFileData) => {
  const filesSortedBySize = {};
  for (const fileData of allFileData) {
    if (fileData.size in filesSortedBySize) {
      filesSortedBySize[fileData.size].push(fileData.file);
    } else {
      filesSortedBySize[fileData.size] = [fileData.file];
    }
  }

  return filesSortedBySize;
};

А вот моя «лучшая» попытка сделать это функциональным способом:

const groupFilesBySizeFunctional = (allFileData) =>
  allFileData.reduce(
    (filesSortedBySize, fileData) => ({
      ...filesSortedBySize,
      [fileData.size]: filesSortedBySize[fileData.size]
        ? [...filesSortedBySize[fileData.size], fileData.file]
        : [fileData.file]
    }),
    {}
  );

Я проверил их (воспроизводимый пример ниже), и функциональная версия примерно 10000 раз медленнее . Это не шутка - это просто непригодно. Я могу себе представить, что создание нового словаря каждый раз, когда мы обрабатываем файл в reduce, является причиной задержки.

Тем не менее, теперь я вижу две возможности: либо функциональное программирование имеет ужасную производительность, либо я не могу написать правильный функциональный код. Очевидно, что второй является правильным, я хотел бы спросить: Как правильно написать функцию groupFilesBySize функциональным способом?

---

Тест : Используйте эту функцию для получения массива путей к файлам и размеров файлов:

async function walk(dir) {
  let files = [];
  files = await fs.readdir(dir);
  const parsedFiles = await Promise.all(files.map(async (fileName) => {
    const filePath = path.join(dir, fileName);

    const stats = await fs.lstat(filePath);
    if (stats.isSymbolicLink() || stats.size === 0) {
      return null;
    }
    if (stats.isDirectory()) {
      return walk(filePath);
    } else if (stats.isFile()) {
      return { file: filePath, size: stats.size };
    }
  }));

  return parsedFiles.reduce(
    (all, folderContents) => (folderContents ? all.concat(folderContents) : all),
    []
  );
}

Затем сравните все с помощью:

const benchMark = async () => {
  const dir = path.dirname(__filename);
  const allFileData = await walk(dir);
  console.log(`Total files: ${allFileData.length}`);

  let start = new Date();
  const result1 = groupFilesBySize(allFileData);
  const time1 = new Date() - start;

  start = new Date();
  const result2 = groupFilesBySizeFunctional(allFileData);
  const time2 = new Date() - start;

  console.log('\nFINAL REPORT:')
  console.log(`Are results equal? ${JSON.stringify(result1) === JSON.stringify(result2)}`);
  console.log(`Non functional approach: ${time1} ms`);
  console.log(`Functional approach: ${time2} ms`);
};

Чтобы получить значительные данные, я решил установить пакет узла eslint, поэтому мне нужно сгруппировать все файлы в папке node_modules: npm install eslint. Выход в моей машине:

Total files: 6229

FINAL REPORT:
Are results equal? true
Non functional approach: 6 ms
Functional approach: 34557 ms

Answer 1

Если вы хотите использовать использовать парадигму функционального программирования, убедитесь, что вы используете функциональные структуры данных, например, предоставляемые Immutable. js.

const { Map, List } = Immutable;

const groupFilesBySize = allFileData =>
    allFileData.reduce((filesSortedBySize, { size, file }) =>
        filesSortedBySize.update(size, List(), list => list.push(file)), Map());

const allFileData = [
    { size: 12, file: "Hello World!" },
    { size: 3,  file: "foo" },
    { size: 3,  file: "bar" },
    { size: 6,  file: "foobar" },
    { size: 12, file: "Hello World!" },
    { size: 4,  file: "fizz" },
    { size: 4,  file: "buzz" },
    { size: 8,  file: "fizzbuzz" },
];

console.time("groupFilesBySize");
for (let i = 0; i < 1e6; i++) groupFilesBySize(allFileData);
console.timeEnd("groupFilesBySize");

console.log(groupFilesBySize(allFileData));

<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/4.0.0-rc.12/immutable.min.js"></script>

На моем компьютере для выполнения миллиона итераций требуется около 3 секунд. Сравните это с вашим оригинальным решением.

const groupFilesBySize = (allFileData) => {
  const filesSortedBySize = {};
  for (const fileData of allFileData) {
    if (fileData.size in filesSortedBySize) {
      filesSortedBySize[fileData.size].push(fileData.file);
    } else {
      filesSortedBySize[fileData.size] = [fileData.file];
    }
  }

  return filesSortedBySize;
};

const allFileData = [
    { size: 12, file: "Hello World!" },
    { size: 3,  file: "foo" },
    { size: 3,  file: "bar" },
    { size: 6,  file: "foobar" },
    { size: 12, file: "Hello World!" },
    { size: 4,  file: "fizz" },
    { size: 4,  file: "buzz" },
    { size: 8,  file: "fizzbuzz" },
];

console.time("groupFilesBySize");
for (let i = 0; i < 1e6; i++) groupFilesBySize(allFileData);
console.timeEnd("groupFilesBySize");

console.log(groupFilesBySize(allFileData));

На моем компьютере для выполнения миллиона итераций требуется около 400 миллисекунд. Следовательно, функциональная программа всего лишь в 10 раз медленнее императивной программы.

В заключение, не используйте парадигму функционального программирования с императивными структурами данных, такими как объекты и массивы. Это медленно и грязно. Вместо этого используйте функциональные структуры данных.

Answer 2

Если вы измените мутирование внутри уменьшения, проблем не будет, и вы немного улучшите производительность.

const groupFilesBySizeFunctional = allFileData =>
  allFileData.reduce(
    (filesSortedBySize, fileData) =>
      Object.assign(filesSortedBySize, {
        [fileData.size]: filesSortedBySize[fileData.size]
          ? [...filesSortedBySize[fileData.size], fileData.file]
          : [fileData.file]
      }),
    {}
  );