Эффективная схема слияния двух массивов данных

внешний интерфейс
Эффективная схема слияния двух массивов данных

Это 8-й день моего участия в Gengwen Challenge, смотрите подробности мероприятия:Обновить вызов

предисловие

В качестве внешнего интерфейса данные, возвращаемые сервером, просты в использовании, что может значительно повысить эффективность разработки.
Если данные могут быть предоставлены одним интерфейсом, нет необходимости вызывать два или более сетевых запроса, а затем выполнять слияние данных.

Однако между идеалом и реальностью реальность всегда ищет меня, и я не чувствую тепла идеальной пары.

жестокий опыт

Говоря об этом, вы можете не верить, но, пожалуйста, поверьте мне, потому что я очень добрая.

У одного из наших предприятий есть список данных, и нам нужно вызвать три интерфейса для объединения данных следующим образом:

  1. Возврат 10 единиц базовой информации за раз
  2. еще 10 раз, чтобы запросить детали
  3. Используйте определенное значение идентификатора из результата шага 2 и отправьте еще 10 запросов для запроса информации о пользователе.

прерывать ваше заклинание, не спрашивайте меня почему, так это делалось раньше.

Сделаем простую арифметику:1 + 10 + 10 = 21
Боже мой, в изначальном небе нет слияния данных.

Позже, по моей неоднократной просьбе, наконец-то стало вызывать два интерфейса:

  1. Возврат 10 единиц базовой информации за раз
  2. Используйте значение идентификатора в наборе данных на шаге 1, а затем пакетный запрос

Проделаем более простую арифметику:1 + 1 = 2

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

Сегодня давайте рассмотрим объединение данных массива вместе.

демонстрационные данные

Предположим, что есть два набора данных, один из которых представляет собой базовые данные пользователя, а другой — данные о баллах.uidассоциация.

export const usersInfo = Array.from({ length: 10 }, (val, index) => {
    return {
        uid: `${index + 1}`,
        name: `user-name-${index}`,
        age: index + 10,
        avatar: `http://www.avatar.com/${index + 1}`
    }
});

export const scoresInfo = Array.from({ length: 8 }, (val, index) => {
    return {
        uid: `${index + 1}`,
        score: ~~(Math.random() * 10000),
        comments: ~~(Math.random() * 10000),
        stars: ~~(Math.random() * 1000)
    }
});

базовая версия

Двухслойный цикл, сравнение по ключу, а затем присвоение значения.
Я хочу сказать, простой и удобный, XDM, вы не осудите меня. Если это не хорошо, рекомендуется, чтобы наггетсы разработали функцию степпинга.

import * as datas from "./data";

const { usersInfo, scoresInfo } = datas;

console.time("merge data")
for (let i = 0; i < usersInfo.length; i++) {
    var user = usersInfo[i] as any;
    for (let j = 0; j < scoresInfo.length; j++) {
        var score = scoresInfo[j];
        if (user.uid == score.uid) {
            user.score = score.score;
            user.comments = score.comments;
            user.stars = score.stars;
        }
    }
}
console.timeEnd("merge data")
console.log(usersInfo);

версия с базовым хэшем

Основная идея здесь состоит в том, чтобы сначала преобразовать массив в объект. Конечно, его также можно преобразовать вMapобъект.
Заменить поиск по массиву поиском по хешу.

Основная точка:

  1. Найдите уникальный ключ атрибута, который может пометить объект, эта статьяuid
  2. Обход массива с одним атрибутом данныхuidЗначение атрибута используется в качестве ключа атрибута, а один фрагмент данных используется в качестве значения.

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

Вы можете спросить, почему это намного быстрее, ведь поиск по массиву здесь осуществляется не по индексу, а по связному списку.

import * as datas from "./data";

const { usersInfo, scoresInfo } = datas;

console.time("merge data")

const scoreMap = scoresInfo.reduce((obj, cur) => {
    obj[cur.uid] = cur;
    return obj;
}, Object.create(null));

for (let i = 0; i < usersInfo.length; i++) {
    const user = usersInfo[i] as any;
    const score = scoreMap[user.uid];

    if(score != null){
        user.score = score.score;
        user.comments = score.comments;
        user.stars = score.stars;
    }
}
console.timeEnd("merge data")

console.log(usersInfo);

В этот момент вы можете потянуться и выпить.
Случайно выпьешь слишком много, ты выпьешь слишком много.

Эта реализация имеет несколько обходов, поэтому мы выпрыгиваем после достижения цели.

публикация с базовым хэшем

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

Говорим с данными:

Если в нашем списке 100 элементов данных, необходимо объединить только 10 элементов данных. Предположим, элементы 40-49 в списке — это данные, которые нужно объединить.

Давай посчитаем:100-50 = 50

Эта сцена будет пройдена еще 50 раз. При разных сценариях количество многократных обходов тоже разное.

import * as datas from "./data";

const { usersInfo, scoresInfo } = datas;

console.time("merge data")

const scoreMap = scoresInfo.reduce((obj, cur) => {
    obj[cur.uid] = cur;
    return obj;
}, Object.create(null));


const len = scoresInfo.length;
let count = 0;
let  walkCount = 0;
for (let i = 0; i < usersInfo.length; i++) {
    const user = usersInfo[i] as any;
    const score = scoreMap[user.uid];

    walkCount++;
    if(score != null){
        count++
        user.score = score.score;
        user.comments = score.comments;
        user.stars = score.stars;       

        if(count>=len){
            break;
        }
    }
}
console.log(`合并完毕：遍历次数${walkCount}, 实际命中次数${count}, 预期命中次数${len}`)

console.timeEnd("merge data");

console.log(usersInfo);

В этот момент вы очаровательно улыбнулись, открыли Наггетс и обнаружили, что статья на первой странице на самом деле идет от первой до второй страницы.

фокус第二页, да наши данные вообще подгружаются в пагинации.

Теоретически мы тянем одну страницу и один раз объединяем данные. То есть в большинстве случаев данные, извлеченные позже, добавляются к исходному списку.

После того, как новые данные будут добавлены в исходный список, будет ли быстрее проходить в обратном порядке? Ответ определенно да.
Конечно, если вытащить данные позже, выставить вперед, и последовательный обход будет быстрее.

Базовая хэш-выпрыгивающая обратная версия

Разница между обходом в обратном порядке и последовательным обходом заключается в том, что один выполняется спереди назад, а другой — сзади наперед. код показывает, как показано ниже

import * as datas from "./data";

const { usersInfo, scoresInfo } = datas;

console.time("merge data")

const scoreMap = scoresInfo.reduce((obj, cur) => {
    obj[cur.uid] = cur;
    return obj;
}, Object.create(null));


const len = scoresInfo.length;
let count = 0;
let  walkCount = 0;
for (let i = usersInfo.length - 1; i>=0 ; i--) {
    const user = usersInfo[i] as any;
    const score = scoreMap[user.uid];

    walkCount++;
    if(score != null){
        count++
        user.score = score.score;
        user.comments = score.comments;
        user.stars = score.stars;       

        if(count>=len){
            break;
        }
    }
}
console.log(`合并完毕：遍历次数${walkCount}, 实际命中次数${count}, 预期命中次数${len}`)

console.timeEnd("merge data");

console.log(usersInfo);

В этот момент вы уже собирались уходить, как вдруг коллега А увидел вас и обнаружил, что вы пишете слияние массивов.

Коллега АСкажи: Ух ты, напиши слияние данных, мне тоже нужно, можно кстати абстрагировать и инкапсулировать. Мои данные имеют тип добавления, то есть обход в обратном порядке.

После того, как коллега А закончил говорить, несколько коллег встали и сказали: «У меня тоже есть потребности».

Коллега БСкажи: Шахта вставлена ​​в голову и ее нужно пройти последовательно.
Коллега ССкажите: свойства, которые я хочу объединить,a.b.cТакого рода.
Коллега ДинСкажи: то, что я хочу слить,a[0].bТакого рода.

В это время, что вы делаете?

Открытый исходный код

И подчеркивание, и lodash работают с данными, но они не соответствуют нашим потребностям. С ним конечно можно. Но если вы все полагаетесь на lodash, то ваша переносимость под вопросом.

array-union, array-merge-by-key, deep-mergerА так есть возможность слияния, но она не так хороша, как мы ожидали.

Забудь, напиши сам.

Подготовьте инструменты

Чтение и установка свойства

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

разноеlodash.getОн отлично реализован, давайте взглянем на его официальное демо:

var object = { 'a': [{ 'b': { 'c': 3 } }] };
 
_.get(object, 'a[0].b.c');
// => 3
 
_.get(object, ['a', '0', 'b', 'c']);
// => 3
 
_.get(object, 'a.b.c', 'default');
// => 'default'

Это очень мощно? Аналогично, настройки свойств, lodash предоставляетlodash.set, мы получили проблеск.

var object = { 'a': [{ 'b': { 'c': 3 } }] };
 
_.set(object, 'a[0].b.c', 4);
console.log(object.a[0].b.c);
// => 4
 
_.set(object, ['x', '0', 'y', 'z'], 5);
console.log(object.x[0].y.z);
// => 5

Здесь вы можете сказать, что не полагаетесь на lodash, и дело не только в lodash.
Пожалуйста, не волнуйтесь, друзья, мы реализуемвсеохватность.

Удаляем те, которые нам не особо нужны, ядро ​​это три метода

  • stringToPath: преобразовать путь в массив
  • getProperty: прочитать свойство
  • setProperty: установить свойство
const stringToPath = (string: string) => {
    const result = [];
    if (string.charCodeAt(0) === charCodeOfDot) {
        result.push('');
    }
    string.replace(rePropName, ((match, expression, quote, subString) => {
        let key = match;
        if (quote) {
            key = subString.replace(reEscapeChar, '$1');
        }
        else if (expression) {
            key = expression.trim();
        }
        result.push(key);
    }) as any);
    return result;
};

function getProperty(obj: Object, key: string, defaultValue: any = undefined) {

    if (!isObject(obj)) {
        return defaultValue;
    }

    const path = stringToPath(key);

    let index = 0;
    const length = path.length;

    while (obj != null && index < length) {
        obj = obj[path[index++]];
    }
    return (index && index == length) ? obj : undefined || defaultValue;
}

function setProperty(obj: Object, path: string, value: any = undefined) {

    if (!isObject(obj)) {
        return obj;
    }
    const keys = stringToPath(path);

    const length = keys.length;
    const lastIndex = length - 1;

    let index = -1;
    let nested = obj;

    while (nested != null && ++index < length) {
        const key = keys[index];
        let newValue = value;

        if (index != lastIndex) {
            const objValue = nested[key];
            newValue = undefined;
            if (newValue === undefined) {
                newValue = isObject(objValue) ? objValue : (isIndexLike[keys[index + 1]] ? [] : {})
            }
        }
        nested[key] = newValue;
        nested = nested[key];
    }
    return obj;
}

На этом проблема чтения и установки многоуровневых атрибутов решена.

Следующая немного более сложная проблема доступа — это проблема прямой последовательности и ретроспективного анализа.

Вперед и воспоминания - итераторы

Будь то обход в прямом порядке или обход в ретроспективе, его суть — итерация.
Согласно традиционной реализации, три способа

  1. if/else + два цикла for
  2. while
  3. forEach, уменьшить и т. д. массивов

Но нет возможности разделить логические суждения, последовательные они или флешбеки, эти суждения прописываются в обходном коде, и читабельность кода станет хуже.

Мы должны думать об итераторах здесь, об итераторах.

Используйте функции более высокого порядка для инкапсуляции рекурсивной логики и заботьтесь только о hasNext и current извне.

function getStepIter(min: number, max: number, desc: boolean) {

    let start = desc ? max : min;
    let end = desc ? min : max;

    if (desc) {
        return {
            hasNext() {
                return start >= end
            },
            get current() {
                return start;
            },
            next() {
                return --start

            }
        }
    }
    return {
        hasNext() {
            return end >= start
        },
        get current() {
            return start;
        },
        next() {
            return ++start
        }
    }
}

После того, как эти две большие проблемы будут решены, начинайте закатывать рукава, просто делайте это!

благодарныйSSShuai1999Предлагаемые решения по оптимизации, Количество строк кода уменьшается. существуетhasNextКогда есть тройная операция.

function getStepIter(min: number, max: number, desc: boolean): any { 
    let [start, end, operator] = desc ? [max, min, -1] : [min, max, +1] 
     return { 
         hasNext() { 
             return desc ? start >= end : end >= start 
         }, 
         get current() { 
             return start; 
         }, 
         next() { 
             return start += operator 
         } 
     } 
 }

Реализация

немного.
Будет ли эта альпака пробегать мимо, ха-ха.
Из-за нехватки места, пожалуйста, перейдите наarrayMerge

демо

см. код

data.ts, Мы уменьшаем количество данных для удобства просмотра результатов.
uid userInfo здесь 1,2,3
uid scoresInfo здесь 2,3
Это предназначено для демонстрации обхода воспоминаний.

// data.ts
export const usersInfo = Array.from({ length: 3 }, (val, index) => {
    return {
        uid: `${index + 1}`,
        name: `user-name-${index}`,
        age: index + 10,
        avatar: `http://www.avatar.com/${index + 1}`
    }
});

export const scoresInfo = Array.from({ length: 2 }, (val, index) => {
    return {
        uid: `${index + 2}`,
        score: ~~(Math.random() * 10000),
        comments: ~~(Math.random() * 10000),
        stars: ~~(Math.random() * 1000)
    }
});

test.ts

import { mergeArray } from "../lib/array";

import * as datas from "./data";

const { usersInfo, scoresInfo } = datas;


const arr = mergeArray(usersInfo, scoresInfo, {
    sourceKey: "uid", // 源列表对象的用来比较的属性键
    targetKey: "uid",  // 目标列表对象的用来比较的属性键
    sKMap: {
        "score": "data.score",  // 把源的score属性映射到目标对象的data.score属性上
        "comments": "data.comments"， // 把源的comments属性映射到目标对象的data.comments属性上
        "stars": "stars" // 把源的stars属性映射到目标对象的stars属性上
    }
});

console.log("arr", arr);

результат операции:
targetArr(3), sourceArr(2), 统计：遍历次数2, 命中次数2
Это означает: длина списка — 3, длина сливаемого — 2, кумулятивный обход — 2 раза, попадание — 2 раза.

mergeArray:: targetArr(3), sourceArr(2), 统计：遍历次数2, 命中次数2
arr [
  {
    uid: '1',
    name: 'user-name-0',
    age: 10,
    avatar: 'http://www.avatar.com/1'
  },
  [Object: null prototype] {
    uid: '2',
    name: 'user-name-1',
    age: 11,
    avatar: 'http://www.avatar.com/2',
    data: { score: 6979, comments: 3644 },
    stars: 434
  },
  [Object: null prototype] {
    uid: '3',
    name: 'user-name-2',
    age: 12,
    avatar: 'http://www.avatar.com/3',
    data: { score: 6348, comments: 320 },
    stars: 267
  }
]

Пока что это действительно можно считать высоким абзацем.

задавать вопросы

  1. Что не так с текущей версией и как это исправить.
  2. Какие улучшения есть в текущей версии?

Любой, кто оставит сообщение, автор ответит на 100% и войдет в ваше пространство Nuggets, чтобы наступить.

напиши в конце

Писать нелегко, если вы думаете, что это хорошо, лайк и комментарий — моя самая большая мотивация.

Категории