Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 01.08.2020, 08:56
Профессор
Отправить личное сообщение для Shitbox2 Посмотреть профиль Найти все сообщения от Shitbox2
 
Регистрация: 04.10.2010
Сообщений: 569

Ускорите код?
Уважаемые знатоки, возможно ли ускорить функцию groupBy хотя бы в 1,5 раза (для node.js)?
/**
 * Group items by field
 *
 * items = [
 *  {id: 1, name: 'A', val: 1, smth: true},
 *  {id: 2, name: 'B', val: 2, ...},
 *  {id: 3, name: 'A', val: 3, ...},
 *  {id: 4, name: 'B', val: 4, ...},
 *  {id: 5, name: 'A', val: 5, ...}
 * ]
 *
 * groupBy(items, 'name', ['val', ...]) =
 *   [
 *     {
 *       groupField: 'name',
 *       groupValue: 'A',
 *
 *       // Items of the group
 *       items: [{id: 1, name: 'A', val: 1, , smth: true}, {id: 3, name: 'A', val: 3}, {id: 5, name: 'A', val: 5}],
 *
 *       // Values of first item
 *       id: 1,
 *       smth: true,
 *       ...
 *
 *       // Summed values
 *       val: 9,
 *       ...
 *     }, {
 *       groupField: 'name',
 *       groupValue: 'B',
 *       items: [{id: 2, name: 'B', val: 2}, {id: 4, name: 'B', val: 4}],
 *       id: 2,
 *       val: 6,
 *       ...
 *     }
 *   ]
 *
 * @param items - Array<any> - items array
 * @param field - string - field name
 * @param sumFields - Array<string> - array with names of fields which should be summed
 * @returns Array<any>
 */
function groupBy(items, field, sumFields = []) {
    const groupsMap = {};

    for (let i = 0; i < items.length; i++) {
        const item = items[i];
        const groupValue = item[field];
        let group = groupsMap[groupValue];

        if (!group) {
            group = {items: [], groupField: field, groupValue: groupValue, ...item};
            groupsMap[groupValue] = group;
        }

        // Add values which should be summed
        for (let j = 0; j < sumFields.length; j++) {
            const fieldName = sumFields[j];
            const sumValue = item[fieldName];

            if (sumValue) {
                group[fieldName] += sumValue;
            }
        }

        group.items.push(item);
    }

    return Object.keys(groupsMap).map(key => groupsMap[key]);
}

function generateData(amount) {
    return Array.from({length: amount}, (v, i) => {
        return {
            id: i,
            group: String.fromCharCode(Math.floor(Math.random() * 25) + 65),
            string: Math.random().toString(36).substring(2),
            number: Math.random() * 100,
            number2: Math.random() * 1000,
            null: null,
            undefined: undefined,
            boolean: true
        }
    })
}

const data = generateData(100000)
console.time('Groupping')
grouped = groupBy(data, 'group', ['number', 'number2'])
console.timeEnd('Groupping')

Последний раз редактировалось Shitbox2, 02.08.2020 в 00:20.
Ответить с цитированием
  #2 (permalink)  
Старый 01.08.2020, 12:11
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,320

Shitbox2, что у вас делает 70-я строчка?

Upd. еще для ускорения можно попробовать перебирать массив сразу с двух сторон.

Последний раз редактировалось Nexus, 01.08.2020 в 12:15.
Ответить с цитированием
  #3 (permalink)  
Старый 01.08.2020, 14:23
Профессор
Отправить личное сообщение для Shitbox2 Посмотреть профиль Найти все сообщения от Shitbox2
 
Регистрация: 04.10.2010
Сообщений: 569

Сообщение от Nexus Посмотреть сообщение
что у вас делает 70-я строчка?
Делает из мапы массив. На производительности практически на сказывается)

Самая тяжелая операция тут - let group = groupsMap[groupValue]

Сообщение от Nexus Посмотреть сообщение
Upd. еще для ускорения можно попробовать перебирать массив сразу с двух сторон.
Перебор с обоих сторон тут ничего не даст. Или были реальные замеры?

Последний раз редактировалось Shitbox2, 01.08.2020 в 14:26.
Ответить с цитированием
  #4 (permalink)  
Старый 01.08.2020, 14:31
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,320

Сообщение от Shitbox2
Делает из мапы массив.
Может тогда лучше Object.values использовать?

Сообщение от Shitbox2
Самая тяжелая операция тут - let group = groupsMap[groupValue]
Вот уж вряд ли.

Сообщение от Shitbox2
Перебор с обоих сторон тут ничего не даст.
Почему вы так считаете? Кол-во итераций уменьшится вдвое, скорость соответственно должна увеличиться.

И в своем коде вы замеряете не только скорость работы вашей функции группировки, но и скорость генерации ваших данных.
Ответить с цитированием
  #5 (permalink)  
Старый 01.08.2020, 16:09
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 986

>> возможно ли ускорить функцию groupBy
Врятли.
По сути тут идет простая итерация всего объекта с простым условным ветвлением для фильтрации значений по установленным признакам.
Можно развернуть цикл делая по двадцать итераций за проход но с такими оптимизациями интерпретатор и сам справляется.

Тут с логикой проблема, управление данными осуществляется в приложении алгоритмами собранными топориком на коленке.
Задачи связанные с группировкой, хранением, сортировкой, индексацией и выборкой данных лучше решать с помощью баз данных.
Ответить с цитированием
  #6 (permalink)  
Старый 01.08.2020, 16:44
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 986

Цитата:
Вот уж вряд ли.
Это ссылка на внешнюю переменную что не позволяет оптимизатору автоматически развернуть цикл.
Более того этот объект изменяется на текущей итерации цикла т.е. пока не закончится текущая итерация и объект не будет изменен следующую/параллельную итерацию интерпретатор выполнять не может так как состояние объекта еще не определенно что работает как брошенный якорь на гоночном автомобиле.
Основной способ оптимизации выполнения это избавление от побочных эффектов при выполнении блока кода или вынос их в отдельный блок кода.
А строки 50, 67 как раз и есть эти побочные эффекты.
Но данные во внешнем изменяемом объекте не пересекаются по этому если в ручную развернуть цикл то это должно дать прибавку к скорости. Хотя оптимизатор наверно и сам может просчитать что данные не пересекаются и ожидать изменения объекта не обязательно.

Последний раз редактировалось MallSerg, 01.08.2020 в 16:49.
Ответить с цитированием
  #7 (permalink)  
Старый 01.08.2020, 16:49
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 986

размотка цикла
Побочный_эффект_(программи ование)
Ответить с цитированием
  #8 (permalink)  
Старый 01.08.2020, 18:40
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 787

Попробовать использовать Map вместо объекта.
Группы сразу пушить в массив, который вернуть вместо выражения на строке 70.

Читерство: суммируемые поля оформить как проперти, можно с мемоизацией.
Ответить с цитированием
  #9 (permalink)  
Старый 01.08.2020, 19:21
Профессор
Отправить личное сообщение для voraa Посмотреть профиль Найти все сообщения от voraa
 
Регистрация: 03.02.2020
Сообщений: 636

Сообщение от MallSerg
Это ссылка на внешнюю переменную что не позволяет оптимизатору автоматически развернуть цикл.
Это Javascript. Это Node.js Это V8.
Он ничего не разворачивает.
Ответить с цитированием
  #10 (permalink)  
Старый 01.08.2020, 20:37
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 986

Сообщение от voraa
Это Javascript. Это Node.js Это V8.
Он ничего не разворачивает.
Да неужели? В самом деле? ))

Прямая ссылка на исходник где происходит оптимизация турбофаном в V8
https://github.com/v8/v8/blob/4b9b23...eline.cc#L1064

Если вкратце то турбофан пытается байткод виртуальной машины V8 транспилировать в машинный код текущего процессора.
Причем с такой PGO оптимизацией что компиляторы C/C++ пускают слюни от зависти.
Ничего необычного пытается заинлайнить методы и развернуть цыклы где это удается ну и еще дефрагментирует расположение данных в памяти.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Почему разные браузеры по-разному обрабатывают код? izumov AJAX и COMET 3 05.06.2019 00:54
Сортировка массива с объектами на javascript sergiu920 Элементы интерфейса 2 07.12.2018 08:47
как получить исходный код страницы после ajax lerneree AJAX и COMET 4 28.05.2018 13:53
Как найти и заменить код скрипта на странице на другой код? smls Общие вопросы Javascript 2 18.07.2016 22:01
Требуется выводить код рекламного блока Adsense из файла JavaScript??? speedflow Элементы интерфейса 0 26.05.2012 14:50