This is the 8th day of my participation in the More text Challenge. For details, see more text Challenge

preface

As a front end, the data returned by the server is easy to use and can greatly improve the development efficiency. Do not make two or more network requests and then merge data that can be provided by one interface.

However, both ideal and reality, reality always find me, can not feel the warmth of the ideal.

Brutal experience

You may not believe it, but believe me, for I am kind.

One of our business has a list of data and needs to call three interfaces to merge the data. The details are as follows:

  1. 10 basic information is returned at a time
  2. 10 more requests for details
  3. Using an ID value from the result in step 2, make another 10 requests for user information

Interrupt your casting. Don’t ask me why. It’s been done before.

Let’s do some simple arithmetic: 1 + 10 + 10 = 21 My goodness, there is no data merge in heaven.

After my repeated requests, I finally changed to calling two interfaces:

  1. 10 basic information is returned at a time
  2. Use the ID value in the data set in step 1, and then batch query

Let’s do a simpler arithmetic: 1 + 1 = 2

This is only one more time than returning all the data at once, but it throws up an unavoidable problem of merging arrays of data.

Today, let’s explore array data merging.

The demo data

Suppose you have two sets of data, user base data and score data, associated by a 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)}});Copy the code

Basic version

Two levels of loop, compare by a key, and assign. I mean, easy to use, XDM, if you don’t scold me. May not also suggest that the Nuggets make a step on the function.

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);
Copy the code

Basic – Hash version

The basic idea here is to convert an array into an object. It can also be a Map object. Replace array lookup with hash lookup.

Emphasis:

  1. Find a unique attribute key that can mark an objectuid
  2. Traverses the array to a single data attributeuidAs the attribute key, and a single piece of data as the value

Looking up object properties is much faster than looking up arrays, so you get a lot of performance improvements here.

You might be wondering why it’s so much faster, because the array lookup here is not in terms of the index lookup, it’s in terms of the linked list lookup.

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);
Copy the code

At this point, you might stretch and take a sip of water. Accidentally got drunk. You got drunk.

This implementation is multi-traversal, so when we reach our goal, we jump out.

Basic -hash- skip publishing

The biggest difference between this version and the previous version is the addition of the count function, which records the number of merges and jumps out when the expected number is reached. You might laugh at the idea of remembering numbers.

We use data:

Suppose we have 100 pieces of data in our list and only 10 pieces need to be merged. Suppose items 40 to 49 in the list are the data to be merged.

Let’s count the numbers: 100 minus 50 is 50

This scenario is traversed 50 more times. The number of multiple traversals varies depending on the scenario.

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('Merge completed: Number of iterations${walkCount}, the actual hit times${count}, the expected number of hits${len}`)

console.timeEnd("merge data");

console.log(usersInfo);
Copy the code

Here, you smile very charming, open the nuggets, found themselves on the first page of the article, actually ran from the first page to the second page.

Highlight the second page, yes our data is usually loaded in pages.

We theoretically pull a page and merge the data once. That is, in most cases, the data that is pulled is appended to the original list.

The new data is appended to the original list, so is it faster to iterate backwards? The answer, yes. Of course, if you pull back the data, and you put it forward, it’s faster to iterate sequentially.

Basic -hash- Jump out – reverse version

The difference between reverse and sequential traversal is that one is front to back and one is back to front. The following code

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('Merge completed: Number of iterations${walkCount}, the actual hit times${count}, the expected number of hits${len}`)

console.timeEnd("merge data");

console.log(usersInfo);
Copy the code

At this point, just as you are about to leave, a colleague looks at you and finds you are writing an array merge.

Colleague a say: wow, write data merge, I this also have demand, you by the way abstract encapsulate once. My data is append, which means I’m going backwards.

Colleague a say that finish, several colleague stand up, say, I this also have demand.

Colleague B said: mine is inserted into the head, need to order traversal. Colleague C said: THE attribute I want to merge is A.B.C. My colleague Ding said: WHAT I want to merge is a[0]. B.

Now what do you do?

Turn to the open source

Both underscore and Lodash have operations on data, but they fall short of what we need. Of course you can do it with it. But if you rely on lodash, then your mobility is questionable.

Array-union, Array-merge-by-key, deep-merger and so on have the ability to merge, but not as much as we expected.

Forget it. Write it yourself.

Prepare tool class

Property read and set

So let’s just do a little bit of reorganizing, the merge of arrays, when we do that, is actually the merge of objects. Object merge level attributes merge easy, multi-level, is a problem.

The other lodash.get has been implemented perfectly, so let’s take a look at the official demo:

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'

Copy the code

Is it very powerful? Similarly, with the setting of properties, lodash provides lodash.set, which we have a look at.

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

Copy the code

Here, you might say, well, you don’t rely on lodash, they’re all lodash. Please don’t be in a hurry, we will carry out the plan.

Let’s cut out the ones we don’t care about, and at its core, there are three methods

  • StringToPath: converts a path to an array
  • GetProperty: read property
  • SetProperty: sets the property
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;
}

Copy the code

At this point, the multilevel property read setting problem is resolved.

The next, slightly more complicated issue is that of positive sequence and flashback.

Positive sequence and flashback – iterators

Whether it is positive order traversal or reverse traversal, its essence is iteration. Traditionally, there are three ways

  1. If /else + two for loops
  2. while
  3. Array forEach, reduce, etc

However, there is no escape from the need to separate the logical decisions between order and flashback, and when these decisions are written in traversal code, the code becomes less readable.

We should think of iterators here, iterators.

Use higher-order functions, encapsulate recursive logic, and externally only care about hasNext and 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
        }
    }
}
Copy the code

These two big problems solved, begin to roll up your sleeves, just do it! .

Thanks to SSShuai1999, the number of lines of code was reduced. There is a triadic operation in 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 
         } 
     } 
 }

Copy the code

The specific implementation

A little. Will that alpaca run by? Haha. For space problems, please move to arrayMerge for all code

demo

Look at the code

Data.ts, we reduce the amount of data to make it easier to see the results. The uid of usersInfo here is 1,2,3 and the uid of scoresInfo here is 2,3 and this is designed to demonstrate the reverse traversal.

// 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)}});Copy the code

test.ts

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

import * as datas from "./data";

const { usersInfo, scoresInfo } = datas;


const arr = mergeArray(usersInfo, scoresInfo, {
    sourceKey: "uid".// Attribute key of the source list object for comparison
    targetKey: "uid".// Attribute key of the target list object for comparison
    sKMap: {
        "score": "data.score".// Map the source score attribute to the target object's data.score attribute
        "comments": "data.comments".// Map the source comments property to the data.comments property of the target object
        "stars": "stars" // Map the stars attribute of the source to the stars attribute of the target object}});console.log("arr", arr);
Copy the code

Run result: targetArr(3), sourceArr(2), statistics: traversal number 2, hit number 2 It means: the length of the list is 3, the length of the merge is 2, the total traversal is 2, and the hit number is 2.

mergeArray:: targetArr(3), sourceArr(2), statistics: the number of passes2, hit times2
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}]Copy the code

So far, so high and so low.

Ask questions

  1. What’s wrong with the current version and how to fix it.
  2. What are the improvements in the current version?

All comments, I 100% reply and enter your gold space to tread.

Write in the last

Writing is not easy, if I feel good, praise a review, is my biggest motivation.